CSE 200, Computability and Complexity, Spring, 2008

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: Kirill Levchenko
Office Hours: Kirill: 200 only, Tuesday 2-3, B260 A; 200/202 Friday 10-11, B260 A

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

Russell will be away Wed. May 14 until Tuesday, May 20. He will not have office hours during that time. Instead, there will be the following special office hours: (Monday, May 12, 1-2 as usual). Tuesday, May 13, 3-4. Thursday, May 22, 3-4.
Announcement:

Note : Kirill's office hours are 1/2 hour late today, Tuesday

Office hours for this week and finals week: Kirill: Friday 10-11, Tuesday 2:30-3:30 (not quite normal) Russell: Friday 12-1 (additional), Monday 1-4 (sign-up), Tuesday 2-5 (sign-up). For individual meetings Monday and Tuesday, sign up outside Russell's office.

Course Handouts
  1. Class Description (ps)
  2. Class Description (pdf)
  3. Calibration Homework due April 7 (ps)
  4. Calibration Homework due April 7 (pdf)
  5. Calibration Homework Answer Key (ps)
  6. Calibration Homework Answer Key (pdf)
  7. Homework 1, due April 28 (ps)
  8. Homework 1, due April 28 (pdf)
  9. Homework 1, answer key (ps)
  10. Homework 1, answer key (pdf)
  11. Homework 2, due May 28 (ps)
  12. Homework 2, due May 28 (pdf)
  13. Homework 2, answer key (ps)
  14. Homework 2, answer key (pdf)
  15. Homework 3, due June 2 (ps)
  16. Homework 3, due June 2 (pdf)
  17. Take home final, due June 11 at 6 AM (ps)
  18. Take home final, due June 11 at 6 AM (pdf)
Last year, 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 are often Chris's way of presenting things, not Russell's.
  1. First Lecture Notes: 1 tape vs multi-tape TMs.
  2. Lecture Notes: RAMs and circuits
  3. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT
  4. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  5. Recommended additional reading related to last three lectures: Chapter 7 and Chapter 9.