Home Bookmarks Papers Blog

598: Randomized Algorithms

Lectures

      1. [PDF] 8/25/05 - Quick Sort ( O(n log n) in expectation) and BSP.
        - the BSP part is described better in the book.
      2. [PDF] 8/30/05 - MinCut
      3. [PDF] 9/06/05 - Complexity, # min changes, and closest pair.
      4. [PDF] 9/08/05 - Occupancy problem.
      5. [PDF] 9/13/05 - Coupon collector II, and randomized selection.
      6. [PDF] 9/15/05 - Two Point Sampling, Chernoff's Inequality, and QuickSort Revisited.
      7. [PDF] 9/20/05 - Chernoff's Inequality, routing in the hypercube, and faraway strings.
      8. [PDF] - Marginales
      9. [PDF] - Marginales II
      10. [PDF] - Probabilistic method.
      11. [PDF] - Probabilistic method II.
      12. [PDF]- Probabilistic method III.
      13. [PDF] - Probabilistic method IV.
      14. [PDF] - random walk on the integer grid
      15. [PDF] - random walks II
      16. [PDF] - random walks III
      17. [PDF] - random walks IV
      18. [PDF] - Johnson-Lindenstrauss lemma.
      19. [PDF] - Finite metric spaces, partitions.
      20. [PDF] - VC dimension, eps-net, eps-sample.
      21. [PDF] - max cut.
      22. [PDF] - entorpy.

Last modified: Tue Nov 29 15:01:49 CST 2005