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. 11-12:20, Pepper Canyon 120

**TA**: Jiawei Gao

**Russell's Office Hours:** Monday, Wed., Friday, 4-5
4248 CSE, or 4258 if it is crowded

**Jiawei's Office Hours:** Tu, Th: 2:00-3:00, 4217 CSE (Waiting for departmental
approval on the room reservation so may change)

Announcements:

Office hours today are postponed until after the party. I'll stay until no one is waiting.
The class description mentioned a project. This is an idea I had but abandonned
as impractical, and forgot to remove, replacing it with an additional homework assignment.
The class description has been updated. DO NOT PANIC! THERE IS NO PROJECT DUE!
Course Handouts

- READ THIS!!!!!!! Class Description (pdf)
- Homework 1 due Sept. 29. See class description for guidelines
- Homework 1 answers. See class description for guidelines
- Homework 2 due Oct. 20
- Homework 2 answer key
- Homework 3 due Nov. 3
- Homework 3 answer key
- Homework 4 due Nov. 22
- Homework 4 answer key
- Homework 5 due Dec. 1
- Take-home final

- [Updated 02/09/16] 1 tape vs multi-tape TMs.
- RAMs and circuits
- Simulating TMs by circuits
- Diagonalization
- Reductions
- Undecideability of tiling problems
- 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