This is an old revision of the document!
Table of Contents
Chapter 1
My notes on Chapter 1 readings
Section 1: Stable Matching
In this section, our goal is to find an algorithm that generates a perfect, stable matching between n men and n women. The Gale-Shapley algorithm accomplishes this.
Algorithm outline: Pick a random man and have him propose to his top choice who he has not yet proposed to. This woman will accept if single or if this man is preferred to her current mate. Otherwise he remains single. Repeat this until every man is engaged or has proposed to every woman.
We found the maximum number of iterations for this algorithm is n^2 and that each execution produces the same set of pairs. Since the men propose, they end up with their best possible match.
Readability: 8
Section 2: Five Representative Problems
- Summary of this section
- Insights I have
- The questions I have
- How readable section was
