CS 4410, Fall 2023 Class
Schedule, Lecture Notes
Note: Schedule is subject to
change, please check frequently
WK |
Class/Date |
Topic |
Book Chapter |
Assignments
|
Reading |
1 |
M
8/21 |
Course Introduction |
1.1 |
Syllabus Chapter 1 |
|
W 8/23 |
Mathematical Preliminaries and Notation |
1.1 |
Assignment 1 | ||
F 8/25 |
Mathematical Preliminaries and Notation | 1.1 |
|||
2 |
M 8/28 |
Mathematical Preliminaries and Notation | 1.1 |
||
W 8/30 |
Three
Basic Concepts |
1.2 |
Assignment 1 Due Assignment 2 |
||
F 9/1 |
Three Basic Concepts | 1.2 |
|||
3 |
M 9/4 |
Labor Day Holiday |
|||
W 9/6 |
Assignment 2 hints
and group work |
1.2 |
|||
F 9/8 |
Deterministic Finite Accepters |
2.1 |
Assignment 3 |
||
4 |
M 9/11 |
Nondeterministic Finite Accepters | 2.2 |
||
W 9/13 |
Equivalence of Deterministic and Nondeterministic Finite Accepters | 2.3 |
Assignment
4 |
||
F
9/15 |
Group work on HW3 and HW4 | 2 |
Assignment 2 Due | ||
5 |
M
9/18 |
Group work on HW3 and HW4 | |||
W 9/20 |
Regular Expressions | 3.1 |
Assignment 3 Due | ||
F
9/22 |
Regular Expressions and Regular Languages | 3.2 |
Assignment 5 | ||
6 |
M 9/25 |
Regular Grammars | 3.3 |
Assignment 4 Due | |
W 9/27 |
Group work on HW5 | ||||
F 9/29 |
Closure Properties of Regular Languages |
4.1 |
|||
7 |
M 10/2 |
Closure Properties of Regular Languages Elementary Questions about Regular Languages Identifying Nonregular Languages |
4.1, 4.2, 4.3 | Assignment 5 Due | |
W 10/4 |
Go over Homework 3 |
2.1 |
|||
F 10/6 |
Go over Homework 4 |
2.2, 2.3 |
Assignment 6 | ||
8 |
M 10/9 |
Identifying Nonregular Languages | 4.3 |
||
W 10/11 |
Quiz 1 and 2 online |
||||
F 10/13 |
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 | ||
9 |
M 10/16 |
Identifying Nonregular Languages | 4.3 |
||
W 10/18 |
Identifying Nonregular Languages | 4.3 |
Assignment 7 | ||
F 10/20 |
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 | ||
10 |
M 10/23 |
Context-Free Grammars | 5.1 |
Assignment 6 Due | |
W 10/25 |
Context-Free Grammars | 5.1 |
|||
F 10/27 |
Context-Free Grammars Parsing and Ambiguity | 5.2 |
Assignment 7 Due | ||
|
|
Group work on HW 8 |
5.1, 5.2 |
Assignment 8 |
|
W 11/1 |
Homework 5 and Quiz 3
Review |
3.1, 3.2 |
|||
F 11/3 |
Nondeterministic Pushdown Automata | 7.1 |
|||
12 |
|
Nondeterministic Pushdown Automata | 7.1, 7.2 |
Assignment
8 Due |
|
W 11/8 |
Pushdown Automata and
CFLs |
7.2 |
Assignment 9 |
||
F 11/10 |
Veteran's Day Holiday | ||||
13 |
|
Properties of CFLs |
8.1, 8.2 |
||
W 11/15 |
Turing Machines |
9.1 |
Assignment 9 Due |
||
F 11/17 |
Quiz
4 and 5 review |
4.3, 7 |
|||
November 20-24 Thanksgiving Holiday | |||||
14 |
|
Quiz 5 Review |
7 |
||
W 11/29 |
Limits of Algorithmic Computation | 12 |
Chapter 12 Reflection | ||
F 12/1 |
Overview of Computational Complexity | 14 |
|||
15 |
|
Overview of Computational Complexity | 14 |
Chapter 14
Reflection |
|
W 12/6 |
Review
Quizzes |
||||
F 12/8 |
Review Quizzes | Chapter 12 and 14 Reflections Due | |||
Friday 12/15 |
11:15 am - 1:15 pm |
|