Lecture Schedule for CS 4510: Automata and Complexity

Lecture Schedule

[Jan 11: Lecture 1]
Introduction. Alphabets, Languages, Star operation. Example of a DFA.
Reading: Chapter 0. Section 1.1 (through page 37)
[Jan 13: Lecture 2]
DFA's. More examples of DFA's. Regular Languages. Regular Operations. Regular Languages closed under union.
Reading: Section 1.1
[Jan 15: Lecture 3]
Finish closure under union. Nondeterminism. NFA's. Examples of NFA's. Equivalence of NFA's and DFA's.
Reading: Section 1.2 (through page 58)
[Jan 20: Lecture 4]
Closure under regular operations. Regular Expressions. Equivalence with Finite Automata (one direction).
Reading: Sections 1.2, 1.3 (through page 67)
[Jan 22: Lecture 5]
Equivalence of Regular Expressions and Finite Automata. Pumping Lemma--statement.
Reading: Sections 1.3, 1.4 (through page 78)
[Jan 25: Lecture 6]
Pumping Lemma. Myhill-Nerode Theorem.
Reading: Section 1.4, Online notes for Myhill-Nerode theorem.
[Jan 27: Lecture 7]
Context Free Grammar. Ambiguity. Chomsky Normal Form. Equivalence of CFG and CNF.
Reading: Section 2.1, Online notes for Ambiguity, Empty rules and Unit rules.
[Jan 29: Lecture 8]
Cocke-Younger-Kasami Algorithm. Closure of CFL's under regular operations.
Reading: Theorem 7.16 (pp. 262-263), Online notes for CYK Algorithm.
[Feb 1: Lecture 9]
Pushdown automata. Various Normalizations of PDA's.
Reading: Section 2.2 (through page 116)
[Feb 3: Lecture 10]
Equivalence of CFG and PDA.
Reading: Section 2.2
[Feb 5: Lecture 11]
Pumping Lemma for CFL's. CFL's are not closed under intersection and complement.
Reading: Section 2.3
[Feb 8: Lecture 12]
Turing Machines. Decidability. Recognizability. Examples.
Reading: Section 3.1
[Feb 10: Lecture 13]
Multitape TM. Equivalence to single tape. Nondeterministic TM.
Reading: Section 3.2 (through page 150), A short note on two questions asked in class.
[Feb 12: No Lecture]
Snow day! Georgia Tech campus closed at 2:30 pm.
Reading: Your favorite book.
[Feb 15: Lecture 14]
NTM examples. Equivalence of NTM and DTM. Church-Turing Thesis.
Reading: Sections 3.2, 3.3 (through page 155), Online notes for NTM simulation.
[Feb 17: Lecture 15]
Algorithms. Decidability. A_DFA, E_DFA, EQ_DFA, A_CFG, E_CFG.
Reading: Sections 3.3, 4.1
[Feb 19: Lecture 16]
Halting Problem or A_TM. Diagonalization. A_TM is undecidable.
Reading: Section 4.2 (through page 179)
[Feb 22: Lecture 17]
A_TM is undecidable. Mapping reducibility. Reductions. Examples. HALT_TM.
Reading: Sections 4.2, 5.1 (through page 189), 5.3
[Feb 22: Review Session]
At 6:00 pm, Klaus 1447. Please come with questions.
Reading: Chapters 1, 2, 3.
[Feb 24: Midterm 1]
Reading: Chapters 1, 2, 3.
[Feb 26: Lecture 18]
HALT_TM, E_TM, EQ_TM, REGULAR_TM. Computation histories.
Reading: Sections 5.1 (through page 193), 5.3. Online notes on reductions.
More notes on reductions
[Mar 1: Lecture 19]
ALL_CFG is undecidable. PCP.
Reading: Section 5.1, 5.2 (through page 200). Online notes on computation histories, the undecidability of ALL_CFG and PCP.
[Mar 3: Lecture 20]
PCP is undecidable. Applications.
Reading: Section 5.2. Online notes on PCP and an example.
[Mar 5: Lecture 21]
Rice's Theorem. Example of reductions. Running time. O notation.
Reading: Problems 5.14, 5.28. Section 7.1 (through page 251)
[Mar 8: Lecture 22]
The class P. Examples of languages in P.
Reading: Section 7.2
[Mar 10: Lecture 23]
The class NP. Examples of languages in NP. Equivalence with verifier model.
Reading: Section 7.3
[Mar 12: Lecture 24]
NP-completeness. Poly-time reductions. Examples of reductions. Cook-Levin Theorem (statement).
Reading: Section 7.4 (through page 276)
[Mar 15: Lecture 25]
Proof of Cook-Levin Theorem.
Reading: Section 7.4 (through page 280)
[Mar 17: Lecture 26]
Conclude Cook-Levin Theorem. 3-SAT, CLIQUE is NP-complete.
Reading: Section 7.4, Online notes on valid windows in Cook-Levin Theorem.
[Mar 19: Lecture 27]
More NP-complete problems. VERTEX-COVER, HAM-PATH.
Reading: Section 7.5 (through page 290)
[Mar 20 - Mar 28 : Spring Break]
Have a good break!
[Mar 29: Lecture 28]
More NP-complete problems. UHAM-PATH, SUBSET-SUM.
Reading: Section 7.5
[Mar 31: Lecture 29]
KNAPSACK, 0/1 ILP. The class co-NP and co-NP completeness.
Reading: Online notes from Tsinghua and Cornell.
[Apr 2: Lecture 30]
Polynomial Hierarchy.
Reading: Online notes from Tsinghua and Cornell.
More notes: A chapter from Arora and Barak's book.
[Apr 5: Lecture 31]
Space Complexity. DSPACE(f(n)), NSPACE(f(n)). Relations with time bounded complexity classes.
Reading: Sections 8.0, 8.4
[Apr 7: Lecture 32]
NL-completeness, Logspace Reductions. PATH.
Reading: Section 8.5
[Apr 9: Lecture 33]
Savitch's Theorem. NL = co-NL.
Reading: Sections 8.1, 8.6, Online notes on NL = co-NL.
[Apr 12: Lecture 34]
Revise NL = co-NL. Review for midterm 2.
Reading: Section 8.6, Online notes on NL = co-NL, Chapters 4, 5, 7
[Apr 14: Midterm 2]
Reading: Chapters 4, 5, 7.
[Apr 16: Lecture 35]
Finish NL = co-NL. PSPACE.
Reading: Sections 8.6, 8.2, Online notes on NL = co-NL.
[Apr 19: Lecture 36]
PSPACE Completeness, TQBF is PSPACE complete.
Reading: Section 8.3 (through page 313)
[Apr 21: Lecture 37]
Formula Game, Generalized Geography is PSPACE complete.
Reading: Section 8.3 (through page 318)
[Apr 23: Lecture 38]
Generalized Geography is PSPACE complete, Introduction to Communication Complexity.
Reading: Section 8.3
[Apr 26: Lecture 39]
Communication Complexity of Equality. Deterministic lower bound. O(log n) randomized algorithm.
Reading: Chapter 13 Arora-Barak. Draft available here. Online notes on O(log n) algorithm.
[Apr 28: Lecture 40]
Lower bound techniques: Tiling with Monochromatic Rectangles.
Reading: Arora-Barak draft.
[Apr 30: Lecture 41]
Rank Lower Bound. Conclusion. Review for class. Donuts.
Reading: Arora-Barak draft, Sipser Chapters 1, 2, 3, 4, 5, 7, 8.
[May 3: Final Exam]
Reading: Chapters 1, 2, 3, 4, 5, 7, 8.

This page was last modified on .