3

I have a list of courses taken by a student, as well as several requirements. Each requirement consists of a list of courses that fulfill that requirement and the number of such courses that must be taken.

How can I determine whether a student has passed all of his or her requirements, given the restriction that a single course can only count towards one requirement at a time?

My initial thought was to iterate through the list of requirements and remove courses from the student's list as they are used by requirements, but this can run into difficulties in cases where a course is on multiple requirements lists:

Student's courses: A, B, C, D

Requirement Foo: 2 courses from A,B,C,D
Requirement Bar: 1 course from A,B

If A and B are used up first to fill requirement Foo, then they are unavailable to fill requirement Bar.

How can I efficiently explore the possible allocations of courses to different requirements to determine if some arrangement results in all of the requirements being fulfilled? Does this map to some standard set or graph theory problem that I could apply the solution to?

  • 1
    Your example and question seem to contradict the restriction in your original problem: "given the restriction that a single course can only count towards one requirement at a time" – Miguel van de Laar Mar 4 '16 at 23:26
  • 3
    @MiguelvandeLaar: It's an optimization problem. Given a set of completed classes, map the classes to the requirements in such a way that will satisfy as many requirements as possible. – Robert Harvey Mar 4 '16 at 23:27
  • 1
    Don't try to go directly to an efficient solution right off the bat. Try something, and you'll learn from it. It may even help clarify your understanding of the problem, which is always a good thing. Further, you may not need the best possible algorithm; it's hard to know until you have a base line. There are many possibilities here, some multi-cpu or parallel computation may be a good approach, since I suspect this may be a classic kind of problem whose solution is that of trying all permutations (as is graph coloring, for example). – Erik Eidt Mar 5 '16 at 0:30
  • You can model this as a boolean satisfiability problem.Foo would translate as : (A and B) or (A and C) or (A and D) or (B and C) ... etc. while Bar would be (A or B). This problem is NP-complete so there's no efficient way of doing what you want to do. You're going to have to brute force it. – Adrian Apr 7 '16 at 11:02
  • @Adrian your model does not take into account that a course can only satisfy one requirement. Also, the exponential expansion of multi-course requirements does not seem efficient. I propose a more efficient model in my answer below. – Aniket Schneider Apr 7 '16 at 20:34
1

After brainstorming on this for a while, I believe an algorithmically efficient way to do this is to model it as a max flow problem:

Start with a Source vertex and a Sink vertex.

Each course taken by the student is represented by a vertex which is connected to the Sink via an edge with capacity 1.

Each requirement is represented by a vertex which is connected to the Source via an edge with capacity C, where C is the number of courses required by that requirement. This vertex is connected by an edge with capacity 1 to each course that can fulfill that requirement.

One can then apply Floyd-Fulkerson, or another Max-Flow algorithm. If the max flow through the graph is equal to the sum of the number of courses required for each requirement, then all the requirements have been satisfied; inspecting the flow over the edges from requirements to courses will give the details of the allocation of courses to different requirements.

Based on the complexity of Floyd-Fulkerson, I think this should have worst-case running time of O(r(R+S)), where r is the total number of required courses, R is the size of the requirements specification, and S is the number of courses taken by the student.

Of course this is all theoretical right now, as I have yet to implement it, and it might be overkill for my practical application.

  • I am facing the exact same use case and would be interested to know how this worked out? I have been looking at using a variant of the stable marriage algorithm or the knapsack problem when I ran across this. Did you ever end up implementing it? – swestner Jul 6 '16 at 1:29
  • Sadly, this never went beyond a thought experiment for me. In our use case, a much simpler brute force method gave adequate performance. – Aniket Schneider Jul 8 '16 at 16:18
1

(if only as a starting point, towards a better solution)

so, here is a naive, brute-force backtracking (in ECMAScript 5) I was thinking of, which should always find a solution if there is any, along with the trace of it.

This could certainly be adapted, likewise, to explore and return all the possible solutions (if more than one), along with their traces:

https://jsfiddle.net/YSharpLanguage/w2zoz3us

