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

11

M 10/30

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

M 11/6

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

M 11/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

M 11/27

Quiz 5 Review
7


W 11/29

Limits of Algorithmic Computation 12
Chapter 12 Reflection

F 12/1

Overview of Computational Complexity 14


15

M 12/4

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