Onye's Journal

Algorithms are important. They help us solve problems. They help us understand stuff. This book is about algorithms.

Section 1.1 talked about the stable matching problem and the gale shapely soluition to it. A typical example of the stable matching problem is n men and n women looking to be matched, with each man and woman having a strict order of preferences. For a given matching, m and w form an unstable pair if they each prefer each other to their current partner. For n men and n women with strict preferences, it is always possible to find a matching with no unstable pairs, and the gale shapely algorithm does just that. This works by taking any single man and attempting to pair him the his highest rated woman that we have not attempted to pair him with yet. If she prefers him to her current match, the pairing is successful, and she is paired with him and her current partner becomes single again. Repeat this until every man has proposed to every women.

Chapter 2 discusses the computational tractability and the running time of algorithms. It also discusses asymptotic order of growth and Big O. Algorithms that are polynomial time are O(n^k) for some k. These are said to be efficient. As opposed to that, some algorithms may be O(k^n), for some k > 1, for example. These algorithms are incredibly computationally intensive and quickly become impossible to calculate in a reasonable amount of time. For example, an exponential algorithm may run in under a second for n = 1, but take billions of years for n = 20.