CS420: Intro to Theory of Computation
UMass Boston, Spring 2024
Mon, 15 Jan 2024 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 other accounts 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: Mon, 22 Apr 2024 11:52:45 -0400
Schedule (subject to change):
Lectures meet MW 2:30-3:45pm in McCormack M03-0407
Readings: S = Sipser; HMU = Hopcroft, Motwani, Ullmann
# | Date | Topic | Reading | HW out |
1 | 1/22 Mon | Welcome to CS420 [slides] | S0.2-0.4, HMU1.2-1.4 | |
2 | 1/24 Wed | CS420 Logistics [slides] | S0.2-0.4, HMU1.2-1.4 | |
3 | 1/29 Mon | Using and Proving Logical Statements [slides] | HMU1.2-1.4 | |
4 | 1/31 Wed | Deterministic Finite Automata (DFA) [slides] | S1.1 | |
5 | 2/5 Mon | Computing with DFAs [slides] | HMU2.2 | |
6 | 2/7 Wed | Regular Languages [slides] | S1.1, HMU2.2 | |
7 | 2/12 Mon | Combining DFAs, Closed Ops [slides] | S1.1, HMU2.2 | |
8 | 2/14 Wed | Nondeterminism and NFAs [slides] | S1.2, HMU2.3,2.5 | |
no class | 2/19 Mon | President’s Day | ||
9 | 2/21 Wed | Computing with NFAs [slides] | S1.2, HMU2.3,2.5 | |
10 | 2/26 Mon | NFA -> DFA [slides] | S1.2, HMU2.3 | |
11 | 2/28 Wed | Regular Expressions [slides] | S1.3 | |
12 | 3/4 Mon | Proof by Induction [slides] | S0.4,1.3, HMU1.4 | |
13 | 3/6 Wed | Non-Regular Languages [slides] | S1.4 | |
no class | 3/11 Mon | Spring Break | ||
no class | 3/13 Wed | Spring Break | ||
14 | 3/18 Mon | Context-free Grammars (CFG) [slides] | S2.1, HMU5.1 | |
15 | 3/20 Wed | Pushdown Automata (PDA) [slides] | S2.2, HMU6.1 | |
16 | 3/25 Mon | CFL <=> PDA, CFL Subsets, DPDAs [slides] | S2.2,2.4, HMU6.1 | |
17 | 3/27 Wed | non-CFLs [slides] | S2.3 | |
18 | 4/1 Mon | Turing Machines (TMs) [slides] | S3.1-3.3 | |
19 | 4/3 Wed | Nondeterministic TMs, TM configs [slides] | S3.2 | |
20 | 4/8 Mon | Decidability [slides] | S4.1 | |
21 | 4/10 Wed | Decidability for DFAs [slides] | S4.1 | |
no class | 4/15 Mon | Patriot’s Day | ||
22 | 4/17 Wed | Decidability for CFLs [slides] | S2.1,4.1 | |
no class | 4/18 Thu | Course P/F/Withdraw Deadline | ||
23 | 4/22 Mon | Undecidability [slides] | S4.2,5.1, HMU9.3 | |
24 | 4/24 Wed | Reducibility [slides] | S4.2,5.1, HMU9.3 | |
25 | 4/29 Mon | Mapping Reducibility | S5.3, HMU9.5 | |
26 | 5/1 Wed | Unrecognizability | S4.2,5.2-5.3, HMU9.5 | 11 |
27 | 5/6 Mon | Intro to Time Complexity | S7.1 | |
28 | 5/8 Wed | P | S7.2-3 | 12 |
5/9 Thu | Study Period start | |||
5/12 Sun | Study Period end | |||
no class | 5/13 Mon | Final Exam Period | ||
no class | 5/15 Wed | Final Exam Period |