| Lec. | Date | Topics | Reading | Homework, exams and handouts |
|---|
| 1 | Mon, Jan 14 | Introduction, finite automata | Chapters 0-1.1 | General Course Information
|
| 2 | Wed, Jan 16 | Regular operations, nondeterminism, closure properties, regular expressions | Chapters 1.2-1.3 | HW 1 out
|
| 3 | Wed, Jan 23 | Closure properties, equivalence of DFAs and regular expressions, pumping lemma for regular languages | Chapters 1.2-1.4 | HW1 due, HW 2 out
|
| 4 | Mon, Jan 28 | Context-free grammars and pushdown automata | Chapters 2.1-2.2 |
|
| 5 | Wed, Jan 30 | Equivalence of CFGs and PDAs, pumping lemma for context-free languages | Chapters 2.2-2.3 | HW2 due, HW 3 out
|
| 6 | Fri, Feb 1
at 10:30am in IST 333
|
Make up lecture:
Finish pumping lemma for CFLs. Turing machines
Extra office hours: 4pm-5pm
| Chapters 3.1-3.3 |
|
| Mon, Feb 4 |
Lecture and office hours are cancelled
| |
|
| Wed, Feb 6 |
Lecture is cancelled. Slip HW3 under my office door
| Chapters | HW3 due, HW 4 out
|
| 7 | Mon, Feb 11 | TM variants. Enumerators. | Chapters 3.2-3.3 | You can resubmit optional problem on HW3 with HW4
|
| 8 | Wed, Feb 13 | Decidable languages. Review. | Chapter 4.1 | HW4 due at 11:59am on Thursday
|
| 9 | Mon, Feb 18 | Undecidability. Halting problem. Diagonalization. | Chapters 4.2, 5.1 |
Exam 8:15-10:15pm in 103 Walker, Chapters 0-4.1
|
| 10 | Wed, Feb 20 | Mapping reducibility. Turing-unrecognizable languages. | Chapters 5.1, 5.3 | HW 5 out
|
| 11 | Fri, Feb 22 at 10:30am in IST 333
|
Make up lecture: Computation history metod. Undecidability of E_LBA and POST | Chapters 5.1, 5.2 |
|
| 12 | Mon, Feb 25 | Computation history metod: undecidability of ALL_PDA. Recursion Theorem | Chapters 5.1, 6.1 |
|
| 13 | Wed, Feb 27 | Problem solving session | | HW5 due, HW 6 out
|
| 14 | Mon, Mar 3 | Asymptotic notation; measuring complexity | Chapter 7.1 |
|
| 15 | Wed, Mar 5 | Complexity relationships among models. Class P. | Chapter 7.2 | HW6 due, HW 7 out
|
| Mar 10-14 | Have a good spring break! |
|
| 16 | Mon, Mar 17 | Class NP | Chapters 7.3-7.4 |
|
| 17 | Wed, Mar 19 | NP-completeness. Cook-Levin Theorem | Chapter 7.4 | HW7 due, HW 8 out
|
| 18 | Mon, Mar 24 | Examples of NP-complete problems | Chapter 7.5 |
|
| 19 | Wed, Mar 26 | Review and problem solving | | HW8 due
|
| 20 | Mon, Mar 31 | Savitch's Theorem | Chapters 8.1 |
Exam 8:15-10:15pm in 103 Walker
|
| 21 | Wed, Apr 2 | PSPACE and PSPACE-completeness | Chapters 8.2 | HW 9 out
|
| 22 | Mon, Apr 7 | PSPACE-completeness. Problem solving session. | Chapters 8.3 |
|
| 23 | Wed, Apr 9 | L and NL. NL-completeness | Chapters 8.4-8.5 | HW9 due, HW 10 out
|
| 24 | Mon, Apr 14 | NL-completeness. NL=coNL | Chapters 8.5-8.6 |
|
| 25 | Wed, Apr 16 | Hierarchy theorems | Chapter 9.1 | HW10 due, HW 11 out
|
| 26 | Mon, Apr 21 | Oracles and relativization | Chapter 9.2 |
|
| 27 | Wed, Apr 23 | | Chapters | HW11 due, HW12 out
|
| 28 | Mon, Apr 28 | | Chapters |
|
| 29 | Wed, Apr 30 | | Chapters | HW12 due
|
| Mon, May 5 | Final exam 10:30am-1:30pm, IST 333 |
|