Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:emily:home [2014/01/16 21:43] – [Preface, Chapter 1.1, 2.1, and 2.2 Summary] admin | courses:cs211:winter2014:journals:emily:home [2014/04/01 23:04] (current) – [6.1, 6.2, 6.3, 6.4] hardye | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Emily' | ====== Emily' | ||
| - | ===== Preface, Chapter 1.1, 2.1, and 2.2 Summary | + | ===== Journal Entries Listed In Order: |
| - | ==== The Stable Matching Problem - Gale and Shapely | + | ===== Preface, 1.1, 2.1, 2,2 ===== |
| - | * design an admissions/ | + | [[courses:cs211:winter2014: |
| - | * based on matching preference lists | + | |
| - | * if the process is based on self interests, then there will be situations where people will commit and possibly go back on their commitments if a better offer comes along (retract and redirect) | + | |
| - | * question asked: given a list of preferences can we assign applicants to employers so at least one of the following is the case | + | |
| - | * the employer prefers one of its accepted applicants to another | + | |
| - | * the applicant prefers her current situation over working for another employer | + | |
| - | * Formulating the Problem | + | |
| - | * to eliminate complications we assume that each n applicants applies to each n companies and each company accepts one applicant -> we will use the case of devising a system of matching males and females for marriage | + | |
| - | * a matching S is a set of ordered pairs from the sets of M men and W women where each member of M and W appears in at most 1 pair | + | |
| - | * a perfect matching S' is a matching where each member of M and W appears in **exactly** one pair in S' | + | |
| - | * there is neither single hood nor polygamy | + | |
| - | * each M and W creates a preference list where they rank the opposite gender | + | |
| - | * **instability** a pair is unstable if one of the pair prefers another male/female | + | |
| - | * it is possible for an instance to have more than one stable matching | + | |
| - | * Designing the Algorithm | + | |
| - | * women will naturally accept an engagement even if she prefers another male | + | |
| - | * if a free m proposes to a woman w who is already engaged to m', she may accept the proposal from m if he ranks higher than m' on her preference list | + | |
| - | * the algorithm will stop when everyone is engaged. | + | |
| - | * Analyzing the Algorithm | + | |
| - | * from the view of the woman | + | |
| - | * once w is engaged she will remain engaged to a sequence of men who get higher on her ranking list as they propose | + | |
| - | * from the view of a man | + | |
| - | * as m proposes, the sequence of women he proposes to gets lower on his list of ranked women | + | |
| - | * **maximum iterations needed for termination is n^2** | + | |
| - | * PROOF: | + | |
| - | * measure the progress- way of saying each step of the algorithm brings it closer to termination | + | |
| - | * each iteration is a man proposing to a woman he has never proposed to before -> P(t) denotes the set of pairs (m,w) where m has proposed to w by the end of the iteration t | + | |
| - | * there are only n^2 possible pairs of men and women total so P() can only increase n^2 times over the whole algorithm | + | |
| - | * How do we show that the set S at the end of termination is a perfect matching? | + | |
| - | * if a man is free at some point during the algorithm then there is a women he has not proposed to | + | |
| - | * proof by contradiction | + | |
| - | * the set of engaged pairs always forms a perfect matching because the algorithm cannot terminate with a free man | + | |
| - | * How do we prove that the algorithm returns a set of stable matching? | + | |
| - | * we already know that S is a perfect matching so by way of contradiction we prove that S is a stable matching. (if m did not proposed to w then w' must be higher on his preference list) | + | |
| - | * there is an unfairness in the algorithm that favors male preferences over female | + | |
| - | * question do all executions of the algorithm yield the same matching? ... YES! | + | |
| - | * characterize the matching by showing each man gets the "best possible partner" | + | |
| - | * a woman, w, is a //valid partner// for m if there is a stable matching with the pair (m, w) | + | |
| - | * the order of the proposals in the algorithm has no effect on the final outcome | + | |
| - | * PROOF | + | |
| - | * by way of contradiction prove that S' is stable | + | |
| - | * in this stable matching each woman is paired with her //worst// valid partner | + | |
| - | ===== Chapter Two ===== | + | ===== 2.3, 2.4, 2.5 ===== |
| - | ==== Computational Tractability | + | [[courses: |
| + | |||
| + | ===== 3.1, 3.2., 3.3 ===== | ||
| + | |||
| + | [[courses: | ||
| + | |||
| + | ===== 3.4, 3.5, 3.6, 4.1 ===== | ||
| + | [[courses: | ||
| + | |||
| + | ===== 4.2, 4.4, 4.5, 4.6 ===== | ||
| + | |||
| + | [[courses: | ||
| + | |||
| + | ===== 4.7, 4.8, 5.1 ===== | ||
| + | |||
| + | [[courses: | ||
| + | |||
| + | ===== 5.2, 5.3, 5.4 ===== | ||
| + | |||
| + | [[courses: | ||
| + | |||
| + | ===== 6.1, 6.2, 6.3, 6.4 ===== | ||
| + | |||
| + | [[courses: | ||
| + | |||
| + | ===== 7.1, 7.2, 7.5, 7.7 ===== | ||
| + | |||
| + | [[courses: | ||
| - | * our goal is to find efficient algorithms for computational problems! We will focus on running time efficiency but will also note algorithms efficiency in space and memory | ||
| - | * What does efficiency mean? | ||
| - | * //an algorithm is efficient if, when implemented, | ||
| - | * things we are missing: where and how well the algorithm is implemented and a " | ||
| - | * we want efficiency to be platform-independent, | ||
| - | * Worst-Case Running Times | ||
| - | * we analyze the worst-case running time by finding the largest possible running time the algorithm could have over all inputs of a given size | ||
| - | * Why do we use this instead of average case? | ||
| - | * it is hard to determine how to randomly generate input instances | ||
| - | * sets of random input could perform very poorly compared to another set-- tells us more about the random generation instead of the algorithm | ||
| - | * How do we decide if the worst-case analysis running bound is impressive? | ||
| - | * by comparison with brute-force search over the space of possible solutions | ||
| - | * there is a natural brute-force search algorithm that checks every possible solution | ||
| - | * since this takes exponential time it is unacceptable | ||
| - | * we offer a new definition of efficiency | ||
| - | * //an algorithm is efficient if it achieves qualitatively better worst-case performance at an analytical level, than brute-force search// | ||
| - | * vagueness of " | ||
| - | * polynomial time | ||
| - | * we want a good algorithm to have a good scaling property. | ||
| - | * **desirable scaling property** | ||
| - | * if the input size increases by one the number of possibilities incases multiplicitively. We want better than this!! we want when the input size increases by a constant factor, the algorithm should only slow down by some constant factor C. | ||
| - | * we get our third definition of efficiency | ||
| - | * //an algorithm is efficient if it has a polynomial running time// | ||
| - | * our specific definition of efficiency is beneficial because it become negatable | ||
| - | * possible that there is //no// efficient algorithm for a particular problem | ||
| - | Asymptotic Order of Growth | ||
| - | * an algorithm' | ||
| - | * we want to express growth rate of running times in a way that is insensitive to constant factors and low-order terms | ||
| - | * Asymptotic Upper Bounds | ||
| - | * T(n) is O(f(n)) if there are constants x>0 and nº >= 0 such that T(n) <= x(f(n) for n>= nº. T is asymptotically upper-bounded by f. | ||
| - | * Asymptotic Lower Bounds | ||
| - | * we want to show that the upper bound is the best one possible | ||
| - | * T(n) is Ω(f(n)) if there are constants x>0 and nº >= 0 such that T(n) >= x(f(n) for n>= nº. | ||
| - | * Asymptotic Tight Bounds | ||
| - | * T(n) grows exactly like f(n) to within a constant factor | ||
| - | * T(n) = pn^2 + qn + r is O(n^2) and Ω(n^2) | ||
| - | * they characterize the worst-cast performance of an algorithm precisely up to constant factors. | ||
| - | * properties of asymptotic growth rates | ||
| - | * **transitivity** | ||
| - | * if a function f is asymptotically upper-bounded by a function g, and if g is asymptotically upper bounded by function h, then f is asymptotically upper-bounded by h. | ||
| - | * **sums of functions** | ||
| - | * f = O(h) and g = O(h) then f+g = O(h) | ||
| - | * the overall running time is the sum of two functions, results on asymptotic bounds for sums of functions are relevant | ||
| - | Asymptotic Bounds for Some Common Functions | ||
| - | * **Polynomials** | ||
| - | * their asymptotic rate of growth is determined by their term that determines the degree | ||
| - | * algorithms with running-time bounds O(n^2) or O(n^3) are polynomial-time | ||
| - | * O(n log n) is also polynomial time | ||
| - | * **Logarithms** | ||
| - | * **Exponentials** | ||
