Handouts
- This is handout 1. It presents the stable marriage problem that was briefly discussed in lecture 2.
- Proof for O(n log n) average-case run time of quicksort:
Average-Case Analysis of Quicksort - Growth Rate of the Binomial Coefficient
- Independent Set and Vertex Cover
- Bounded Approximation Algorithm for Knapsack