CS 4410, Fall 2025 Class
Schedule, Lecture Notes
Note: Schedule is subject to
change, please check frequently
|
WK |
Class/Date |
Topic |
Book
Chapter |
Assignments |
Reading |
| 1 |
W 8/20 |
Syllabus |
Write down 2
questions about the syllabus |
Syllabus |
|
| F 8/22 |
Mathematical Preliminaries and Notation | 1.1 |
HW1 Assigned | ||
|
2 |
M 8/25 |
Mathematical Preliminaries and Notation | 1.1 |
||
|
W 8/27 |
Mathematical Preliminaries and Notation | 1.1 |
|||
|
F 8/29 |
Practice
Proofs on your own - no class meeting |
||||
3 |
M 9/1 |
Labor Day Holiday - no
class meeting |
|||
| W 9/3 |
Three Basic Concepts | 1.2 |
HW2 Assigned HW1 Due |
||
| F 9/5 |
Practice with Proofs |
||||
4 |
M
9/8 |
Three Basic Concepts | 1.2 |
Practice Proofs Due | |
| W 9/10 |
Deterministic Finite Accepters | 2.1 |
HW3
Assigned |
||
| F 9/12 |
Practice
with DFAs |
2.1 |
HW4 Assigned |
||
|
5 |
M 9/15 |
Nondeterministic Finite Accepters | 2.2 |
||
|
W 9/17 |
Equivalence of Deterministic and Nondeterministic Finite Accepters | 2.3 |
HW2 Due | ||
|
F 9/19 |
Group Work on HW3 and HW4 | ||||
|
6 |
M 9/22 |
Regular Expressions | 3.1 |
HW5 Assigned HW3 Due |
|
|
W 9/24 |
Regular Expressions and Regular Languages | 3.2 |
HW4
Due |
||
|
F 9/26 |
Regular Languages and Regular Grammars | 3.2 |
|||
|
7 |
M 9/29 |
Regular Grammars, Homework 5, Quiz Review | 3.3 |
||
|
W 10/1 |
No Class Today,
instead watch: Brian Christian and Tom Griffiths "Algorithms to Live By" Talks at Google |
Reaction Paper: 1. List the problems they discussed.
2. Pick one of the problems and describe it and their
solution(s).3. Describe a problem in your life that might have an algorithmic solution In Canvas |
https://www.youtube.com/watch?v=OwKj-wgXteo |
||
|
F 10/3 |
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 |
||
|
8 |
M 10/6 |
Quiz review and Chapter 3 review |
|||
|
W 10/8 |
Quiz on Chapter 2 |
||||
|
F 10/10 |
Regular Grammars | 3.3 |
|||
|
9 |
M 10/13 |
Group Work on HW5 |
|||
|
W 10/15 |
Closure Properties of Regular Languages | 4.1 |
|||
|
F 10/17 |
Elementary
Questions about Regular Languages Work on Homework 5 |
4.2 |
HW5 Due | ||
|
|
|
Pumping Lemma for Regular Languages | 4.3 |
||
|
W 10/22 |
Pumping Lemma for Regular Languages | 4.3 |
|||
|
F 10/24 |
Pumping Lemma for Regular Languages | 4.3 |
|||
|
11 |
|
HW5 Solns and quiz review, work on HW 6 | HW6 Due | ||
|
W 10/29 |
Pumping Lemma for Regular Languages | ||||
|
F 10/31 |
Work
on HW6 and HW7 |
||||
|
12 |
|
Quiz 2 on Chapter 3 |
HW7 Due | ||
|
W 11/5 |
Context-Free Grammars | 5.1 |
|||
|
F 11/7 |
Context-Free Grammars, Parsing and Ambiguity | 5.2 |
HW8 Assigned | ||
|
13 |
|
Nondeterministic Pushdown Automata | 7.1 |
||
|
W 11/12 |
Nondeterministic Pushdown Automata |
7.1 |
HW9 Assigned | ||
|
F 11/14 |
Pushdown Automata and CFLs | 7.2 |
|||
|
14 |
|
Turing Machines | 9 |
HW8 Due |
|
|
W 11/19 |
Quiz 3 on Pumping Lemma | Chapter 12 and 14 Reflections Assigned | |||
|
F 11/21 |
Quiz Review | HW9 Due | |||
| Thanksgiving Break:
November 24 - 28 |
|||||
| 15 |
M 12/1 |
Some problems that cannot
be solve by Turing Machines Efficiency of Computation Quiz Review |
12, 14 | Videos on
Canvas |
|
| W 12/3 | Quiz 4 on Chapter 5 | ||||
| F 12/5 |
Quiz 5 on Chapter 7 |
||||
| M 12/8 |
Review for final and more
on complexity |
Chapter 12 and 14 Reflections Due | |||
| |
Friday 12/12 |
FINAL EXAM |
|