| [**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 |
Non-Determinism 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 |
Push-Down Automata and Context-Free 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 Fixed-Point 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 |
Kolmogorov-Chaitin Complexity (15pdf) |
Chapter 6 |
|
| Thu Mar 20 |
Time Complexity and Polynomial Time; Non-Deterministic Turning Machines and NP (16pdf) |
Chapters 7 |
|
| Tue Mar 25 |
NP-Completeness:The Cook-Levin Theorem(17apdf) |
Chapters 7 |
** Project Report 2 due (Detailed Outline or Draft) Homework 8� Sol8 |
| Thu Mar 27 |
NP-Completeness:The Cook-Levin 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 PSPACE-Completeness (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., co-Classes (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!!! |
|
|
|
|
|
|
|