This is an old revision of the document!
Table of Contents
Week 1
Chapter 0: Preface
Algorithms are everywhere. By using algorithms, we can not only find solutions to difficult problems but also do so efficiently and prove that our findings are accurate. If we work hard, we can find solutions to problems as difficult as the Stable Matching problem, as culturally-welcome as the same-sex Stable Matching problem1), and as easy as the Traveling Salesman Problem2) Algorithms help us to take a problem, break it down to its essential components, solve that problem and prove it with advanced logic, and then apply that algorithm to real life problems.
Chapter 1: Introduction: Some Representative Problems
The Stable Matching Problem
Gale and Shapeley developed an algorithm to solve the Stable Matching Problem, typically referred to as the Stable Marriage Problem. The problem states that given n men and n women and a list for each man's and woman's preference list of preferred marriage partners, pair up all of the men and women together such that no unstable matchings occur. An unstable matching is any occasion when a man, m1 is paired with a woman w1 and a man m2 is paired with a woman w2 but m1 and w2 would prefer to be married to each other over their current paired partners. The algorithm consists of pairing
Chapter 2: Basics of Algorithm Analysis
1)
The footnote on page 3 of the textbook mentions that Gale and Shapely also considered a same-sex case of the Stable Marriage Problem that is very different from the heterosexual Stable Marriage Problem. This article from the “Pholosophy for Programmers” blog is a good read because it addresses the merit of such an algorithm while providing an interesting perspective on the subject.
2)
Note that the italicized words are sarcastically opposite of what they actually are. 
You could leave a comment if you were logged in.
