Posted by: atri | September 12, 2012

## Lect 7: Analyzing Gale Shapley algorithm

In today’s lecture, we finished proving that the Gale Shapley algorithm has at most $n^2$ iterations. We also proved that the algorithm outputs a perfect matching. Next lecture, we will finish the proof that the perfect matching is indeed a stable matching and then move on to Chapter 2 in the book. If you are craving reading assignments, I will assign the “Extensions” subsection in Section 1.1 in the book as a reading assignment on Friday.

The slides and notes for the lecture have been uploaded.