Homework 1, Greedy Stable Matching.

Short Description:

Goals

• Demonstrate Something

Formal Description

1. Consider the greedy stable matching algorithm

   GREEDY-STABLE-MATCH(M,W)
   
    mark all m ∈ M and w∈ W as free
    S ← {}
    while there is a m ∈ M who is free
       w ← highest choice in m's preference list that is free
       S ← S ∪ (m, w)
       mark m and w as engaged
    return S
   

   1. [10 points] Trace this algorithm with the following data. Show your work.

      1 C B E A D 2 A B E C D 3 D C B A E 4 A C D B E 5 A B D E C

      A 3 5 2 1 4 B 5 2 1 4 3 C 4 3 5 1 2 D 1 2 3 4 5 E 2 3 4 1 5

   2. [10 points] Is your solution a stable match? Argue that it is or show an in-stable pair.
   3. [10 points] Discuss how the selection of m in line 3 changes the result of the algorithm. Could you change the answer with a different set of random selections?
2. Testing a solution to the stable match algorithm
   1. [10 points] Create an algorithm which, given the input to the stable match problem and (M, W) the output (S) determines if S is a stable match. Use algorithm notation similar to that in the lectures and above.
   2. [10 points] Using the results from the notes, run your algorithm on a stable match and a match that is not stable to show that it works for known example data.
   3. [10 points] Argue that your algorithm is correct.

Notes

Required Files

Submission