## Part 1 ### A ``` initialize all s ∈ S to free while ∃ a free student s who hasn't interviewed with all c ∈ C: c = first company on s's list to whom s has not yet interviewed with if c has open slots: (s, c) engage in salary negotiations else some pair (s', c) already exists where s' is the companies least favorite candidate that it's considering: if c prefers s to s': s' gets the rejection email (s, c) begin negotiations else: (s', c) remain in negotiations ``` The notable modification to the Gale-Shapley algorithm is that we add a clause to account for the fact that companies have multiple slots for internships. Namely, we always consider the pair `(s', c)` where `s'` is the _least_ favorite candidate of company c. ### B This algorithm is O(n^2 * m) (n is students and m is internships). The first n term is because we always have to consider every student, the m term is because the number of companies dictates the maximal number of times that a student could have to re-try their matching. The reason there's an extra n term compared to GS is that the act of finding `s'` every time we try to switch 2 students is another linear scan of the students. If we modified the datastructure used to store the students and companies such that each company maintained a sorted list of the students it had in it's slots, then it would be possible to reduce the complexity to O(m * nlogn) because we could binary search for the students instead of doing linear scans and inserting new students. On the other hand that would increase the space complexity of the algorithm, so I chose to use the O(m * n^2) version.