### Overview:

In this class we will be learning about the

mathematical science
behind Computer Science -- the study of what things can and cannot be
computed

even
in principle. We will start by considering a very simple
model of computation -- the finite automaton. This model captures what
can be computed in finite memory, but is already surprisingly powerful
-- as we will see, it is sufficient to capture

regular languages.
This model will give us our first taste of how to reason about the
limitations of computation. We will then study a much more powerful
model of computation, the

Turing
machine, which captures (as far as we know) the power to
compute anything that we can compute by physical means, by any method.
Surprisingly, we will see that this model of computation still has
dramatic, fundamental limitations. Finally, we will consider the
question of computation with limited resources. What can we compute
subject to the constraint that the running time of our algorithm must
be polynomial in the size of the input (the complexity class P)? What
is the power of non-determinism (the complexity class NP)? How can we
cope with these limitations, if they apply to problems that we need to
solve?

### Staff:

Professor:

Aaron Roth
TAs: Matthew Joseph
(Head TA), Eric Kwong, He Chen, Justin Austin, Kelly Tan, Lucy Chai, Meryem Essaidi, Omar Paladines, Paul Lou, Vivek Raj

### Logistics:

Class Time and Location: Tuesday/Thursday 12:00-1:30, Towne 100

Recitation: Monday 4:30-5:30 DRLB A1

Prerequisites: CIS 160 and mathematical maturity.

Course Software: We will be using

Piazza
for questions. Ask and answer questions here (this counts towards your
participation grade). You will turn in assignments and see grades using

GradeScope (Course entry code: 9RDNR9).

Textbook: Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.

### Problem Sets

- Problem Set 1. Due September 8th by 11:59am.
- Problem Set 2. Due September 27 by 11:59am.
- Problem Set 3. Due October 11 by 11:59am.
- Problem Set 4. Due November 1 by 11:59am.

### Lecture Slides:

- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12
- MIDTERM (10/13)
- Lecture 13
- Lecture 14
- Lecture 15 -- Unrecognizable Problems + Reductions (10/25)
- Lecture 16 -- Linear Bounded Automata (10/27)
- Lecture 17 -- Kolmogorov Complexity (11/1)
- Lecture 18 -- Begin time complexity; the class P. (11/3)
- Lecture 19 -- Non-determinisim, and the class NP. (11/8)
- NO CLASS (11/10)
- Lecture 20 -- NP Completeness and reductions. (11/15)
- Lecture 21 -- More reductions; Cook's Theorem. (11/17)
- Lecture 22 -- Approximation Algorithms. (11/22)
- Lecture 23 -- Randomized Algorithms. (11/29)
- Lecture 24 -- Advanced Topics (12/1)
- Lecture 25 -- Advanced Topics (12/6)
- Lecture 26 -- Review -- Last class! (12/8)

### Office Hours: