Home Bookmarks Papers Blog

Randomized Algorithms and Combinatorial Optimization

CS 497, Spring 2001
3:30 - 4:45 TuTh, 103B3 Engineering Hall
Announcement
Office hours: 17:00-19:00 on Thursday, DCL 2111. Please email if you plan to come.

In class

1. 1/16 Introduction
Course summary (PS, tex)
Notes - Quicksort/BSP (ps, tex)
2.1/18Minimum Cut (1.1), Las Vegas and Monte Carlo algorithms (1.2)
3.1/23 Game Tree Evaluation (2.1), Occupancy problems (3.1) The Markov and Chebyshev Inequalities (3.2)
4.1/25 Markov's inequality, Chebyshev's inequality, Lazy Select (html, ps, latex )
5.1/30 3.4 Two point sampling, 3.6 The coupon collector's problem (3.6.!),
6.2/1 4.1 Chernoff Bound, 4.2 Routing in a parallel computer (html, ps, latex).
7.2/6 4.3 A wiring problem - random rounding
8.2/8 8.2 Random Treaps
9.2/13 8.3 Skip list, 8.4 Hash Tables
10.2/15 8.5 Hashing with O(1) Search Time
11.2/20 PAC Learning and VC Dimension
12.2/22Proving the existance of small epsilon-nets (Alon & Spencer 220-230)
13.2/27Small epsilon-nets - cont' + range-searching data-structures
14.3/19.2 Another variant of quick-sort and Convex hull in the plane. Introduction to Clarkson abstract framework.
15.3/6The exponential decay lemma, clarkson bound on the sum of squared expectations, cuttings, convex-hull in 3d.
16.3/8 Vertical decomposition, Diameter in 3d.
3/13Spring Vacation
3/15Spring Vacation
17.3/20 9.10 Linear programming.
18.3/22 10.1 All pairs shortest path
19.3/27 Witnesses for binary matrix multiplication
20.3/29Faster Min-Cut algorithm
21.4/3Linear time MST
22.4/5Number theory and algebra
23.4/10 Primality testing
24.4/12Sphere in higher dimensions and its concentration of mass
25.4/17The Johnson Lindenstraus lemma
26.4/19The probabilistic method - 5.1, 5.2
27.4/245.3 Expanding graphs, 5.3.1 Probability Amplification
28.4/26 MAX CUT/MAX 2SAT Approximation using Semi-definite programming
29.5/1Approximate NN search and locality sensitive hashing

Homework

1. Due: 2/6 Homework 1 (PS, tex)
2. Due: 2/20 Homework 2 (PS, tex)
3. Due: 3/6 Homework 3 (PS, tex)
4. Due: 3/20 Homework 4 (PS, tex)
5. Due: 4/10 Homework 5 (PS, tex)
6. Due: 5/10 Homework 6 (PS, tex)

Chapter/sections skipped

  1. 2.2, 2.3, 3.6.2, 3.6.3
  2. 4.4 Martingles
I plan to return to some of those later in the course.

Recommended Books

  1. Main book:
    Randomized Algorithms, Motwani and Raghavan.
    Errata.
  2. The probabilistic method, 2ed, Noga Alon and Joel Spencer.

Additional references

  1. The Discrepancy Method, Bernard Chazelle.
  2. Computational Geometry: An Introduction Through Randomized Algorithms, Ketan Mulmuley

Additional resources on the web

  1. Randomized Algorithms, CMU.
  2. Randomized Algorithms, UIUC 1999.
  3. Randoimized Algorithms, Duke.
Last modified: Mon Sep 4 20:23:28 EDT 2000