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

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; Kolmogorov complexity; 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 2:00-2:50pm, Lincoln Hall (TH) 207
Instructor Contact Information: Lev Reyzin, SEO 418, (312)-413-3745,
Textbook: M. Sipser, Introduction to the Theory of Computation, 3rd edition
Office Hours: M 1:00PM-1:50PM, W 11:00AM-11:50AM

Exam Dates

Midterm 1: 2-2:50pm, Friday February 16th (in class)
Midterm 2: 2-2:50pm, Monday April 9th (in class)
Final Exam: 1-3pm, Wednesday May 9th

Problem Sets

problem set 1 due 2/5/18
problem set 2 due 2/14/18
problem set 3 due 3/5/18
problem set 4 due 3/23/18 (Turing's paper and Aaronson's article)
problem set 5 due 5/2/18 (Nielsen's article)

Lectures and Readings

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

Lecture 1 (1/17/18)
covered material: intro to the course, overview of covered material, intro to DFAs
reading: chapter 0

Lecture 2 (1/19/18)
covered material: DFA examples, their formal description, defining computation
reading: begin chapter 1.1

Lecture 3 (1/22/18)
covered material: regular languages, the regular operations
reading: continue chapter 1.1

Lecture 4 (1/24/18)
covered material: closuring of regular languages under union, intro to nondeterminism
reading: finish chapter 1.1, begin chapter 1.2

Lecture 5 (1/26/18)
covered material: equivalence of NFAs and DFAs, closure of RLs under concatenation and star
reading: finish chapter 1.2
other: problem set 1 assigned

Lecture 6 (1/29/18)
covered material: intro to regular expressions
reading: begin chapter 1.3

Lecture 7 (1/31/18)
covered material: regular expressions are equivalent to regular languages, GNFAs
reading: finish chapter 1.3

Lecture 8 (2/2/18)
covered material: nonregular languages and the pumping lemma
reading: chapter 1.4

Lecture 9 (2/5/18)
covered material: intro to CFGs and CFLs, their formal definition, some examples
reading: begin chapter 2.1
other: problem set 2 assigned

Lecture 10 (2/7/18)
covered material: regular languages are a proper subset of context-free languages
reading: continue chapter 2.1
other: midterm 1 announced

Lecture 11 (2/9/18)
covered material: Chomsky normal form, converting a CFG into Chomsky normal form
reading: finish chapter 2.1
other: problem set 2 assigned

Lecture 12 (2/12/18)
covered material: grammar and language ambiguity, intro to PDAs, nondeterminism in PDAs
reading: begin chapter 2.2

Lecture 13 (2/14/18)
covered material: review for midterm 1
other: midterm exam tomorrow!

Lecture 14 (2/16/18)
midterm exam 1: no lecture

Lecture 15 (2/19/18)
covered material: formal definition of PDAs, examples
other: continue chapter 2.2

Lecture 16 (2/21/18)
covered material: converting PDAs to CFGs and CFGs to PDAs
reading: finish chapter 2.2

Lecture 17 (2/23/18)
covered material: pumping lemma for CFL and examples
reading: begin chapter 2.3
other: problem set 3 assigned

Lecture 18 (2/26/18)
covered material: intro to TMs, their formal description and state diagrams, decidable and recognizable languages
reading: begin chapter 3.1
other: problem set 3 assigned

Lecture 19 (2/28/18)
covered material: multi-tape TMs, nondeberministic TMs, and enumerators, and their equivalence to TMs
reading: chapter 3.2

Lecture 20 (3/2/18)
covered material: Church-Turing thesis, intuitive idea of algorithms, encodings, a recognizable language
reading: chapter 3.3

Lecture 21 (3/5/18)
covered material: encodings, ADFA, ANFA, AREX, EDFA, EQDFA are all decidable
reading: chapter 4.1

Lecture 22 (3/7/18)
covered material: diagonalization, introduction to undecidability, ATM is not decidable
reading: chapter 4.2

Lecture 23 (3/9/18)
covered material: HALTTM, ETM, and EQTM are not decidable via reductions
reading: begin first half of chapter 5.1
other: problem set 4 assigned

Lecture 24 (3/12/18)
covered material: REGULARTM not decidable, Rice's theorem
reading: first half of chapter 5.1
optional reading: note on Rice's theorem

Lecture 25 (3/14/18)
covered material: computable functions and mapping reductions, comparing to Turing reductions
reading: chapter 5.3, chapter 6.3

Lecture 26 (3/16/18)
covered material: introduction to Kolmogorov complexity, bounds on Kolmogorov complexity, incomputability of Kolmogorov complexity
reading: chapter 6.4

Lecture 27 (3/19/18)
covered material: Busy Beaver numbers, Universal Turing Machines, discussion of incompleteness
optional reading: chapter 6.2

Lecture 28 (3/21/18)
covered material: introduction to time complexity. asymptotic analysis and notation, the class TIME(t(n))
reading: chapter 7.1

Lecture 29 (3/23/18)
covered material: the class NTIME(t(n)), P, and NP, complexity theoretic Church-Turing thesis,
reading: begin chapter 7.2

Lecture 30 (4/2/18)
covered material: examples of problems in P and NP
reading: finish chapter 7.2

Lecture 31 (4/4/18)
covered material: midterm 2 review
other: a reminder that midterm 2 is on Monday

Lecture 32 (4/6/16)
covered material: polynomial time verifiability and certificates, polynomial time verifiers
reading: begin chapter 7.3

Lecture 33 (4/9/18)
midterm exam 2: no lecture

Lecture 34 (4/11/18)
covered material: more on polynomial time verifiers and certificates, equivalence of NP and deterministic verifiers
reading: begin chapter 7.3

Lecture 35 (4/13/18)
covered material: polynomial time reductions and NP-Completeness
reading: begin chapter 7.4

Lecture 36 (4/16/18)
covered material: gadget reduction from 3SAT to CLIQUE, begin Cook-Levin theorem
reading: continue chapter 7.4
other: problem set 5 assigned

Lecture 37 (4/18/18)
covered material: finish proof of Cook-Levin theorem, the class co-NP, HP-Hardness
reading: finish chapter 7.4

Lecture 38 (4/20/18)
covered material: reduction from 3SAT to HAMPATH, intro to space complexity
reading: chapter 7.5, chapter 8.1

Lecture 39 (4/23/18)
covered material: TQBF, FORMULA-GAME, generalized geography (GG), polynomial heirarchy
reading: chapter 8.3

Lecture 40 (4/25/18)
covered material: Savitch's theorem, PSPACE = NPSPACE, PSPACE-Completeness
reading: chapter 8.2

Lecture 41 (4/27/18)
covered material: logspace transducers, L, EXPTIME
optional reading: chapter 8.4

Lecture 42 (4/30/18)
covered material: time and space heirarchy theorems and their implications, polynomial heirarchy
reading: chapter 9.1, lecture notes from Cornell

Lectures 43 and 44 (5/2/18, 5/4/18)
covered material: review for final exam
other: reminder that the exam is on Wednesday, May 9th