In this class we will be learning about the mathematical science
behind Computer Science -- the study of what things can and cannot be
. 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
, 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
: 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 100Recitation
: Monday 4:30-5:30 DRLB A1Prerequisites
: 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 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.
- Problem Set 5. Due November 17 by 11:59am.
- Problem Set 6. Due December 6 by 11:59am.
- 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
- NO CLASS (10/27)
- Lecture 16
- Lecture 17
- Lecture 18
- NO CLASS (11/10)
- Lecture 19
- Lecture 20
- Lecture 21
- Lecture 22
- Lecture 23
- Lecture 24 --- Last class!
- FINAL EXAM: Tuesday, December 20, 12:00-2:00. Meyerson Hall B1.