Chapter 1

My notes on the Preface & Chapter 1 readings

The ideas surrounding algorithm analysis are important and pervasive to a variety of disciplines, and a firm understanding of these ideas and their related problems offer us an important mode through which we can understand computer science. Algorithm design is about both finding an elegant mathematical representation of a problem, and then using algorithm design patterns to solve that problem. A quote I especially like from this passage is “[algorithms] form the language that lets you cleanly express the underlying questions” of a problem (p. xiv).

• Stable matching is the process by which we match members of multiple groups based on their preferences for one another.
• The Gale-Shapely algorithm is a stable-matching algorithm which completes, finding a stable matching for all members of each group.
  • The version of the Gale-Shapely algorithm we covered in class is likely a simpler version of the algorithm used by W&L panhel in order to match women and sororities during sorority recruitment, which is a matching problem that came up in my graph theory class for some reason last year.
• What are the limitations to using the Gale-Shapely algorithm? Are there specific types of stable matching problems for which G-S does not work out, ignoring the obvious such as uneven numbers of members in each group?
• I found this section to be fairly readable, and I think I'm going to like the way this book is set up and written.