| Date |
Material |
Reading |
| 8/28 |
Introduction to the course, math background (sets, tuples, functions & relations,
graphs, strings and languages, boolean logic |
Chapter - paragraphs 0.1, 0.2 |
| 9/2 |
Math background (Proofs: by construction, by contradiction,
by induction, counterexamples) |
Chapter 0 - paragraphs 0.3, 0.4 |
| 9/4 |
DFAs (what is a dfa, formal definition of a dfa, examples of dfa, designing dfa) |
Chapter 1 - paragraph 1.1 until page 43 |
| 9/9 |
Exercises, Minimum DFA |
Notes on minimum dfa |
| 9/11 |
NFA, NFAε, NFA - DFA equivalence |
Chapter 1 - paragraph 1.2 |
| 9/23 |
Exercises on NFA-DFA equivalence and minimizing DFAs |
Chapter 1 - paragraph 1.2, notes on minimizing DFAs |
| 9/25 |
Regular Operations, Regular Languages and Closure under Reg. Op., Regular Expressions,
equivalence with FA |
Chapter 1 - paragraphs 1.1 (pages 44 - 47), 1.2 (pages 58 - 63), 1.3 |
| 10/2 |
Exercises - Review on Chapter 1 |
Chapter 1 - paragraphs 1.1-1.3, notes on minimum dfa |
| 10/7 |
Test I (on Finite Automata and Regular Expressions) |
Chapter 1 - paragraphs 1.1-1.3, notes on minimum dfa |
| 10/16 |
Regular and Context Free Grammars, Ambiguity, Chomsky Normal Form, Equivalence
of Regular Grammars with FA |
Chapter 2 - paragraph 2.1, notes on equivalence of Reg. Gr. with FA |
| 10/21 |
Exercises, The CYK Algorithm |
Chapter 2 - paragraph 2.1, notes on the CYK algorithm |
| 10/23 |
Designing Pushdown Automata |
Chapter 2 - paragraph 2.2 |
| 10/28 |
Exercises, Formal definition of PDAs, DPDA & NPDA |
Chapter 2 - paragraph 2.2 |
| 10/30 |
Turing Machines, the Chomsky Hierarchy, Church-Turing Thesis |
Chapter 3 - paragraph 3.1, notes on the Chomsky Hierarchy |
| 11/4 |
Exercises on PDAs |
Chapter 3 - paragraph 3.1 |
| 11/6 |
Turing Machines , TMs with output and computable functions |
Chapter 3 - paragraph 3.1 |
| 11/11 |
(Partially) Computable predicates, (partially) computable languages, the Chomsky Hierarchy,
undecidability (halting problem), the Turing-Church's thesis |
Notes on computable and partially computable langiages (instead of Chapter 4) |
| 11/13 |
Review |
Chapters 1, 2, 3, 4, notes |
| 11/18 |
Test II (on Pushdown Automata and Turing Machines) |
Chapters 2, 3 notes |
| 11/20 |
DTM - NTM equivalence O-notation |
Chapter 7 - paragraph 7.1 |
| 11/25 |
Exercises on O-notation, Time Complexity, the P class, reductions |
Chapter 7 - paragraph 7.2 |
| 12/2 |
Exercises on P, the NP class |
Chapter 7 - paragraph 7.3 |
| 12/4 |
reductions, NP-completeness |
Chapter 7 - paragraphs 7.4, 7.5 |
| 12/9 |
Exercises on NP-completeness, Review (mostly on Complexity Theory) |
Chapter 7, notes on additional NP-C problems |
| 12/23 |
Final Exam |
Chapters 1, 2, 3, 4, 7, notes |