Table of Contents
Chapter 1
This chapter discusses one problem in details and introduces 5 types of problems of distinct complexities.
Section 1: Stable Matching
This section talks about the stable matching problem. It first introduces the problem and the associated history. Then a solution is given in details. Next, the solution algorithm is analyzed. Last, the book states some properties of the algorithm and gives out proofs.Most and the most core materials in this section are covered in class. Thus the reading is relatively less interesting. But it helps organize the lecture materials well. The readable score is 2.
Section 2: 5 Representative Problems
This section talks about the “five representative problems”. In order to illustrate this problem better, the book also introduces the important concepts of “graphs”. The first representative is the interval scheduling problem and it can be solved using the greedy algorithm. The weighted interval scheduling problem is the second representative and dynamic programming is the best way to solve the problem efficiently. The third one, which is the blueprint of the stable matching problem, is the bipartitie matching problem; augmentation, which is utilized in the stable matching problem, is the algorithm to solve such problems. The forth representative is the independent set problem, where all the previous problems are special cases of this category; it is NP-Hard, thus no efficient algorithms are known for the general cases. The last problem is the competitive facility location problem. It is PSPACE-Hard-easy to check a solution but hard to be solved. The motivation of showing this problem is to display 3 different level of “solvability” and help us to become familiar with the idea that a subtle change in the narration of the problem could cause dramatic change in terms of solvability. This section also aims at improving our understanding of how difficult, or how solvable different problems are. The concept of “bipartiteness” (node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y.) is new to me. I really like to see the 5 different categories and the insights of the algorithm behind all the fancy coding. It suddenly organizes my visions towards algorithms. The readable score for this section is 10.
