CSE 200, Computability and Complexity, Spring, 2010

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: William Matthews
Office Hours: Russell: W, Th, 10-11. Start in 4248, if it gets crowded, we'll move down the corridor. William: M: 5-6, Tu: 4-5. B240 A, EBU3b NOTE NEW TIME MONDAYS!

Announcement: FINAL EXAM available NOW! EXAM WEEK EXTENDED Office Hours: William will have the following exam week office hours: Tuesday, June 1: 3-5, Monday, June 7, 5-7, Tuesday, June 8, 3-5. Russell will have office hours Wed. June 2, 10-12, Thursday, June 3, 10-12, Friday June 4, 10-12. Most meetings concerning the exam will need to be individual, so expect a queue.


Course Handouts
  1. Class Description (ps)
  2. Class Description (pdf)
  3. Calibration Homework due April (ps) Note: Fixed typo in problem 1, Monday after class
  4. Calibration Homework due April 7 (pdf) Note: Fixed typo in problem 1, Monday after class
  5. Calibration Homework Answer Key (ps)
  6. Calibration Homework Answer Key (pdf)
  8. Homework 1, due April 21 (ps)
  9. Homework 1, due April 21 (pdf)
  10. Homework 1 Answer Key (ps)
  11. Homework 1 Answer Key (pdf)
  12. Homework 2, due May 10 (ps)
  13. Homework 2, due May 10 (pdf)
  14. Homework 2 Answer Key (ps)
  15. Homework 2 Answer Key (pdf)
  16. Homework 3, due May 26 (ps)
  17. Homework 3, due May 26 (pdf)
  18. Homework 3 Answer Key (ps)
  19. Homework 3 Answer Key (pdf)
  20. FINAL EXAM (ps)
  21. FINAL EXAM (pdf)
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, 2006, 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.