| Syllabus: | Syllabus. |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 Office Hours: WF 2:30-3:30, or by appointment. |
| TA: | Xin Li Email: lixints@cs.utexas.edu Office (for office hours): ENS 31NQ Desk #1 Office (for all other purposes): TAY 3.108 Phone: 471-9520 Office Hours: M 2-3 |
| Useful References: |
Review Sheet 2005 version of course N. Alon and J. H. Spencer, "The Probabilistic Method" ( ebook available with UT EID) L. Babai and P. Frankl, "Linear Algebra Methods in Combinatorics, with applications to geometry and computer science" For students wishing to review probability, I recommend the first two chapters (except Section 2.6) of R. Meester, A Natural Introduction to Probability Theory. For general problem-solving and proof techniques, I recommend Chapters 2 and 3 of P. Zeitz, The Art and Craft of Problem Solving, and for basic counting I recommend Sections 6.1 and 6.2 of the same book. Manuel Blum's lecture notes contain a counting argument showing the existence of hard functions. Linear algebra reference. Madhu Sudan's lecture notes on coding theory. My Pseudorandomness lecture notes include three lectures on coding theory. My talk on codes in theoretical computer science. Nisan-Wigderson Pseudorandom Generator Hoory-Linial-Wigderson survey of expander graphs Lecture notes on expander graphs and random walks on expanders from my Pseudorandomness class. Lecture notes on extractors and their applications from my Pseudorandomness class. For more on extractors, see Nisan's survey and Shaltiel's survey. My paper giving a simple extractor construction, and an application to inapproximability. |
| 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: |
2005 midterm
Solutions
The final exam will be cumulative and held on Monday, December 17 from 9am-noon in ENS 109. No make-up exams will be given, so plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides); for the final you may bring two such sheets. No calculators are allowed (they won't be necessary). |