| Syllabus: | Syllabus. |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: TAY 3.134 Office Hours: TTh 3:30-4:30 |
| TA: | Anindya Patthak Email: anindya@cs.utexas.edu Phone: 471-9513 Office (for office hours): ESB 229, Desk 1 Office (for all other purposes): TAY 3.104B Office Hour: W 2-3 |
| Text: | Michael Sipser, Introduction to the Theory of Computation |
| Useful Pointers: | Manuel Blum's lecture notes (pages 3 and 4) contain a counting argument showing the existence of functions with exponential circuit complexity. Note that he allows arbitrary gates on 2 inputs, whereas we allow only AND, OR, and NOT. |
| 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 #1
Solutions
Midterm #2 Solutions The final exam will be held on Tuesday, May 15, from 9am - noon. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). |