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