function fulfilled(solution, requirements, attended, relaxer, index) {
  function newRequirement(original, isRelaxed) {
    if (isRelaxed) {
      var i = original.courses.indexOf(relaxer),
          // Exclude the relaxer course from
          // the courses of a relaxed requirement
          newCourses = original.courses.slice(0, i).
                       concat(original.courses.slice(i + 1)),
          // Decrement the weight of a relaxed requirement
          newWeight = original.weight - 1;
      return {
        id: original.id,
        weight: newWeight,
        courses: newCourses
      };
    }
    else {
      return original;
    }
  }
  function someUnfulfilled() {
    // True if any unfulfilled requirement,
    // false otherwise
    return requirements.find(function(requirement) {
      return requirement.weight > 0;
    }) != null;
  }
  // Are we trying to relax some requirement
  // by a given (relaxer) course, or are we
  // merely at the bottom of the call stack?
  if (typeof index !== "undefined") {
    // ... yes, we are relaxing a requirement; so make
    // a new requirement list differing only by it,
    // at index, relaxed by the relaxer course
    var relaxed = requirements[index];
    requirements = requirements.map(function(requirement) {
      return newRequirement(requirement, requirement.id === relaxed.id);
    });
  }
  // Is there any unfulfilled requirement?
  if (someUnfulfilled()) {
    // Is there any more courses being attended?
    if (attended.length > 0) {
      // Current course, head of the attended courses:
      var course = attended[0];
      for (var i = 0; i < requirements.length; i++) {
        var candidate;
        // Try to relax only the unfulfilled requirements:
        if ((candidate = requirements[i]).weight > 0) {
          // Remaining courses, after the current one:
          var remaining = attended.slice(1);
          // Can the current course contribute to the solution
          // by relaxing the candidate (i-th) requirement?
          if (
            (candidate.courses.indexOf(course) >= 0) &&
            (fulfilled(solution, requirements, remaining, course, i))
          ) {
            // Yes, it could; so, record its contribution,
            // and backtrack with a success signal
            solution.push({ course: course, requirement: candidate.id });
            return true;
          } else {
            // (Keep iterating through the requirements)
          }
        } else {
          // (Ignore the already fulfilled requirements)
        }
      }
      // The current course cannot relax any requirement,
      // and also contribute to the solution by doing so;
      // so, backtrack with a failure signal
      return false;
    } else {
      // Not enough of attended courses to fulfill the requirements;
      // so, backtrack with a failure signal
      return false;
    }
  } else {
    // All the requirements have been fulfilled by now,
    // so, backtrack with a success signal
    return true;
  }
}

E.g.,

(as in your question's example)

var allRequirements =
    [
      { id: "R1", weight: 2, courses: [ 'A', 'B', 'C', 'D' ] },
      { id: "R2", weight: 1, courses: [ 'A', 'B' ] }
    ],
    aSolution = [ ],
    input = [ 'A', 'B', 'C', 'D' ];

fulfilled(aSolution, allRequirements, input)
aSolution.reverse()

yields:

aSolution === [
  {
    "course": "A",
    "requirement": "R1"
  },
  {
    "course": "B",
    "requirement": "R2"
  },
  {
    "course": "C",
    "requirement": "R1"
  }
]

while,

allRequirements =
    [
      { id: "R1", weight: 3, courses: [ 'A', 'B', 'C', 'D' ] },
      { id: "R2", weight: 2, courses: [ 'A', 'B', 'E' ] }
    ];
aSolution = [ ];
input = [ 'A', 'B', 'C', 'D', 'E' ];

fulfilled(aSolution, allRequirements, input)
aSolution.reverse()

yields:

aSolution === [
  {
    "course": "A",
    "requirement": "R1"
  },
  {
    "course": "B",
    "requirement": "R2"
  },
  {
    "course": "C",
    "requirement": "R1"
  },
  {
    "course": "D",
    "requirement": "R1"
  },
  {
    "course": "E",
    "requirement": "R2"
  }
]

'HTH,

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.