
[Schedule/Assignments  Project
Info  What's New?]
This
Schedule is tentative, but the topics we’ll cover should not deviate too much from it.

DATE

LECTURE (Handouts)

READING

ASSIGNMENT

Tue Jan 14

Overview
Deterministic Finite Automata and Regular
Languages (1pdf)

Chapters 0, 1.1

Homework 1 Sol1

Thu Jan 16

NonDeterminism and Regular Operations (2pdf)

Chapter 1.2


Tue Jan 21

Regular Expressions and the Pumping Lemma for
Regular Languages (3pdf)

Chapter 1.3, 1.4

Homework 2 Sol2

Thu Jan 23

Minimizing DFAs (4pdf)

Finish Chapter 1


Tue Jan 28

PushDown Automata and ContextFree Grammars;
Pumping Lemma for CFLs (5pdf)

Chapter 2.1, 2.2, 2.3

Homework 3 Sol3

Thu Jan 30

Equivalence of PDAs and CFGs,
(6pdf)



Tue Feb
5

Chomsky Normal Form, Turing Machines (7pdf)

Chapter 2, Chapter 3

Review1
Homework

Thu Feb 6

Review (8pdf)


*Project Report
1 due
(Topic, Main
Contact)

Tue Feb 11

Midterm Exam 1


Homework 4 Sol4

Thu Feb 13

Undecidability (9pdf)

Chapter 3, Chapter 4


Tue Feb 18

Undecidability II:
Reductions (10pdf)

Chapter 5.1

Homework 5 Sol5

Thu Feb 20

More Mapping Reducibilities

Chapter 5.3


Tue Feb 25

Post Correspondence Problem (11pdf)

Chapter 5.2

Homework 6 Sol6

Thu Feb 27

Rice’s Theorem; The Recursion Theorem; The FixedPoint
Theorem (12pdf)

Chapter 6


Tue Mar 4

Oracle Turing Machines and Turing Reducibility (13pdf)

Chapter 6

Homework 7 Sol7

Thu Mar 6

The Arithmetic Hierarchy (14pdf)

Chapter 6


Tue Mar 11

No class. SPRING BREAK!



Thur
Mar 13

No class. SPRING BREAK!



Tue Mar 18

KolmogorovChaitin
Complexity (15pdf)

Chapter 6


Thu Mar
20

Time Complexity and Polynomial Time;
NonDeterministic Turning Machines and NP (16pdf)

Chapters 7


Tue Mar 25

NPCompleteness:The CookLevin
Theorem(17apdf)

Chapters 7

**Project
Report 2 due
(Detailed Outline or Draft)
Homework 8 Sol8

Thu Mar 27

NPCompleteness:The CookLevin Theorem(17bpdf)



Tue Apr 1

NP: Completeness: Karp (18 pdf)

Chapter 7


Thu Apr 3

Midterm Review Review (19 pdf)



Tue Apr 8

Midterm Exam 2



Thu Apr 10

No Class, SPRING CARNIVAL!



Tue Apr 15

Space Complexity I: Savitch's
Theorem and PSPACECompleteness (20 pdf)

Chapter 8

Homework 9 Sol9

Thu Apr 17

Space Complexity II. (21 pdf)

Chapter 8


Tue Apr 22

Randomized Complexity: BPP, RP, etc.,
coClasses
(22 pdf)

Chapter 10.2

Homework
10 Sol10

Thu Apr 24

Project
Presentations I



Tue Apr 29

Project
Presentations II



Thur May 1

Review and Presentations
III


***Final Project Report due


FINAL EXAM Friday May 9, 5:30 pm, MM
A14
Good luck!!!



