CS 395T (now called CS 388R): Randomized Algorithms (Fall 2006)

Syllabus: Syllabus
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: W 2-3 and F 3-4, or by appointment.
TA: Anup Rao
Email: arao@cs.utexas.edu
Office (for office hours): ESB 229
Office (for all other purposes): 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.
S. Dasgupta, 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
My Pseudorandomness Lecture Notes
N. Nisan and A. Wigderson, Hardness vs. Randomness
Problem Sets: Problem Set #1
Problem Set #2
Problem Set #3
Problem Set #4
Problem Set #5
Problem Set #6
Problem Set #7
Problem Set #8
Exams: Midterm.
The final exam will be cumulative and held on Thursday, December 14, from 2-5pm in ETC 2.132. You may bring two 8.5x11 inch, handwritten sheets of paper, with writing on both sides. No calculators are allowed (they won't be necessary).

Last modified: December 12, 2006