|
2Date |
Topics
|
Readings
|
Notable |
|
9/8 Wed
|
L1. Introduction: course policies; Overview
|
|
Info Sheet
|
|
9/13 Mon
|
L2. Generalized Computers, Strings, Languages
|
Chp. 0
|
|
|
9/15 Wed
|
L3. Abstract Input/Output machines
|
|
|
|
9/20 Mon
|
L4. Abstract Deciders and the Language of a
Machine:> the three major paradigms
|
1.1
|
|
|
9/22 Wed
|
L5. Nondeterminism
|
1.2
|
|
|
9/27 Mon
|
L6. Regular Languages and Regular
Operations. Closure of Regular Languages Under
Boolean Operations
|
|
HW1
|
|
9/29 Wed
|
L7. Regular Expressions (REG); FA = NFA = REG
|
1.3
|
|
|
10/4 Mon
|
L8. Minimization
|
online lecture
,PDF
|
|
|
10/6 Wed
|
L9. Pumping Lemma
|
1.4
|
|
|
10/11 Mon
|
L10. Context Free Languages: Derivations,
Parse-Trees, Ambiguity
|
2.1
|
HW2
|
|
10/13 Wed
|
L11. Pushdown Stack Automata (PDA's)
|
2.2
|
|
|
10/18 Mon
|
L12. Grammar and Machine Transformations
|
2.3
|
|
|
10/20 Wed
|
MIDTERM 1
|
|
|
|
10/25 Mon
|
L13. Context Free Pumping Lemma
|
|
|
|
10/27 Wed
|
L14. Turing Machines: Motivation, Definitions,
Recognizers vs. Decider
|
3.1
|
HW3
|
|
11/1 Mon
|
NO CLASS Election holiday
|
|
|
|
11/3 Wed
|
L15. Turing Machine Variants: 3 levels of
TMabstraction, Non-deterministic recognizers
anddeciders, König's infinity lemma,
MultitapeTM's
|
3.3
|
|
|
11/8 Mon
|
L16. Universal Models of Computation:
TM=k-track TM = k-tape TM = NTM,FIFO
Queue Machines
|
4.1
|
|
|
11/10 Wed
|
L17. Viewing algorithms as languages,Algorithmic
Decision
Problems:ATM,ACFG,
AREX,ETM, etc
|
|
|
|
11/15 Mon
|
L18. Incomputable Languages: Existence of
Incomputable Languages; Cantor's
Diagonalization Argument; Undecidability
ofATM, ETM,
EQTM; ALLTM
|
4.2
|
HW4
|
|
11/17 Wed
|
L19. More Undecidable Problems:
Reducibility:Turing reducible, Mapping
reducible,Co-mapping reducible; Beyond
undecidable
|
Chp. 5
|
|
|
11/22 Mon
|
MIDTERM 2 -covers HW3 and HW4
|
7.1
|
|
|
11/24 Wed
|
L20. Complexity: Running time,
Big-Oreview, The class P,
Efficiency ofTM's, Encoding Input/Output as
Yes/No(e.g. Factoring numbers), Context
freelanguages are in P and CYKalgorithm
CC
|
7.2
|
|
|
11/29 Mon
|
L21. The Class NP: Nondeterministiccomplexity:
poly-time NTM's, poly-timeVerifiers, poly-size
proofs; Punch-CardPuzzle, SAT and variants,
class Co-NP;Polynomial time reductions
|
7.3
|
|
|
12/1 Wed
|
L22. NP-complete problems; P vs. NP
OpenProblem: Known and unknown
hierarchies;Nondeterministic complexity
|
7.4
|
HW5
|
|
12/6 Mon
|
L23.The Cook-Levin Theorem: Showing that CSAT
is NP-hard, Reducing CSAT to 3SAT.
|
7.5
|
|
|
12/8 Wed
|
L24. Catch-up
|
|
HW6
|
|
12/13 Mon
|
FINAL EXAM - in class - cumulative |
|
|
