Chapter 1

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 (p 6): 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

Now that we've solved the Stable Matching Problem, we have an idea of how the process of algorithm design works. In general, we will usually: formulate a mathematically precise question, design an algorithm, prove it is correct, and give a bound on its running time.

Here are some problems representing the different types we will encounter later.

• Interval Scheduling (Greedy Algorithms): How can we maximize the number of reservations accepted for a given resource?
• Weighted Interval Scheduling (Dynamic Programming): Same as above but some requests are worth more than others.
• Bipartite Matching (Augmentation/ Network Flow Problems): How can we find a matching of maximum size, given an arbitrary bipartite graph?
• Independent Set (No efficient algorithm): Given a graph, how can we find an independent set that is as large as possible?
• Competitive Facility Location (No efficient algorithm, difficult to check a solution): In the game of selecting nodes, all selected nodes must form an independent set and P1 starts. Is there a strategy for P2 so that no matter how P1 plays, P2 can select a set of nodes with a total value of B?

Readability: 7