The Department of Commuter Silence at Sham-Poobanana University has a flexible curriculum with a complex set of graduation requirements. The department offers n different courses, and there are m different requirements. Each requirement specifies a subset of the n courses and the number of courses that must be taken from that subset. The subsets for different requirements may overlap, but each course can be used to satisfy at most one requirement. For example, suppose there are n = 5 courses A, B, C, D, E and m = 2 graduation requirements:
• You must take at least 2 courses from the subset A, B, C.
• You must take at least 2 courses from the subset C, D, E. Then a student who has only taken courses B, C, D cannot graduate, but a student who has taken either A, B, C, D or B, C, D, E can graduate.
Describe and analyze an algorithm to determine whether a given student can graduate. The input to your algorithm is the list of m requirements (each specifying a subset of the n courses and the number of courses that must be taken from that subset) and the list of courses the student has taken.
The post a flexible curriculum with a complex appeared first on My Assignment Online.