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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: