CS388R: Randomized Algorithms (Fall 2008)

Syllabus: Syllabus
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: TTh 2-3, or by appointment.
TA: Raghu Meka
Email: raghu@cs.utexas.edu
Office: TAY 3.108
Phone: 471-9520
Office Hours: M 3-4.
Useful References: Review Sheet from my Combinatorics and Graph Theory course.
Errata for the text. Doesn't include error in Problem 7.3.
P. Indyk's survey Algorithmic Aspects of Geometric Embeddings
S. Dasgupta and A. Gupta, An Elementary Proof of a Theorem of Johnson and Lindenstrauss
D. Achlioptas, Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins
M. Goemans, Lecture Notes on Linear Programming
M. Goemans and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming
D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs (online book)
My Pseudorandomness Lecture Notes (Lectures 11, 12, and 16 cover expanders, eigenvalues, mixing times, and cover times of random walks)
S. Hoory, N. Linial, and A. Wigderson's survey Expander Graphs and Their Applications
N. Nisan and A. Wigderson, Hardness vs. Randomness
Problem Sets: Problem Set #1   Solutions
Problem Set #2   Solutions
Problem Set #3   Solutions
Problem Set #4   Solutions
Problem Set #5   Solutions
Problem Set #6   Solutions
Problem Set #7   Solutions
Problem Set #8   Solutions
Exams: 2008 Midterm   Solutions
2006 Midterm   Solutions
The final exam will be cumulative and held on Friday, December 12, from 9am - noon in the regular classroom. No make-up exams will be given, so please plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper, with writing on both sides; for the final you may bring two such sheets. No calculators are allowed (they won't be necessary).

Last modified: December 9, 2008