Instructor:
Swastik Kopparty (__swastik.kopparty@gmail.com__)

Class
Time and Place: Tuesdays and Thursdays 3:20pm – 4:40pm, in TIL 116 (Tillett Hall,
Livingston Campus).

Office
Hours: Thursday 11 am-12 noon (Hill 432)

Textbook:
Introduction to the Theory of Computation, by Sipser, Third Edition

TA:
Aditi Dudeja (ad1222@rutgers.edu)

TA
Office Hours: Tuesday 10am-11am, Friday 10am-11am (Hill 202)

There
will be HW every 1-1.5 weeks.

Grading:
HW 35%, Midterm 1: 30%, Midterm 2: 30%, Participation: 5%

__Homework__

·
Homework 0 (finish
by Jan 18) (Click here for CHAPTER 0)

o Read Chapter 0. Look up whatever you need to in order
to understand it. If you can’t understand Chapter 0, this course will be too difficult
for you.

o Solve the following problems from Chapter 0 and check
your answers with some random classmates

§ 0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.10, 0.12, and
(slightly tricky) 0.13

o Do not turn anything in.

·
Homework 1 (NOW
DUE Tuesday, Jan 30 in class)

o Problems from the book:

§ 1.6.a, 1.6.b, 1.6.g, 1.6.i, 1.7.e, 1.8.a, 1.9.a,
1.10.a, 1.31, 1.34, 1.41

·
Homework 2 (Due
Tuesday, Feb 6 in class)

o Problems from the book:

§ 1.16b, 1.17a, 1.20e, 1.21b, 1.29b, 1.37, 1.43, 1.70,
1.71

·
Homework 3 (Due
Tuesday, Feb 13 in class)

o Problems from the book:

§ 2.1, 2.4c, 2.4e, 2.9, 2.10, 2.6b, 2.13, 2.14, 2.16,
2.26, 2.30a, 2.31

·
Homework 4 (Due
Thursday, March 1 in class)

o Problems from the book:

§ 3.6, 3.8b, 3.11, 3.15b, 3.15e, 3.16b, 3.16d, 3.18,
4.5, 4.7, 4.8, 4.18, 4.20

·
Homework 5 (Due
Thursday, April 12 in class)

o Problems from the book:

§ 6.14, 6.19, 7.5, 7.6, 7.7, 7.13, 7.14, 7.9, 7.17,
7.18, 7.20, 7.22, 7.34, 7.35, 7.39

§ bonus problems (for extra credit): 6.16, 7.26, 7.27,
7.28, 7.29, 7.30, 7.31

__Lecture Schedule__

·
January 16: course
overview, finite automata, regular languages

·
January 18:
nondeterministic finite automata

·
January 23: NFAs
and regular operations

·
January 25:
regular expressions, the pumping lemma

·
January 30:
applications of the pumping lemma

·
February 1:
context free grammars (notes for CYK parsing algorithm
– from Hopcroft-Motwani,-Ullman)

·
February 6: push
down automata

·
February 8:
pumping lemma for context free languages

·
February 13:
Turing machines, Church-Turing thesis

·
February 15:
universal Turing machine, countability, existence of non-Turing-recognizable
sets

·
February 20:
undecidability via diagonalization

·
February 22:
undecidability (and non-Turing-recognizability) via reductions

·
February 27:
MIDTERM 1

·
March 1: oracles,
Turing reductions

·
March 6:
compression, Kolmogorov complexity

·
March 8:
Kolmogorov complexity (continued)

·
March 13: NO CLASS

·
March 15: NO CLASS

·
March 20: time
complexity, space complexity

·
March 22: the time
hierarchy theorem, NP

·
March 27: some
problems in NP

·
March 29: NP
completeness

·
April 3: NP
completeness

·
April 5: NP
completeness

·
April 10: MIDTERM
2

·
April 12: L, NL,
Savitch’s theorem

·
April 17: the
polynomial time hierarchy

·
April 19: randomized
algorithms, RP, BPP

·
April 24: introduction
to cryptography

·
April 26: review