CS420: Intro to Theory of Computation
UMass Boston, Spring 2022
Tue, 18 Jan 2022 00:00:00 -0500
Hi Students,
Welcome to CS420! I am looking forward to the semester.
To ensure a smooth start, please fill out this pre-class survey as soon as you can. (Enter your full umb.edu email into the Google sign-in box to access the survey. You may need to sign out of another account first, or open the link in an incognito window.) This way I can address any concerns as soon as possible.
Also, please note that CS220 (discrete math) is a requirement (and you will need it).
See you in the first class!
Last updated: Tue, 3 May 2022 12:49:23 -0400
Schedule (subject to change):
Lectures meet MW 4-5:15pm, University Hall Y02-2300
Readings: S = Sipser; HMU = Hopcroft, Motwani, Ullmann
# | Date | Topic | Reading | HW out |
1 | 1/24 Mon | Intro to CS420 [slides] | S0.2-0.4, HMU1.2-1.4 | |
2 | 1/26 Wed | Finite Automata and DFAs [slides] | S1.1, HMU2.2 | |
3 | 1/31 Mon | Combining DFAs, Closed Ops [slides] | S1.1, HMU2.2 | |
4 | 2/2 Wed | Nondeterminism and NFAs [slides] | S1.2, HMU2.3,2.5 | |
5 | 2/7 Mon | NFA -> DFA [slides] | S1.2, HMU2.3 | |
6 | 2/9 Wed | Regular Expressions [slides] | S1.3 | |
7 | 2/14 Mon | Non-Regular Languages [slides] | S1.4 | |
8 | 2/16 Wed | Context-free Grammars (CFGs) [slides] | S2.1, HMU5.1 | |
no class | 2/21 Mon | President’s Day | ||
9 | 2/23 Wed | Pushdown Automata (PDA) [slides] | S2.2, HMU6.1 | |
10 | 2/28 Mon | DPDAs and Parsing; Non-CFLs [slides] | S2.4 | |
11 | 3/2 Wed | Turing Machines (TMs) [slides] | S3.1-3.3 | |
12 | 3/7 Mon | Nondeterministic TMs [slides] | S3.2 | |
13 | 3/9 Wed | Decidability [slides] | S4.1 | |
no class | 3/14 Mon | Spring Break | ||
no class | 3/16 Wed | Spring Break | ||
14 | 3/21 Mon | Decidability for CFLs [slides] | S4.1 | |
15 | 3/23 Wed | Undecidability [slides] | S4.2,5.1, HMU9.3 | |
16 | 3/28 Mon | Reducibility [slides] | S4.2,5.1, HMU9.3 | |
17 | 3/30 Wed | Context-sensitivity, LBAs [slides] | S5.1-2, HMU8.1,9.5 | |
18 | 4/4 Mon | Mapping Reducibility [slides] | S5.3, HMU9.5 | |
19 | 4/6 Wed | Unrecognizability [slides] | S4.2,5.2-5.3, HMU9.5 | |
20 | 4/11 Mon | Turing Machines and Recursion [slides] | S6.1 | |
21 | 4/13 Wed | Intro to Time Complexity [slides] | S7.1 | |
no class | 4/18 Mon | Patriots Day | ||
22 | 4/20 Wed | P [slides] | S7.2-3 | |
23 | 4/25 Mon | NP [slides] | S7.2-3 | |
24 | 4/27 Wed | NP-Completeness [slides] | S7.3-4 | |
25 | 5/2 Mon | The Cook-Levin Theorem [slides] | S7.4-5 | |
26 | 5/4 Wed | NP-Complete Problems [slides] | S7.5 | |
27 | 5/9 Mon | More NP-Complete Problems [slides] | ||
28 | 5/11 Wed | Intro Space Complexity [slides] | S8.1-2 |