CSE 200, Computability and Complexity, Spring, 2007

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 5:00-6:20, EBU3b 2154
TA: Chris Calabro, ccalabro@cs.ucsd.edu
Office Hours: Chris: Thursday, 5-6, EBU3b B240a

Russell: Tuesday, 1-2, Wed. 3-4. Room: either 4248 (try first) or we'll move to a room TBA when it gets crowded.

Announcements: Russell will have special office hours for the final, Thursday, 3-4:30 and Friday 2-3:30, but no office hours the week of FCRC. FAQ for final: In the last problem, $A$ is polynomial-time in the size of its input, which is $C$. So if $C$ has $g$ gates, $A$ is allowed to run for poly(g) steps, regardless of how large or small the number of inputs to the circuit is. (Of course, since each input is also a gate, the number of inputs cannot be larger than $g$.)
Course Handouts
  1. Class Description
  2. Calibration Homework (typo corrected, April 4), due April 11
  3. Calibration Homework answer key
  4. Homework 1 due April 30
  5. Homework 1 answer key
  6. Homework 1 answer key (pdf)
  7. Homework 2 due May 14
  8. Homework 2 due May 14 (pdf)
  9. Homework 2 answer key
  10. Homework 2 answer key (pdf)
  11. Homework 3 due May 23
  12. Homework 3 due May 23 (pdf)
  13. Homework 3 answer key
  14. Homework 3 answer key (pdf)
  15. Homework 4 due June 6 Note: the last line was vestigial from last year's assignment. This is now modified to fix that.
  16. Homework 4 due June 6 (pdf) Note: the last line was vestigial from last year's assignment. This is now modified to fix that.
  17. Homework 4 answer key
  18. Homework 4 answer key (pdf)
  19. Take home final (ps)
  21. Take home final (pdf)
  22. These lecture notes are by Chris Calabro from Fall, 2006, and are often Chris's way of presenting things not Russell's. He may add new topics for this quarter.
  23. First Lecture Notes: 1 tape vs multi-tape TMs.
  24. Lecture Notes: RAMs and circuits
  25. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT
  26. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  27. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  28. Recommended additional reading related to last three lectures: Chapter 7 and Chapter 9.