Problem 2: Choosing Electives, Take 2 20 points] Based on the output of your algorithm for the previous question, every student can be associated with an ordered list of preferred electives. In the middle school, there are a total of m elective classes. Each class has space for a finite number of students, which may be different for each class (i.e., there are spaces in class e). There are n students who have submitted their elective preferences, and each student needs to be assigned to a single elective. Unfortunately (budget cuts!) there aren't enough elective seats for all of the students. Any students who do not get placed in an elective will simply have a study hall instead (i.e., they have no elective at all) Each elective requires a different capability from the students. Some have requirements based on auditions (e.g, band and orchestra), while others prefer students with certain backgrounds (e.g., grades in related courses in elementary school). We assume that each elective can provide an algorithm that ranks all of the students in order of their suitability to the course. We want the students to be happy, but we also want them to be well-matched to the assigned courses. We say that a matching is not stable if either of the following conditions holds There are two students s and s' and an elective e such that s is registered for e, s is registered for study ha, and s' is better suited for e than s is There are two students s and s and two electives e and e', s is registered for e and s' is registered for e', but s' is a better fit for e than s is and s' prefers e to e (a) 10 points] Give an algorithm to efficiently compute a stable assignment of students to elective courses. Your algorithm should satisfy both stability conditions above. Briefly state (and justify) a tight upper bound on the running time of your algorithm. Assuming C is the total number of elective seats , we assume nC Problem 2: Choosing Electives, Take 2 20 points] Based on the output of your algorithm for the previous question, every student can be associated with an ordered list of preferred electives. In the middle school, there are a total of m elective classes. Each class has space for a finite number of students, which may be different for each class (i.e., there are spaces in class e). There are n students who have submitted their elective preferences, and each student needs to be assigned to a single elective. Unfortunately (budget cuts!) there aren't enough elective seats for all of the students. Any students who do not get placed in an elective will simply have a study hall instead (i.e., they have no elective at all) Each elective requires a different capability from the students. Some have requirements based on auditions (e.g, band and orchestra), while others prefer students with certain backgrounds (e.g., grades in related courses in elementary school). We assume that each elective can provide an algorithm that ranks all of the students in order of their suitability to the course. We want the students to be happy, but we also want them to be well-matched to the assigned courses. We say that a matching is not stable if either of the following conditions holds There are two students s and s' and an elective e such that s is registered for e, s is registered for study ha, and s' is better suited for e than s is There are two students s and s and two electives e and e', s is registered for e and s' is registered for e', but s' is a better fit for e than s is and s' prefers e to e (a) 10 points] Give an algorithm to efficiently compute a stable assignment of students to elective courses. Your algorithm should satisfy both stability conditions above. Briefly state (and justify) a tight upper bound on the running time of your algorithm. Assuming C is the total number of elective seats , we assume nC