Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:suraj:chapter1.txt [2012/01/23 01:06] – bajracharyas | courses:cs211:winter2012:journals:suraj:chapter1.txt [2012/01/25 01:41] (current) – bajracharyas | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Chapter 1: ====== | + | ====== Chapter 1 ====== |
| ===== Introduction: | ===== Introduction: | ||
| Line 32: | Line 32: | ||
| - | w gets engaged from the moment she receives a proposal and her partner only keeps getting better, but not worse in terms of her preference | + | * w gets engaged from the moment she receives a proposal and her partner only keeps getting better, but not worse in terms of her preference |
| - | It is reversed for m, i.e. his partner keeps getting worse in terms of his preference | + | |
| - | Since at most, each m proposes each w only once, the algorithm has an upper bound order of n^2 | + | |
| - | If m is free at any point, then there should be a w to whom he hasn't proposed yet. This is because there are the same number of w as m | + | |
| - | The set returned at the end is a perfect matching | + | |
| - | Every execution returns the same set (Need help) | + | |
| - | In Stable Matching S*, each w is paired with her worst valid m (Need help) | + | |
| ==== Interval Scheduling ==== | ==== Interval Scheduling ==== | ||
| Line 64: | Line 64: | ||
| This problem is like a game played by two franchises trying to maximize their output by selecting different locations available, turn by turn, with rules that each of them cannot be too close to each other. This is an example of “PSPACE-complete problems”, | This problem is like a game played by two franchises trying to maximize their output by selecting different locations available, turn by turn, with rules that each of them cannot be too close to each other. This is an example of “PSPACE-complete problems”, | ||
| + | |||
| + | ==== Questions and Comments ==== | ||
| + | |||
| + | Definitely did give me an idea of what we would be dealing in this class. Sounds fun. Though I have a question, why would there be the same pairs in each execution of the Stable Matching Algorithm on a set of data? | ||
| + | |||
| + | Aside from that, I thought the chapter was smooth and was understandable. Class discussions helped too. | ||
