CS 4410 - 2, Fall 2026 Class
Schedule, Lecture Notes
Note: Schedule is subject to
change, please check frequently
|
WK |
Class/Date |
Topic |
Book
Chapter |
Assignments |
Reading |
| 1 |
W 8/19 |
Syllabus |
Write down 2
questions about the syllabus |
Syllabus |
|
| F 8/21 |
Practice with Proofs: PMI |
Practice
with Proofs |
|||
|
2 |
M 8/24 |
Practice with Proofs | |||
|
W 8/26 |
Mathematical
Preliminaries |
1.1 |
HW1
Assigned |
||
|
F 8/28 |
Mathematical Preliminaries | 1.1 |
Practice with Proofs Due |
||
3 |
M 8/31 |
Three Basic Concepts - Languages | 1.2 |
HW1
Due HW2 Assigned |
|
| W 9/2 |
Three Basic Concepts - Grammars and Automata | 1.2 |
|||
| F 9/4 |
Deterministic Finite Acceptors |
2.1 |
HW2 Due HW3 Assigned |
||
4 |
M
9/7 |
Labor Day Holiday |
|||
| W 9/9 |
Nondeterministic Finite Acceptors | 2.2 |
|||
| F 9/11 |
Equivalence of Deterministic and Nondeterministic Finite Accepters | 2.3 |
HW3 Due HW4 Assigned |
||
|
5 |
M 9/14 |
No Class Meeting - Watch: Biggest Puzzle in Computer Science: P vs. NP | Reaction Paper In Canvas |
https://www.youtube.com/watch?v=pQsdygaYcE4 |
|
|
W 9/16 |
No
Class Meeting - Watch: What Computers Can't Do - with Kevin Buzzard |
Reaction
Paper: What is P vs NP? Why is it important? In Canvas |
https://www.youtube.com/watch?v=jQPb7DRMoZY |
||
|
F 9/18 |
No Class Meeting - Listen to: Escape Claudes | HW4 Due Reaction Paper in Canvas |
https://www.thisamericanlife.org/896/i-know-what-you-need/act-two-2 |
||
|
6 |
M 9/21 |
Review Chapter 2 | 2 |
||
|
W 9/23 |
Regular Expressions | 3.1 |
Reaction
Papers Due HW5 Assigned |
||
|
F 9/25 |
Regular Expressions and Regular Languages | 3.2 |
|||
|
7 |
M 9/28 |
Quiz 1 |
Chapter 2 |
||
|
W 9/30 |
Regular Grammars | 3.3 |
|||
|
F 10/2 |
Closure Properties of Regular Languages | 4.1 |
HW6 Assigned | ||
|
8 |
M 10/5 |
Chapter 3 Review | |||
|
W 10/7 |
Elementary Questions about Regular Languages | 4.2 |
HW5 Due | ||
|
F 10/9 |
Pumping Lemma for Regular Languages | 4.3 |
HW7 Assigned | ||
|
9 |
M 10/12 |
Pumping Lemma for Regular Languages | 4.3 |
HW6 Due | |
|
W 10/14 |
Pumping Lemma for Regular Languages | 4.3 |
|||
|
F 10/16 |
Quiz
2 |
Chapter 3 |
|||
|
|
|
Pumping Lemma for Regular Languages Quiz Review and HW7 |
4.3 |
||
|
W 10/21 |
Context-Free Grammars | 5.1 |
HW7 Due HW8 Assigned |
||
|
F 10/23 |
Context-Free Grammars | 5.1 |
|||
|
11 |
M 10/26 |
Context-Free Grammars, Parsing and Ambiguity | 5.2 |
||
|
W 10/28 |
Nondeterministic Pushdown Automata | 7.1 |
HW8 Due HW9 Assigned |
||
|
F 10/30 |
Quiz
3 |
4.3 |
|||
|
12 |
|
NPDA and Quiz 4 Review | 7.1 |
||
|
W 11/4 |
Nondeterministic Pushdown Automata | 7.1 |
|||
|
F 11/6 |
Quiz 4 | 5.1 |
|||
|
13 |
|
NPDA and CFL on Zoom | 7.2 |
HW9 Due | |
|
W 11/11 |
Veteran's Day Holiday |
||||
|
F 11/13 |
Quiz
5 Review |
||||
|
14 |
|
Turing Machines |
9 |
||
|
W 11/18 |
Some problems that cannot be solved by Turing Machines | 12 |
Chapter 12 Reflection Assigned |
||
|
F 11/20 |
Quiz5 | ||||
| Thanksgiving Week
11/23-27 no classes |
|||||
| 15 |
M 11/30 |
Some problems that cannot be solved by Turing Machines | 12 |
||
| W 12/2 | Efficiency of Computation | 14 |
Chapter 14 Reflection Assigned | ||
| F 12/4 |
Efficiency of Computation | 14 |
|||
| M 12/7 |
Efficiency of Computation | 14 |
Chapter 12 and 14
Reflections Due Turn in Participation Worksheet |
||
| |
Wednesday 12/16
|
FINAL EXAM |
|