CS420: Intro to Theory of Computation
UMass Boston, Spring 2021
Thu, 21 Jan 2021 00:00:00 -0500
Hi Students,
Welcome to CS420! I am looking forward to the semester.
Please fill out the pre-class survey before the first class (Mon Jan 25).
(Enter your umb.edu credentials into the Google sign-in box to access the survey.)
Remote learning can be tough so this will help me better tailor the course to each of you.
be familiar with basic concepts in mathematical logic and set theory; and
be able to write small programs from scratch (in a language of your choice).
This includes being able to setup a dev environment and write basic build scripts.
In other words, in this class, neither basic math nor programming are themselves the subjects of study, but instead you will use them as tools to study a deeper subject.
(Homework 0 will check and serve as a refresher for these prerequisites.)
See you in the first class!
Last updated: Tue, 20 Apr 2021 13:20:35 -0400
Schedule (subject to change):
Lectures meet MW 4-5:15pm via Zoom.
# | Date | Topic | Reading | HW out |
1 | 1/25 Mon | Intro to Theory of Computation [slides] | Ch 0 | |
2 | 1/27 Wed | Deterministic Finite Automata (DFAs) [slides] | 1.1 | |
3 | 2/1 Mon | Regular Languages [slides] | 1.1 | |
4 | 2/3 Wed | Combining Regular Languages [slides] | 1.1 | |
5 | 2/8 Mon | Nondeterminism and NFAs [slides] | 1.2 | |
6 | 2/10 Wed | NFA -> DFA, Reg Exprs [slides] | 1.2-1.3 | |
no class | 2/15 Mon | President’s Day | ||
7 | 2/17 Wed | More Reg Exprs, Inductive Proofs [slides] | 1.3 | |
8 | 2/22 Mon | More Inductive Proofs, Non-Regular Langs [slides] | 1.3-1.4 | |
9 | 2/24 Wed | Pumping Lemma Proof Examples [slides] | 1.4 | |
10 | 3/1 Mon | Context-free Grammars (CFGs) [slides] | 2.1 | |
11 | 3/3 Wed | Pushdown Automata (PDA), CFG<->PDA [slides] | 2.2 | |
12 | 3/8 Mon | DCFLS, DPDAs, and Parsing [slides] | 2.4 | |
13 | 3/10 Wed | Non-CFLs; Intro to Turing Machines (TMs) [slides] | 2.3,3.1,3.3 | |
no class | 3/15 Mon | Spring Break | ||
no class | 3/17 Wed | Spring Break | ||
14 | 3/22 Mon | Turing Machine Variants [slides] | 3.2,3.3 | |
15 | 3/24 Wed | Decidability and Regular Langs [slides] | 4.1 | |
16 | 3/29 Mon | Decidability and CFLs [slides] | 4.1 | |
17 | 3/31 Wed | Diagonalization and Undecidability [slides] | 4.2 | |
18 | 4/5 Mon | Reducibility and the Halting Problem [slides] | 5.1 | |
19 | 4/7 Wed | Mapping Reducibility [slides] | 5.3 | |
20 | 4/12 Mon | Turing Machines and Recursion [slides] | 6.1 | |
21 | 4/14 Wed | Intro to Time Complexity [slides] | 7.1 | |
no class | 4/19 Mon | Patriot’s Day | ||
22 | 4/21 Wed | Polynomial Time (P) [slides] | 7.2 | |
23 | 4/26 Mon | NP [slides] | 7.3 | |
24 | 4/28 Wed | Poly Time Reducibility, NP-Completeness [slides] | 7.4 | |
25 | 5/3 Mon | The Cook-Levin Theorem [slides] | 7.4,7.5 | |
26 | 5/5 Wed | HAMPATH is NP-Complete [slides] | 7.5 | |
27 | 5/10 Mon | More NP-complete Problems [slides] | 7.5 | |
28 | 5/12 Wed | Recap (last class) [slides] | all |