Skip navigation.


  1. This is handout 1. It presents the stable marriage problem that was briefly discussed in lecture 2.

  2. Proof for O(n log n) average-case run time of quicksort:
    Average-Case Analysis of Quicksort

  3. Growth Rate of the Binomial Coefficient

  4. Independent Set and Vertex Cover

  5. Bounded Approximation Algorithm for Knapsack