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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Categories

%d bloggers like this: