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

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

Exam Dates

Midterm 1: 12:00-12:50 p.m. Friday, February 26 (in class)
Midterm 2: 12:00-12:50 p.m. Friday, April 1 (in class)
Final Exam: 8:00-10:00 a.m. Tuesday, May 3

Problem Sets

problem set 1 (pdf), due 2/1/16
problem set 2 (pdf), due 2/12/16
problem set 3 (pdf), due 2/24/16
problem set 4 (pdf), due 3/14/16 3/16/16 (Turing's paper and Aaronson's article)
problem set 5 (pdf), due 3/27/16 (Nielsen's article)

Lectures and Readings

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

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

Lecture 2 (1/13/16)
covered material: DFA examples, their formal description, defining computation, designing DFAs
reading: begin chapter 1.1

Lecture 3 (1/15/16)
covered material: the regular operations, closure of regular languages under union, intro to nondeterminism
reading: finish chapter 1.1

Lecture 4 (1/20/16)
covered material: equivalence of NFAs and DFAs, closure of RLs under concatenation and star
reading: chapter 1.2

Lecture 5 (1/22/16)
covered material: more NFA examples, intro to regular expressions
reading: begin chapter 1.3
other: problem set 1 assigned

Lecture 6 (1/25/16)
covered material: regular expressions are equivalent to regular languages, GNFAs
reading: finish chapter 1.3

Lecture 7 (1/27/16)
covered material: nonregular languages and the pumping lemma
reading: chapter 1.4

Lecture 8 (1/29/16)
covered material: intro to CFGs and CFLs, their formal definition, some examples
reading: begin chapter 2.1
other: this was a guest lecture by Prof. György Turán

Lecture 9 (2/1/16)
covered material: regular languages are a proper subset of context-free languages, grammar and launguage ambiguity
reading: continue chapter 2.1

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

Lecture 11 (2/5/16)
covered material: intro to PDAs, nondeterminism in PDAs
reading: begin chapter 2.2
other: this was a guest lecture by Prof. György Turán

Lecture 12 (2/8/16)
covered material formal definition of PDAs, converting CFGs to PDAs
other: continue chapter 2.2

Lecture 13 (2/10/16)
covered material: converting PDAs to CFGs, pumping lemma for CFLs and its proof
reading: finish chapter 2.2, begin chapter 2.3

Lecture 14 (2/12/16)
covered material: more on pumping lemma for CFL and examples
reading: finish chapter 2.3

Lecture 15 (2/15/16)
covered material: intro to TMs, their formal description and state diagrams
reading: begin chapter 3.1
other: problem set 3 assigned

Lecture 16 (2/17/16)
covered material: TM examples, decidable and recognizable languages
reading: finish chapter 3.1

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

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

Lecture 19 (2/24/16)
covered material: midterm 1 review
other: a reminder that midterm 1 is on Friday

Lecture 20 (2/26/16)
midterm exam 1: no lecture

Lecture 21 (2/29/16)
covered material: encodings, ADFA, ANFA, AREX, EDFA, EQDFA are all decidable
reading: begin chapter 4.1

Lecture 22 (3/2/16)
covered material: ACFG and ECFG are decidable, introduction to undecidability, diagonalization
reading: finish chapter 4.1, begin chapter 4.2

Lecture 23 (3/4/16)
covered material: ATM and HALTTM are not decidable, co-regonizable languages
reading:finish chapter 4.2

Lecture 24 (3/7/16)
covered material: using undecidable problems to show new problems undecidable, e.g. ETM, EQTM, REGULARTM
reading: first half of chapter 5.1
other: problem set 4 assigned

Lecture 25 (3/9/16)
covered material: computable functions and mapping reductions
reading: begin chapter 5.3

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

Lecture 27 (3/14/16)
covered material: existance of incompressible strings, incomputability of Kolmogorov complexity, the busy beaver function
reading: finish chapter 6.4

Lecture 28 (3/16/16)
covered material: discussion of incompleteness, the Universal TM, EQTM is neither recognizable nor co-recognizable
reading: finish chapter 5.3
optional reading: chapter 6.2

Lecture 29 (3/18/16)
covered material: oracle Turing Machines and Turing reductions
reading: chapter 6.3

Lecture 30 (3/28/16)
covered material: introduction to time complexity. asymptotic analysis and notation, the classes TIME(t(n)) and NTIME(t(n))
reading: chapter 7.1

Lecture 31 (3/30/16)
covered material: midterm 2 review
other: a reminder that midterm 2 is on Friday

Lecture 32 (4/1/16)
midterm exam 2: no lecture

Lecture 33 (4/4/16)
covered material: the complexity theoretic Church-Turing thesis, the classes P and NP
reading: chapter 7.2

Lecture 34 (4/6/16)
covered material: polynomial time verifiability and certificates, polynomial time verifier for HAMPATH
reading: begin chapter 7.3

Lecture 35 (4/8/16)
covered material: equivalence of NP and deterministic verifiers, the CLIQUE problem
reading: finish chapter 7.3

Lecture 36 (4/11/16)
covered material: EXPTIME, polynomial time reductions, 3SAT, NP-Completeness
reading: begin chapter 7.4

Lecture 37 (4/13/16)
covered material: gadget reduction from 3SAT to CLIQUE, begin Cook-Levin theorem
reading: continue chapter 7.4

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

Lecture 39 (4/18/16)
covered material: reduction from 3SAT to HAMPATH, intro to space complexity, the classes SPACE and NSPACE
reading: chapter 7.5, intro to chapter 8
other: problem set 5 assigned

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

Lecture 41 (4/22/16)
covered material: TQBF, FORMULA-GAME, generalized geography (GG), polynomial heirarchy
reading: chapter 8.3, lecture notes from Cornell

Lecture 42 (4/25/16)
covered material: L, NL, logspace transducers, and NL-Completeness and the language PATH
reading: chapter 8.4, chapter 8.5

Lecture 43 (4/27/16)
covered material: time and space heirarchy theorems and their implications, EXPSPACE, short discussiong of co-NL
reading: chapter 9.1
optional reading: chapter 8.6

Lecture 44 (4/29/16)
covered material: final exam review
other: a reminder that the final is on Tuesday