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:** Tu. Th. 3:30-4:50, WLH 2111

**TA**: Jiawei Gao

**Russell's Office Hours:** Monday,12:10-1:50; Wed., Friday, 1-2:20.
4248 CSE, or 4258 if it is crowded

**Jiawei's Office Hours:** Tu, Th: 1:20-3:20, B260A CSE

Announcements:
Russell's office hours Wed. March 16 (aka, day the exam is due), will be moved
to 12:00-1:00.

Course Handouts

- Class Description (pdf)
- Homework 1 due January 12. See class description for guidelines
- Homework 1 answer key
- Homework 2 due January 26.
- Homework 2 answer key
- Homework 3 due Feb. 16. NOTE CHANGE
- Homework 3 answer key
- Homework 4 due March 1
- Homework 4 answer key
- Homework 5 due March 10
- Final exam, due March 16

- 1-tape vs mmulti-tape TMs
- [Updated 02/09/16][Updated this year] 1 tape vs multi-tape TMs.
- RAMs and circuits
- Simulating TMs by circuits
- Diagonalization, non-computable sets, and the time hierarchy theorem
- [Updated this year] Diagonalization
- [New this year] Reductions
- Undecideability of tiling problems
- [Updated this year] Undecideability of tiling problems
- NP and NP-completeness, part 1
- [Updated this year] The class NP
- [Updated this year] NP-completeness
- Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
- NP-completeness of combinatorial problems
- [Updated this year] NP-complete problems (I)
- [Updated this year] NP-complete problems (II)
- [New this year]Coping with NP-completeness, Polynomial hierarchy
- Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
- [Updated this year]Polynomial hierarchy
- Space complexity, part 1 (pdf)
- Space complexity, part 2 (pdf)
- [Updated this year]Space complexity
- [Updated this year]Space complexity: NL=co-NL
- Randomized algorithms and Probabilistic proofs (pdf)
- [Updated this year]Probabilistic Algorithms: polynomial identity testing
- [Updated this year]Probabilistic Algorithms: BPP