MCS 441 - Theory of Computation I
University of Illinois - Chicago
Spring 2013

This course will cover basic computability and complexity theory. We will examine the central questions ''What is computable in principle?" and ''What is efficiently computable?" Covered material will likely include, but not be limited to: automata, regular languages, and nondeterminism; context-free languages and pushdown automata; Turing machines and the Church-Turing thesis; decidability and the halting problem; time complexity, P vs. NP, the Cook-Levin theorem, and reductions; and time permitting, PSPACE, L, NL, or other advanced topics.

Basic Information

Syllabus: pdf
Time and Location: M-W-F 12:00-12:50pm, Taft Hall (TH) 320
Instructor Contact Information: Lev Reyzin, SEO 713, (312)-413-9576,
Textbook: M. Sipser, Introduction to the Theory of Computation, 3rd edition
Office Hours: T-F 2:00-3:00pm, or by appointment

Exam Dates

Midterm 1: 2/20/13, during classtime
Midterm 2: 3/15/13, during classtime
Final Exam: 5/7/2013, 8-10am

Problem Sets

Problem Set 1: pdf, due 1/23/13
Problem Set 2: pdf, due 2/1/13
Problem Set 3: pdf, due 2/8/13
Problem Set 4: pdf, due 2/18/13
Problem Set 5: pdf, due 2/27/13
Problem Set 6: pdf, due 3/8/13 (Turing's paper)
Problem Set 7: pdf, due 3/13/13 (Aaronson's article)
Problem Set 8: pdf, due 4/5/13
Problem Set 9: pdf, due 4/19/13
Problem Set 10: pdf, due 5/1/13

Lectures and Readings

Note: lectures will have material not covered in the readings.

Lecture 1 (1/14/13)
covered material: intro to the course, overview of prerequisite material
reading: chapter 0

Lecture 2 (1/16/13)
covered material: intro to DFAs: examples, their formal description, defining computation
reading: begin chapter 1.1
other: problem set 1 given out

Lecture 3 (1/18/13)
covered material: designing DFAs, intro to regular operations
reading: continue chapter 1.1

Lecture 4 (1/23/13)
covered material: regular languages closed under union and intersection, intro to NFAs
reading: finish chapter 1.1, begin chapter 1.2

Lecture 5 (1/25/13)
covered material: NFA and DFA equivalence, regular languages closed under concatenation and star
reading: finish chapter 1.2
other: problem set 2 given out

Lecture 6 (1/28/13)
covered material: introduction to regular expressions, converting regular expressions to NFAs
reading: begin chapter 1.3

Lecture 7 (1/30/13)
covered material: defining GNFAs, converting DFAs to GNFAs
reading: finish chapter 1.3

Lecture 8 (2/1/13)
covered material: converting GNFAs to REs, introduction to non-regular languages
reading: begin chapter 1.4
other: problem set 3 given out

Lecture 9 (2/4/13)
covered material: enumerability of regular languages, diagonalization on all languages, pumping lemma
reading: continue chapter 1.4

Lecture 10 (2/6/13)
covered material: pumping lemma proof, applying it to show languages are not regular
reading: finish chapter 1

Lecture 11 (2/8/13)
covered material: intro to CFGs and CFLs, their formal definition, that RLs are a proper subset of CFLs
reading: begin chapter 2.1
other: problem set 4 given out, first midterm announced to take place on 2/20/13 in class

Lecture 12 (2/11/13)
covered material: ambiguous grammars, inherently ambiguous languages, CNF, testing CFG membership
reading: finish chapter 2.1

Lecture 13 (2/13/13)
covered material: defining PDAs, an example, discussion of nondeterminism in pushdown automata
reading: begin chapter 2.2

Lecture 14 (2/15/13)
covered material: designing and interpreting PDAs
reading: continue chapter 2.2

Lecture 15 (2/18/13)
covered material: CFG and PDA equivalence, intro to pumping lemma for CFLs
reading: finish chapter 2.2, begin chapter 2.3
other: midterm Wednesday!

Lecture 16 (2/20/13)
midterm exam 1, no lecture
other: problem set 5 given out

Lecture 17 (2/22/13)
covered material: proof of pumping lemma for CFLs, applications to show languages are not context-free
reading: finish chapter 2.3

Lecture 18 (2/25/13)
covered material: closure properties for CFLs, introduction to Turing Machines
reading: begin chapter 3.1

Lecture 19 (2/27/13)
covered material: designing TMs, state diagrams of TMs, defining decidable and recognizable languages
reading: finish chapter 3.1

Lecture 20 (3/1/2013)
covered material multi-tape TMs, nondeterministic TMs, Enumerators, and equivalence to TMs
reading: chapter 3.2
other: problem set 6 given out

Lecture 21 (3/4/2013)
covered material: Hilbert's 10th problem, Church-Turing thesis, some closure properties of decidable languages
reading: chapter 3.3

Lecture 22 (3/6/2013)
covered material: ADFA, ANFA, AREX, EDFA, EQDFA, ACFG, ECFL are all decidable, HALTTM is recognizable
reading: chapter 4.1
other: by plurality vote: second midterm announced to take place on 3/15/13 in class

Lecture 23 (3/8/2013)
covered material: HALTTM, ATM not decidable, co-recognizabile languages, HALTTM not recognizable
reading: chapter 4.2
other: problem set 7 given out

Lecture 24 (3/11/2013)
covered material: introduction to reductions, ETM and EQTM not decidable
reading: begin chapter 5.1

Lecture 25 (3/13/2013)
covered material: many-to-one reductions, EQTM not recognizable or co-recognizable
reading: chapter 5.3
other: exam Friday!

Lecture 26 (3/15/2013)
midterm exam 2, no lecture

Lecture 27 (3/18/2013)
covered material: Rice's theorem, the Post Correspondence Problem
reading: skim chapter 5.2

Lecture 28 (3/20/2013)
covered material: Universal TMs, Turing reductions, introduction to Kolmogorov complexity
reading: chapter 6.3, begin chapter 6.4

Lecture 29 (3/22/2013)
covered material: bounds on Kolmogorov complexity K(x), incomputability of K(x)
reading: finish chapter 6.4
other: problem set 8 given out

Lecture 30 (4/1/2013)
covered material: introduction to time complexity, the class TIME(t(n)), multi-tape vs single-taple TM running times
reading: begin chapter 7.1

Lecture 31 (4/3/2013)
covered material: the class P, the complexity-theoretic Church-Turing thesis, representation issues
reading: finish chapter 7.1, begin chapter 7.2

Lecture 32 (4/5/2013)
covered material: RELPRIME in P, the classes NTIME(t(n)), NP, and EXPTIME, verifiers, certificates, P vs. NP
reading: finish chapter 7.2, begin chapter 7.3

Lecture 33 (4/8/2013)
covered material: examples of problems in NP (CLIQUE, SUBSET-SUM), the class coNP
reading: finish chapter 7.3

Lecture 34 (4/10/2013)
covered material: polynomial time many-to-one reductions, NP-Completeness, 3-SAT
reading: begin chapter 7.4

Lecture 35 (4/12/2013)
covered material: proof of the Cook-Levin theorem, that SAT and 3-SAT are NP-Complete
reading: finish chapter 7.4
other: problem set 9 given out

Lecture 36 (4/15/2013)
covered material: 3-COLORING, INDEPENDENT-SET, VERTEX-COVER are NP-Complete, ATM NP-Hard
reading: read chapter 7.5

Lecture 37 (4/17/2013)
covered material: the classes SPACE(f(n)), NSPACE(f(n)), PSPACE, NPSPACE, and that P ⊆ NP ⊆ PSPACE
reading: begin chapter 8.1

Lecture 38 (4/19/2013)
covered material: ALLNFA in PSPACE, PSPACE ⊆ EXPTIME, the yieldability problem
reading: finish chapter 8.1, begin chapter 8.2

Lecture 39 (4/22/2013)
covered material: Savich's Theorem (PSPACE = NPSPACE)
reading: finish chapter 8.2

Lecture 40 (4/24/2013)
covered material: introduction to PSPACE-Completeness, TQBF, FORMULA-GAME
reading: begin chapter 8.3
other: problem set 10 given out

Lecture 41 (4/26/2013)
covered material: GENERALIZED-GEOGRAPHY is PSPACE-Complete, minimax trees
reading: finish chapter 8.3

Lecture 42 (4/29/2013)
covered material: Σi-SAT, Πi-SAT, and the Polynomial Hierarchy, and defining L and NL
reading: begin chapter 8.4

Lecture 43 (5/1/2013)
coverd material: PATH is NL-Complete, logspace reductions, and heierarchy theorems
reading: read chapter 8.5, skim chapters 8.6 and 9.1