This is an old revision of the document!
Chapter 1.1 Summary:
Stable matching problem
Self-enforcing recruitment/matching process
Outcome is stable if E prefers ever one of its accepted applicants to A; or
A prefers her current situation over working for employer E.
Chapter 2.1 Computational Tractability:
Important to think about how resource requirements – the amount of time and space an algorithm will use- will scale with increasing input size
Algorithms should be fundamentally discrete.
An algorithm is efficient if, when implemented, it runs quickly on real input instances
→
Leaves out test case size, and bad algorithms can pass this test and so can good algorithms coded poorly
An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.
-too vague
→
An algorithm is efficient if it has a polynomial running time
Helps to see that there might not be an efficient algorithm for a particular problem
Chapter 2.2 Asymptotic Order of Growth:
O() expressed upper bound, not the exact growth rate
Upper, Lower, and limit bounds
Transitivity, A upper bound = b upper bound, b upper bound = c upper bound, then c upper bound = a upper bound
Polynomials - asymptotic rate of growth is determined by their “high-order term”
Logarithms- slow growing
Exponentials- fast growing
Every exponential grows faster than every polynomial
