CS475 Lecture Schedule
Spring 2022


The lectures assume that you have already done the pre-class readings from the textbook (Sipser). So they do not walk through basic definitions but, rather, concentrate on aspects of the topic that you probably didn't fully understand after doing the readings. This schedule is just a draft for now; the topics may shift around and the readings will be made more specific soon, but the exam dates will not change.

(worksheet)

 

Week Monday Tuesday Thursday Friday
Week 1
Jan 17-21
 

Pre-class reading: Chapter 0: intro and section 1 (p1-3), and subsection "strings and languages" (p13-14)
Chapter 1: intro and parts of sections 1 (p34-37) and 2 (p47-51)

DFAs / NFAs / regular languages
(slides)
(worksheet)

[topics are from Sipser 1.1-1.3]

Pre-class reading: None

Pumping Lemma / nonregular languages
(worksheet)

[topic is from Sipser 1.4]

Warm-up Problems 1 due at midnight

Week 2
Jan 24-28

Homework 1 due at midnight Pre-class reading: definition and examples of PDAs (section 2.2, p111-116)
academic integrity policy

CFGs / PDAs
(worksheet)

Pre-class reading: definition and examples of CFGs (Section 2.1 p102-105)

CFGs / PDAs
(worksheet)

Warm-up Problems 2 due at midnight

Week 3
Jan 31-Feb 4

Homework 2 due at midnight

exam instructions

CFGs / PDAs
(worksheet)

Pre-class reading: Intro to Turing Machines (p165-170)

Turing machine defn. and variants
(worksheet)

Warm-up Problems 3 due at midnight

Week 4
Feb 7-11

Homework 3 due at midnight

campus emergency info
special situations

Exam review
(worksheet)

Exam 1 No warm-up problems due
Week 5
Feb 14-18
No HW due today

regrade requests

Turing machine defn. and variants
(worksheet)

(un)decidable languages
(worksheet)

Warm-up Problems 5 due at midnight
Week 6
Feb 21-25
Homework 4 due at midnight Enumerators
(worksheet)

Pre-class reading: p215-217

Reducibility
(worksheet)

Warm-up Problems 6 due at midnight
Week 7
Feb 28-Mar 4
Homework 5 due at midnight Reductions using computation histories
(worksheet)
Turing Reducibility (Oracle TMs)
(worksheet)
Warm-up Problems 7 due at midnight (extended to Sunday)
Week 8
Mar 7-11
Homework 6 due at midnight Exam review
(worksheet)
Exam 2 No warm-up problems due
Spring Break
Week 9
Mar 21-25
No HW due today Time complexity
(worksheet)
Time complexity (including NP and ptime-reductions)
(worksheet)
Warm-up Problems 9 due at midnight
Week 10
Mar 28-Apr 1
Homework 7 due at midnight Time complexity (including NP and ptime-reductions)
(worksheet)
Time complexity (including NP and ptime-reductions)
(worksheet)
Warm-up Problems 10 due at midnight
Week 11
Apr 4-8
Homework 8 due at midnight (Chap. 8)

Space complexity
(worksheet)
Space complexity
(worksheet)
Warm-up Problems 11 cancelled
Week 12
Apr 11-15
Homework 9 due at midnight Exam review
(worksheet)
Exam 3 No warm-up problems due
Week 13
Apr 18-22
No HW due today

Space complexity: L and NL
(worksheet)

(Chap. 6)

Recursion theorem
(worksheet)

Warm-up Problems 13 cancelled
Week 14
Apr 25-29

Homework 10 due at midnight

Hierarchy Theorems and Relativization (Ch 9)
(worksheet)

Descriptive complexity (Ch 6)
(worksheet)

Warm-up Problems 14 cancelled
Week 15
May 2-6
Homework 11 due at midnight Exam review
(worksheet)
No class  
Finals Week