COMPSCI 311 Midterm: CMPSCI 311 UMass Amherst Solutions 1
31 Jan 2019
School
Department
Course
Professor
Document Summary
Note: latex template courtesy of uc berkeley eecs dept. You may work in groups, but you must individually write your solutions yourself. There are four questions, each worth 25 points total. This assignment is by 11:59pm on 2/7/2018 in gradescope. You may submit a scanned handwritten document, but a typed submission is preferred: stable marriages (a) stable marriages: k&t ch 1, ex 5, strong instability. Lets see if the propose-and-reject algorithm from class works. If a college proposes to the student, the student only accepts if the student prefers the new proposing college over their current. A college will be content with the student it ends with, as it will have tried all students who it preferred and been rejected or dropped each time until coming to the student it ends with. As students always upgrade, theres no chance that the student will reconsider a school after rejecting it.
