| 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). |