2.2 Graduation

The CS program at a University has m courses. In order to graduate, a student must satisfy several requirements. Each requirement is of the form you must take at least ki courses from subset Si. The problem is to determine whether or not a given student can graduate. The tricky part is that any given course cannot be used towards satisfying multiple requirements. For example if one requirement states that you must take at least two courses from {A, B, C}, and a second requirement states that you must take at least two courses from {C, D, E}, then a student who had taken just {B, C, D} would not yet be able to graduate. Your job is to give a polynomial-time algorithm for the following problem. Given a list of requirements r1, r2, . . . , rt (where each requirement ri is of the form: you must take at least ki courses from set Si), and given a list L of courses taken by some student, determine if that student can graduate. In particular, show how you can solve this using network flow