CMPSC 464: Introduction to the Theory of Computation
Spring 2016

Some Course Highlights

  • You will learn to reason formally about computation.
  • You will learn to model various computational devices. Specifically, we will study finite automata, push-down automata and Turing machines.
  • You will be able to prove that some computational tasks can and some computational tasks cannot be solved by specified computational devices (including general-purpose computers).
  • You will understand the famous "Is P=NP?" question, which roughly asks whether all problems for which we can quickly verify the solution (problems in NP) can also be solved quickly (are in P). The Clay Mathematics Institute offers a $1 million prize for solving this question.
Complexity classes diagram

Course Staff

Office Phone Email id Office Hours
Prof. Sofya Raskhodnikova IST 343F x3-0608 sxr48 Tu 4-5pm, Th 9:30-10:30am
Jayanthi Thankamani (TA) 338E IST jzt175 W 3:45-5:45pm
Mahdy Zolghadr (TA) 339 IST moz5067 M 11am-1pm

Syllabus, Lecture Notes, Reading

1 Tu, Jan 12 Introduction, finite automata (pdf) Chapters 0-1.1 General Course Information, Collaboration and Honesty Policy, HW0 out; play with JFLAP and Automa Tatutor
2 Th, Jan 14 Operations on languages, regular operations, DFAs and NFAs (pdf) Chapters 1.1-1.2 HW0 due, HW1 out
3 Tu, Jan 19 Equivalence of DFAs and NFAs, closure of the class of regular languages under regular operations (pdf) Chapters 1.1-1.2
4 Th, Jan 21 Closure of the class of regular languages under regular operations. Equivalence of DFAs, NFAs and regular expressions (pdf) Chapters 1.1-1.3 HW1 due, HW2 out
5 Tu, Jan 26 Converting NFAs to regular expressions. Pumping lemma for regular languages (pdf) Chapter 1.4
6 Th, Jan 28 Proving that a language is not regular. Pushdown automata. (pdf) Chapters 1.4,2.2 HW2 due, HW3 out
7 Tu, Feb 2 Context-free grammars. Designing CFGs and PDAs. Equivalence of CFGs and PDAs (pdf) Chapters 2.1-2.2
8 Th, Feb 4 Converting from PDAs to CFGs. Pumping lemma for CFLs (pdf) Chapters 2.2-2.3 HW3 due, HW4 out
9 Tu, Feb 9 Pumping lemma for CFLs. Proving a CFGs generates a given language. (pdf) Chapters 2.1-2.3
10 Th, Feb 11 Review. Turing machines. (pdf) Chapter 3.1 HW4 due; practice midterm is distributed in class
11 Tu, Feb 16 Review and Jeopardy! Chapters 0-3.1 Practice midterm solutions are distributed in class
Wed, Feb 17 Exam 8:15-10:15pm in 101 Chambers
12 Th, Feb 18 Turing machines. Turing machine variants (pdf) Chapters 3.1 -3.2 HW5 out
13 Tu, Feb 23 TM variants. Church-Turing Thesis. (pdf) Chapters 3.2 -4.1
14 Th, Feb 25 Universal TM. Decidable languages. (pdf) Chapter 4.1 HW5 due, HW6 out, graded exams and exam solutions are distributed in class
15 Tu, Mar 1 Decidable languages. Countable and uncountable sets. Diagonalization. (pdf) Chapter 4.2
16 Th, Mar 3 Existence of Turing-unrecognizable languages. A_TM is undecidable. (pdf) Chapters 4.2 HW6 due, HW7 out
17 Tu, Mar 15 Complement of A_TM is unrecognizable. Reductions. (pdf) Chapter 5.1
18 Th, Mar 17 Reductions. Mapping reductions. (pdf) Chapters 5.1,5.3. HW7 due, HW8
19 Tu, Mar 22 Mapping reductions. Computation history method. (pdf) Chapters 5.1, 5.3
20 Th, Mar 24 Review. Computation history method. Recursion theorem. (pdf) Chapter 6.1. HW8 due, practice problems for exam 2 are distributed in class
21 Tu, Mar 29 Review (mostly on the board) (pdf) Chapters 0-2.3,3.1-5.1, 5.3-6.1 Practice midterm 2 solutions are distributed in class
Wed, Mar 30 Exam 8:15-10:15pm in 101 Chambers
22 Th, Mar 31 Finish Recursion Theorem. Time complexity. Review of asymptotic notation. Relationships between deterministic models. (pdf) Chapter 7.1 Exam 2 solutions are distributed in class, HW9 out
23 Tu, Apr 5 Relationships between deterministic and nondeterministic models. Class P. (pdf) Chapters 7.1-7.2
24 Th, Apr 7 Class NP. Nondeterministic complexity classes. P vs. NP question. (pdf) Chapter 7.3 HW9 due, HW10 out, graded exams are distributed in class
25 Tu, Apr 12 Polynomial-time reductions (pdf) Chapters 7.4-7.5
26 Th, Apr 14 Polynomial-time reductions. NP-completeness. Cook-Levin Theorem. (pdf) Chapters 7.4-7.5 HW10 due, HW11 out
27 Tu, Apr 19 Examples of NP-complete problems. (pdf) Chapters 7.4-7.5
28 Th, Apr 21 Space complexity. Savitch's Theorem. PSPACE (pdf) Chapters 8.1-8.2 HW11 due, HW12 and EXTRA CREDIT programming assignment out
29 Tu, Apr 26 PSPACE-completeness. Time and space hierarchy theorems (pdf) Chapters 8.3, 9.1
30 Th, Apr 28 Review (pdf) and ``Jeopardy!'' Chapter 9.1 HW12 due, Final exam preparation handout out
Tu, May 3 Final Exam 2:30-4:20pm in 022 DEIKE

Sofya Raskhodnikova