Home Bookmarks Search (Re)search Papers

Randomized Algorithms

CS 497, Fall 2002
12:30 - 13:45 TuTh, 344 M E BLDG
Office hours: 16:00-17:00 on Thursday, DCL 2111. Please email if you plan to come.
Mailing list
Newsgroup: uiuc.class.cs497shp
Prerequisite: CS373 or CS375.

In class

Thu, 8/29 PS, PDF Introduction - QuickSort, started to speak about BSP.
Tue, 9/3 PS, PDF Minimum Cut (1.1, 10.2)
Thu, 9/5 PS, PDF Las Vegas and Monte Carlo algorithms (1.2), Complexity Classes (1.5)
Tue, 9/10 PS, PDF On the Occupancy problem, Markov and Chebyshev inequalities.
Thu, 9/12 PS, PDF Randomized selection (3.3) and Two-point sampling (3.4).
Tue, 9/17 PS, PDF The Coupon Collector's Problem (3.5, 3.6)
Thu, 9/19 PS, PDF Chernoff Bound (4.1), Routing in a parallel computer (4.2)
Tue, 9/24 PS, PDF Martingles (4.4)
Thu, 9/26 PS, PDF Martingles II(4.4)
Tue, 10/1 PS, PDF The probablistic method I
Thu, 10/3 RA 5.3, 5.3.1 [108-112] The probablistic method II
Tue, 10/8 The probablistic method III - Lovasz Local Lemma
Thu, 10/10 PS, PDF The probablistic method IV - Applications of Lovasz Local Lemma
Tue, 10/15 PS, PDF The Probabilistic method V
Conditional probabilities, and further examples
Thu, 10/17 Random Walks - several examples, RA 6.1
Tue, 10/22 Random Walks - walk on Z3, Markiv Chains (RA 6.2)
Thu, 10/24 Markov Chains
Tue, 10/29 Markov Chains and Electrical Networks (RA 6.4, 6.5)
Thu, 10/31 Markov Chains (RA 6.6, 6.7.1, 6.7.2?).
Tue, 11/5 On algebraic properties of graphs.
From: Introduction for graph theory, 2ed, D. West, pages: 453-464.
Alteratnively: Modern graph theory, B. Bollobas, pages 262-270. (The apologia to this book, is an interesting read.)
Thu, 11/7 Expanders and rapidly mixing random walks (6.7)
Tue, 11/12 Rapid Miaxing 6.8 and started VC Dimension
Thu, 11/14 PS, PDF VC Dimension
Tue, 11/19   CLASS CANCELED - out of town
Thu, 11/21   CLASS CANCELED - out of town
11/26, 11/28   Thanksgiving Vacation
Tue, 12/3   VC Dim II
Thu, 12/5   Discrepancy I
Tue, 12/10   Discrepancy II
Thu, 12/12 Discrepancy III

Homework

hw1 ps, pdf Due: 9/24/02.
hw2 ps, pdf Due: 10/8/02 23:59:59.
hw3 ps, pdf Due: 10/31/02 23:59:59.
hw4 ps, pdf Due: 11/14/02 In class.
hw5 ps, pdf Due: 12/3/02.
hw6 ps, pdf
ZIP with source 		Due: 12/25/02.

Chapter/sections skipped

Recommended Books

  1. Main book:
    Randomized Algorithms, Motwani and Raghavan.
    Errata (local copy).
  2. The probabilistic method, 2ed, Noga Alon and Joel Spencer.
  3. An excellent monograph on the topic of Random Walks and Electric Networks is

    Random Walks and Electric Networks, by Peter G. Doyle and J. Laurie Snell.
    It is avliable for free from: here.

Relevant Papers

  1. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, by Mark Jerrum, Alistair Sinclair, Eric Vigoda.
This is the second time I am teaching this course. Here is the old webpage.

Additional resources on the web

  1. Randomized Algorithms, CMU.
  2. Randomized Algorithms, UIUC 1999.
  3. Randoimized Algorithms, Duke.

Topics not covereD

  1. Embeddings I - Johnson-Lindenstraus Lemma,
  2. Embeddings II - Johnson-Lindenstraus Lemma
  3. Embeddings III - Bourgain Theorem
  4. MAX CUT/MAX 2SAT Approximation using
  5. Semi-definite programming
  6. Last class
Last modified: Mon Dec 16 10:07:36 CST 2002