|
|
|
[Schedule/Assignments | Project Handout | What's New]
This
Schedule is tentative, but the topics we’ll cover should not deviate too much from it.
|
|
DATE
|
LECTURE (class handouts)
|
READING
|
ASSIGNMENT
|
|
Tue Jan 15
|
Overview
Deterministic Finite Automata and Regular
Languages (1pdf)
|
Chapters 0, 1.1
|
Homework 1 Sol1
|
|
Thu Jan 17
|
Non-Determinism and Regular Operations (2pdf)
|
Chapter 1.2
|
|
|
Tue Jan 22
|
Regular Expressions and the Pumping Lemma for
Regular Languages (3pdf)
|
Chapter 1.3, 1.4
|
Homework 2 Sol2
|
|
Thu Jan 24
|
Minimizing DFAs (4pdf)
|
Finish Chapter 1
|
|
|
Tue Jan 29
|
Push-Down Automata and Context-Free Grammars;
Pumping Lemma for CFLs (5pdf)
|
Chapter 2.1, 2.2, 2.3
|
Homework 3 Sol3
|
|
Thu Jan 31
|
Equivalence of PDAs and CFGs,
(6pdf)
|
|
|
|
Tue Feb
5
|
Chomsky Normal Form, Turing Machines (7pdf)
|
Chapter 2, Chapter 3
|
Review1
Homework
|
|
Thu Feb 7
|
Review (8pdf)
|
|
*Project Report
1 due
(Topic, Main
Contact)
|
|
Tue Feb 12
|
Midterm Exam 1
|
|
Homework 4 Sol4
|
|
Thu Feb 14
|
Undecidability (9pdf)
|
Chapter 3, Chapter 4
|
|
|
Tue Feb 19
|
Undecidability II:
Reductions (10pdf)
|
Chapter 5.1
|
Homework 5 Sol5
|
|
Thu Feb 21
|
More Mapping Reducibilities
|
Chapter 5.3
|
|
|
Tue Feb 26
|
Post Correspondence Problem (11pdf)
|
Chapter 5.2
|
Homework 6 Sol6
|
|
Thu Feb 28
|
Rice’s Theorem; The Recursion Theorem; The Fixed-Point
Theorem (12pdf)
|
Chapter 6
|
|
|
Tue Mar 5
|
Oracle Turing Machines and Turing Reducibility (13pdf)
|
Chapter 6
|
Homework 7 Sol7
|
|
Thu Mar 7
|
The Arithmetic Hierarchy (14pdf)
|
Chapter 6
|
|
|
Tue Mar 12
|
No class. SPRING BREAK!
|
|
|
|
Thur
Mar 14
|
No class. SPRING BREAK!
|
|
|
|
Tue Mar 19
|
Kolmogorov-Chaitin
Complexity (15.pdf)
|
Chapter 6
|
|
|
Thu Mar 23
|
Review (16pdf)
|
|
**Project Report 2 due
|
|
Tue Mar 26
|
Midterm Exam 2
|
|
Homework 8 Sol8
|
|
Thu Mar 28
|
Time Complexity and Polynomial Time;
Non-Deterministic Turning Machines and NP (17pdf)
|
Chapters 7.1-7.4
|
|
|
Tue Apr 2
|
NP-Completeness:The Cook-Levin Theorem(18
pdf)
|
Chapter 7.5
|
Homework 9 Sol9
|
|
Thu Apr 4
|
SAT Solvers; Midterm Review
|
|
|
|
Tue Apr 9
|
NP: Completeness: Karp (19 pdf)
|
Chapter 8
|
Homework
10 Sol10
|
|
Thu Apr 11
|
Space Complexity I: Savitch's
Theorem and PSPACE-Completeness (20 pdf)
|
|
|
|
Tue Apr 16
|
Space Complexity II. (21 pdf)
|
Chapter 10.2
|
Homework
11 Sol11
|
|
Thu Apr 18
|
No Class, SPRING CARNIVAL!
|
|
|
|
Tue Apr 23
|
Randomized Complexity: BPP, RP, etc.,
co-Classes
(22 pdf)
|
|
|
|
Thu Apr 25
|
Project
Presentations I
|
|
|
|
Tue Apr 30
|
Project
Presentations II
|
|
|
|
Thur May 2
|
Review and Presentations
III
|
|
***Final Project Report due
|
|
FINAL EXAM
Good luck!!!
|
|
|
|
|
