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

- Class Description (ps)
- Class Description (pdf)
- Calibration Homework due April (ps) Note: Fixed typo in problem 1, Monday after class
- Calibration Homework due April 7 (pdf) Note: Fixed typo in problem 1, Monday after class
- Calibration Homework Answer Key (ps)
- Calibration Homework Answer Key (pdf)
- Homework 1, due April 21 (ps)
- Homework 1, due April 21 (pdf)
- Homework 1 Answer Key (ps)
- Homework 1 Answer Key (pdf)
- Homework 2, due May 10 (ps)
- Homework 2, due May 10 (pdf)
- Homework 2 Answer Key (ps)
- Homework 2 Answer Key (pdf)
- Homework 3, due May 26 (ps)
- Homework 3, due May 26 (pdf)
- Homework 3 Answer Key (ps)
- Homework 3 Answer Key (pdf)
- FINAL EXAM (ps)
- FINAL EXAM (pdf)

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 tape vs multi-tape TMs.
- RAMs and circuits
- Simulating TMs by circuits
- Diagonalization, non-computable sets, and the time hierarchy theorem
- Undecideability of tiling problems
- NP and NP-completeness, part 1
- Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
- NP-completeness of combinatorial problems
- Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
- Space complexity, part 1 (pdf)
- Space complexity, part 2 (pdf)
- Randomized algorithms and Probabilistic proofs (pdf)
- Recommended additional reading related to last three lectures: Chapter 7 and Chapter 9.