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