CS 4410, Fall 2022 Class
Schedule, Lecture Notes
Note: Schedule is subject to
change, please check frequently
|
WK |
Class/Date |
Topic |
Book Chapter |
Assignments
|
Reading |
|
1 |
M
8/22 |
Course Introduction | Syllabus |
||
|
W 8/24 |
Mathematical Preliminaries and Notation | 1.1 |
Assignment 1 |
Chapter 1 |
|
|
F 8/26 |
Mathematical Preliminaries and Notation | 1.1 |
|||
|
2 |
M 8/29 |
Mathematical Preliminaries and Notation | 1.1 |
||
|
W 8/31 |
Mathematical Preliminaries and Notation | 1.1 |
|||
|
F 9/2 |
Mathematical Preliminaries and Notation | 1.1 |
|||
|
3 |
M 9/5 |
Labor Day Holiday - no class | |||
|
W 9/7 |
Group work on HW1 Three Basic Concepts |
1.2 |
Assignment
2 |
||
|
F 9/9 |
Three Basic Concepts | 1.2 |
Assignment 1 Die |
||
4 |
M 9/12 |
Three Basic Concepts Hints on HW2 |
1.2 |
||
| W 9/14 |
Group work on HW2 |
1.2 |
Assignment
2 Due |
||
| F
9/16 |
Deterministic Finite Accepters | 2.1 |
Assignment 3 |
||
5 |
M
9/19 |
Nondeterministic Finite Accepters | 2.2 |
||
| W 9/21 |
Equivalence of Deterministic and Nondeterministic Finite Accepters | 2.3 |
Assignment
4 |
||
| F
9/23 |
Group work on HW3 and HW4 |
||||
|
6 |
M 9/26 |
Regular Expressions Video in Canvas |
3.1 |
Assignment 3 Due |
|
|
W 9/28 |
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. |
https://www.youtube.com/watch?v=OwKj-wgXteo | ||
|
F 9/30 |
Regular Expressions and Regular Languages Video in Canvas |
3.2 |
|||
|
7 |
M 10/3 |
Regular Expressions and Regular Languages | 3.2 |
Assignment 4 Due Assignment 5 |
|
|
W 10/5 |
Watch: What Computers Can't Do - with Kevin Buzzard |
Reaction
Paper: What is P vs NP? Why is it important? |
https://www.youtube.com/watch?v=jQPb7DRMoZY | ||
|
F 10/7 |
Regular Grammars Video in Canvas |
3.3 | |||
|
8 |
M 10/10 |
Closure Properties of Regular Languages | 4.1 |
Algorithms and Buzzard
reaction papers due in Canvas |
|
|
W 10/12 |
Closure Properties of
Regular Languages Elementary Questions about Regular Languages |
4.1 4.2 |
|||
|
F 10/14 |
Group work on HW5 | ||||
|
9 |
M 10/17 |
Elementary Questions about Regular Languages | 4.2 |
Assignment 5 Due |
|
|
W 10/19 |
Identifying Nonregular Languages | 4.3 |
Assignment 6 |
||
|
F 10/21 |
Group work on HW6 |
4.1,4.2 |
Assignment 7 |
||
|
10 |
M 10/24 |
Context-Free Grammars | 5.1 |
||
|
W 10/26 |
Context-Free Grammars | 5.1 |
|||
|
F 10/28 |
Group work on HW7 | 4.3 |
|||
|
|
|
Context-Free Grammar, Parsing and Ambiguity | 5.1, 5.2 |
Assignment 6
Due Assignment 8 |
|
|
W 11/2 |
Nondeterministic Pushdown Automata | 7.1 |
|||
|
F 11/4 |
Work on NFA -> DFA algorithm |
||||
|
12 |
|
Nondeterministic Pushdown Automata | 7.1 |
Assignment 7 Due | |
|
W 11/9 |
Nondeterministic Pushdown Automata | 7.1 |
Assignment 9 |
||
|
F 11/11 |
Veteran's Day
Holiday- no class |
2.3 |
|||
|
13 |
|
Group work on HW8 |
5.1, 5.2 | ||
|
W 11/16 |
Pushdown Automata and CFLs | 7.2 |
Assignment 8 Due | ||
|
F 11/18 |
Group work on HW9 | 7.1 |
|||
| All week |
Thanksgiving Break
11/21 - 11/25 |
Quiz 1 and 2 due 11/20 |
|||
|
14 |
|
Overview of Chapters 7 and 8 |
7, 8 |
Assignment
9 Due |
|
|
W 11/30 |
Turing
Machines |
9 |
Quiz 3 and 4 Due |
||
|
F 12/2 |
Limits of Algorithmic Computation |
12 |
Quiz 5 Due |
||
|
15 |
|
Overview of Computational Complexity | 14 |
||
|
W 12/7 |
Office
Hours |
||||
|
F 12/9 |
Office Hours |
All quizzes must be in Chapter 12 and 14 Reflections Due |
|||
Friday 12/16 |
11:15 am - 1:15 pm |