CS 4410, Spring 2025 Class
Schedule, Lecture Notes
Note: Schedule is subject to
change, please check frequently
|
WK |
Class/Date |
Topic |
Book
Chapter |
Assignments |
Reading |
| 1 |
W 1/29 |
Syllabus |
Write down 2
questions about the syllabus |
Syllabus |
|
| F 1/31 |
Mathematical Preliminaries and Notation | 1.1 |
HW1 Assigned | ||
|
2 |
M 2/3 |
Mathematical Preliminaries and Notation | 1.1 |
||
|
W 2/5 |
Mathematical Preliminaries and Notation | 1.1 |
|||
|
F 2/7 |
Practice
Proofs |
||||
3 |
M 2/10 |
Practice Proofs | HW1
Due |
||
| W 2/12 |
Three Basic Concepts | 1.2 |
HW2 Assigned Practice Proofs Due |
||
| F 2/14 |
Three Basic Concepts | 1.2 |
|||
4 |
M
2/17 |
Three Basic Concepts | 1.2 |
||
| W 2/19 |
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 2/21 |
Deterministic Finite Accepters | 2.1 |
HW3 Assigned |
||
|
5 |
M 2/24 |
Practice with DFAs Nondeterministic Finite Accepters |
2.2 |
Algorithms to Live By
reachtion paper Due |
|
|
W 2/26 |
Nondeterministic Finite Accepters | 2.2 |
HW2
Due HW4 Assigned |
||
|
F 2/28 |
Equivalence of Deterministic and Nondeterministic Finite Accepters | 2.3 |
|||
|
6 |
M 3/3 |
Group Work on HW3 and HW4 | HW3 Due |
||
|
W 3/5 |
Regular Expressions | 3.1 |
|||
|
F 3/7 |
Regular Expressions and Regular Languages | 3.2 |
HW4 Due | ||
|
7 |
M 3/10 |
Regular Expressions and Regular Languages | 3.2 |
HW5 Assigned |
|
|
W 3/12 |
Regular Grammars |
3.3 |
|||
|
F 3/14 |
Regular Grammars | 3.3 |
|||
|
8 |
M 3/17 |
Review for Quiz 1 |
Chapter 2 |
HW5 Due |
|
|
W 3/19 |
Closure Properties of Regular Languages | 4.1 |
|||
|
F 3/21 |
Quiz
1 |
Chapter 2 |
|||
|
9 |
M 3/24 |
Closure Properties of Regular Languages | 4.1 |
||
|
W 3/26 |
Elementary Questions about Regular Languages | 4.2 |
HW6
Assigned |
||
|
F 3/28 |
Pumping
Lemma for Regular Languages |
4.3 |
HW7 Assigned | ||
| Spring Break: March 31- April 4 | |||||
|
|
|
Quiz 2 Review |
Chapter 3 |
||
|
W 4/9 |
Quiz 2 Review | Chapter 3 |
HW6 Due |
||
|
F 4/11 |
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 |
||
|
11 |
|
Pumping Lemma for Regular Languages | 4.3 |
Buzzard
Reaction Paper Due in Canvas |
|
|
W 4/16 |
Quiz 2 |
Chapter
3 |
|||
|
F 4/18 |
Pumping
Lemma example and homework hints |
||||
|
12 |
|
Context-Free Grammars | 5.1 |
||
|
W 4/23 |
Context-Free Grammars, Parsing and Ambiguity | 5.2 |
HW7 Due HW8 Assigned |
||
|
F 4/25 |
Nondeterministic Pushdown Automata | 7.1 |
|||
|
13 |
|
Nondeterministic Pushdown Automata | 7.1 |
HW9 Assigned | |
|
W 4/30 |
Pushdown Automata and CFLs | 7.2 |
HW8 Due | ||
|
F 5/2 |
Quiz
3 |
Pumping Lemma |
|||
|
14 |
|
Turing Machines | 9 |
HW9 Due Chapter 12 and 14 Reflections Assigned |
|
|
W 5/7 |
Quiz 4 |
Chapter 5 |
|||
|
F 5/9 |
Warrior
Day - No Class Meeting |
||||
| 15 |
M 5/12 |
Return Quizzes and Quiz 5 review | |||
| W 5/14 | Some problems that cannot be solve by Turing
Machines Efficiency of Computation |
12, 14 |
|||
| F 5/16 |
Quiz 5 | Chapter 7 |
Chapter 12
and 14 Reflections Due |
||
| |
Friday 5/23 |
FINAL EXAM |
Retake Quizzes
All work due to be uploaded to Canvas by 1:15 pm |