CS101 Quiz 11: Solutions

  1. Each student accepts the proposal, and nobody better ever comes along. As a result, the slots are as happy as can be, but the students as unhappy as can be. Since no two slots would consider swapping, the arrangement is stable (though unpleasant).
  2. Proposal i causes student N to drop the arrangement with proposal i-1. Thus, the arrangement is broken N-1 times.
  3. Since every slot favors N, so does slot 1. Thus, student N accepts slot 1's proposal and rejects all others. Thus, the arrangement for N is never broken.
  4. Can be formulated from the answer to question 2.
    Slot First Second Third Fourt
    Number Choice
    1 4 3 2 1
    2 4 3 2 1
    3 4 3 2 1
    4 4 3 2 1
    Student First Second Third Fourt
    Number Choice
    1 4 3 2 1
    2 4 3 2 1
    3 4 3 2 1
    4 4 3 2 1