CSE 200, Computability and Complexity, Spring, 2012

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4248 Computer Science Building, EBU3b
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu


Class Times: M, W 3:30-4:50 , EBU3b 2154
TA: Fjola Bjornsdottir
Office Hours: Russell: T, Th, 2-3:30. Start in 4248, if it gets crowded, we'll move down the corridor. Fjola: M, W, 11-12, B240a

Announcements: Russell will have extra office hours from 3:30-4:30 on Monday.


Course Handouts
  1. Class Description (pdf)
  2. Calibration Homework due April 9 (pdf)
  3. Calibration Homework Answer Key
  4. Homework 1 , due April 30
  5. Homework 1 Answer Key
  6. Homework 2 , due May 14
  7. Homework 2 Answer Key
  8. Homework 3 , due June 4 Some errors have been fixed.
  9. Homework 3 Answer Key, partial. More soon.
  10. Final Exam, Due Wed. June 13 , 11:59 PM
Several years ago, I used ubiquitous presenter. The notes from there are available at: Ubiquitous Presenter, CSE 200, spring 2007 Try logging in as russell, with password turing.
The following lecture notes are by Chris Calabro from Fall, 2008, and by William Matthews. The ones from 2008 may differ from the way we did the same things in class this year.
  1. 1 tape vs multi-tape TMs.
  2. RAMs and circuits
  3. Simulating TMs by circuits
  4. Diagonalization, non-computable sets, and the time hierarchy theorem
  5. Undecideability of tiling problems
  6. NP and NP-completeness, part 1
  7. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
  8. NP-completeness of combinatorial problems
  9. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  10. Space complexity, part 1 (pdf)
  11. Space complexity, part 2 (pdf)
  12. Randomized algorithms and Probabilistic proofs (pdf)
  13. Recommended additional reading related to last three lectures: Chapter 7 and Chapter 9.