|
|
|
[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!!!
|
|
|
|
|
