In most US universities, undergraduate students must satisfy the requirements of a degree program in order to graduate. The general rules are:
- The university has a minimum number of total credits needed, and a series of subject-based baskets (e.g. sciences, humanities, writing, etc) with their own minimum credit counts.
- A program (e.g. biology, art history, etc) has a list of required courses, plus one or more baskets of degree-related topics with their own minimum credit counts.
- Each course counts for a fixed number of credits and fits in one or more of the above categories (e.g. some could potentially be counted in more than one degree-related and/or subject-based basket).
- Each course can only be counted towards a single basket at a time (cannot be shared or divided to satisfy multiple requirements, but could be moved to another basket if eligible).
Given students completing arbitrary lists of courses, is there a fast (O(n^2) or lower) deterministic algorithm to find when a given student first completes enough courses to satisfy their degree requirements (i.e. efficiently arrange the completed courses to fill all baskets while minimizing the number of credits exceeding the minimums)? If not, is there a commonly-used algorithm believed to reduce the number of cases where its basket-filling choices are inefficient?
- If a course only satisfies one basket, put it there.
- ?
- Graduate!
1 Answer 1
I'm assuming we're testing if a student satisfies the requirements for a specific degree, not whether it satisfies any degree.
If so, we can immediately calculate the total number of credits, and whether all required courses have been satisfied with a single loop over the completed courses, using a hashset of required courses that we remove from the set when completed, checking that it is empty after the loop.
The only interesting question is allocating courses to baskets. Unfortunately, this problem is very much NP-hard in general. Even if we remove the limitation that some courses can only be put into certain baskets, and even if each basket required the same number of credits you'd still have a decision variant of the bin covering problem.