Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
courses:cs211:winter2011:journals:wendy:chapter1 [2011/01/19 14:46] – created shangw | courses:cs211:winter2011:journals:wendy:chapter1 [2011/01/19 23:28] (current) – shangw | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Chapter 1 ====== | ====== Chapter 1 ====== | ||
- | + | This chapter discusses one problem in details and introduces 5 types of problems of distinct complexities. | |
- | My notes on Chapter 1 readings | + | |
===== Section 1: Stable Matching ===== | ===== Section 1: Stable Matching ===== | ||
- | * Summary | + | 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 |
- | * Insights I have | + | |
- | * The questions I have | + | ===== Section 2: 5 Representative Problems ===== |
- | * How readable section was | + | |
- | ===== 1.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, |
+ | 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. | ||
- | Summarize the section, issues, what you figured out, readability, | ||
---- | ---- | ||