CS 332: Introduction to the Theory of Computation
Fall 2019

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 Email id Office Hours
Prof. Sofya Raskhodnikova MCS 112 sofya Tu 3:30-4:30pm,Th 4:30-5:30pm
Ramesh Krishnan Pallavoor (TF) EMA 302 rameshkp W 3:30-5:30

Syllabus, Lecture Notes, Reading

Lec.DateTentative SyllabusReadingHandouts/Homework
1 Tu, Sep 3 Introduction, finite automata, regular languages (pdf) Chapters 0-1.1 General Course Information, Collaboration and Honesty Policy, HW0 out; play with JFLAP and Automata Tutor
2 Th, Sep 5 Operations on languages, regular operations, DFAs and NFAs (pdf) Chapters 1.1-1.2 On Friday: HW0 due, HW1 out
3 Tu, Sep 10 Equivalence of DFAs and NFAs, closure of the class of regular languages under regular operations (pdf) Chapters 1.1-1.2
4 Th, Sep 12 Equivalence of DFAs, NFAs and regular expressions (pdf) Chapters 1.1-1.3 On Friday: HW1 due, HW2 out
5 Tu, Sep 17 Pumping lemma for regular languages. Proving that a language is not regular. (pdf) Chapter 1.4
6 Th, Sep 19 Pushdown automata. Context-free grammars. (pdf) Chapters 2.1-2.2 On Friday: HW2 due, HW3 out
7 Tu, Sep 24 Pumping lemma for CFLs. (pdf) Chapters 2.3
8 Th, Sep 26 Equivalence of CFGs and PDAs. Turing Machines (pdf) Chapters 2.1-2.3, 3.1 HW3 due (on Friday), practice midterm is distributed in class
9 Tu, Oct 1 Review and Jeopardy! Chapters 0-2.3 Practice midterm solutions are distributed in class
10 Th, Oct 3 Midterm Exam 1 Chapters 0-2.3 On Friday: HW4 out
11 Tu, Oct 8 Turing machines. TM variants. (pdf) Chapters 3.1-3.3 Play with TM simulator
12 Th, Oct 10 Church-Turing Thesis. Universal TM. Decidable languages. (pdf) Chapter 3.3-4.1 On Friday: HW4 due, HW5 out
13 Th, Oct 17 Decidable languages. Designing deciders. (pdf) Chapter 4.1 On Friday: HW5 due, HW6 out
14 Tu, Oct 22 Countable and uncountable sets. Diagonalization. Existence of Turing-unrecognizable languages. A_TM is undecidable. (pdf) Chapter 4.2
15 Th, Oct 24 Complement of A_TM is unrecognizable. Reductions. (pdf) Chapters 4.2-5.1 On Friday: HW6 due, HW7 out
16 Tu, Oct 29 Reductions. Mapping reductions. (pdf) Chapters 5.1, 5.3
17 Th, Oct 31 Computation history method. (pdf) Chapters 5.1,5.3, 6.1. HW7 due (on Friday), practice problems for midterm 2 are distributed in class
18 Tu, Nov 5 Review and Jeopardy! Chapters 0-2.3,3.1-5.1, 5.3-6.1 Practice midterm 2 solutions are distributed in class
19 Th, Nov 7 Midterm Exam 2 Chapters 0-2.3,3.1-5.1, 5.3 On Friday: HW8 out
20 Tu, Nov 12 Recursion Theorem. Time complexity. Asymptotic notation. (pdf) Chapters 6.3-7.1 Exam 2 solutions are distributed in class, programming assignment out
21 Th, Nov 14 Relationships between models. Class P. (pdf) Chapters 7.1-7.2 On Friday: HW8 due, HW9 out
22 Tu, Nov 19 Class NP. P vs. NP question. (pdf) Chapters 7.3
23 Th, Nov 21 Polynomial-time reductions. NP-completeness. (pdf) Chapters 7.4-7.5 On Friday: HW9 and extra credit programming assignment due, HW10 out
24 Tu, Nov 26 Cook-Levin Theorem. Examples of NP-complete problems. (pdf) Chapters 7.4-7.5
25 Tu, Dec 3 Space complexity. Savitch's Theorem. PSPACE. PSPACE-completeness. (pdf) Chapters 8.1-8.3
26 Th, Dec 5 PSPACE-completeness. Time and space hierarchy theorems. (pdf) Chapters 8.3, 9.1 HW10 due (on Friday); final exam preparation handout distributed in class
27 Tu, Dec 10 Review and Jeopardy!
Tu, Dec 17 Final Exam, 3:00pm-5:00pm CGS 311

Miscellaneous

Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; ShareLatex is a web-based latex system (allows you to avoid latex installation on your machine).
Not so short intro to latex; a latex tutorial.
Homework template files: tex, pdf, cls, jpg.

Sofya Raskhodnikova