Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:martinj:chapters1_2 [2018/01/16 18:44] – created martinj | courses:cs211:winter2018:journals:martinj:chapters1_2 [2018/01/19 22:42] (current) – admin | ||
|---|---|---|---|
| Line 4: | Line 4: | ||
| __How should you initially approach complex problems, especially matching ones?__: creating a “bare-bones” version of the problem (ex: simplify the recruitment process to only look at ONE company looking to hire ONE candidate from a set of n applicants) | __How should you initially approach complex problems, especially matching ones?__: creating a “bare-bones” version of the problem (ex: simplify the recruitment process to only look at ONE company looking to hire ONE candidate from a set of n applicants) | ||
| - | ===== The Stable Matching Problem & the Gale-Shapley Algorithm ===== | + | ===== The Stable Matching Problem & Gale-Shapley Algorithm ===== |
| __Defining instability for this problem__: when a woman in one marriage prefers a man in a different marriage to her current husband, and the man also prefers that woman over his own wife → infidelity, marriage falling apart, spiraling out of control as the abandoned spouses seek new mates | __Defining instability for this problem__: when a woman in one marriage prefers a man in a different marriage to her current husband, and the man also prefers that woman over his own wife → infidelity, marriage falling apart, spiraling out of control as the abandoned spouses seek new mates | ||
| Line 13: | Line 13: | ||
| __Defining stable for this problem__: A matching set is stable if | __Defining stable for this problem__: A matching set is stable if | ||
| - It is perfect (as defined above) | - It is perfect (as defined above) | ||
| - | - There is no instability (as definwd | + | - There is no instability (as defined |
| **__How the algorithm works:__** | **__How the algorithm works:__** | ||
| Line 39: | Line 39: | ||
| * See pg 11 for proof by contradiction | * See pg 11 for proof by contradiction | ||
| - | ===== 2.1-2.2 ===== | ||
| - | __Discrete__: | ||
| - | |||
| - | **An algorithm is __efficient__ if it has a polynomial running time** | ||
| - | |||
| - | Runtimes in order from slowest to fastest: | ||
| - | * n | ||
| - | * nlog2n | ||
| - | * n^2 | ||
| - | * n^3 | ||
| - | * 1.5^n | ||
| - | * 2^n | ||
| - | * n! | ||
| - | |||
| - | **__Asymptotic Defs__** | ||
| - | |||
| - | __Asymptotic Upper Bounds__: We say T(n) = O(f(n)) | ||
| - | |||
| - | __Asymptotic Lower Bounds__: we say T(n) is Ω(f(n)) (“T is asymptotically lower bounded by f”) in the case opposite of the asymptotic lower bounds (f(n) < T(n) forever after a certain point). | ||
| - | |||
| - | __Asymptotically Tight Bounds__: if T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)) | ||
