| | |
| September 3: |
Course Overview |
slides |
notes |
| September 5: |
Induction and Strings |
slides |
| September 8: |
Deterministic Finite Automata (DFAs) |
Not available yet |
| September 10: |
Regular Languages |
slides |
| September 12: |
Non-deterministic Finite Automata (NFAs) |
slides |
latex source |
| September 15: |
Equivlance of NFAs and DFAs |
slides |
| September 17: |
Regular Expressions = Finite Automata |
slides |
| September 19: |
Regular Expressions and Non-Regular Languages |
slides |
| September 22: |
The Pumping Lemma |
slides |
| September 24: |
Context Free Languages |
slides |
| October 3: |
Pumping Lemma for CFLs |
slides |
| October 6: |
Regular Language Review |
notes |
| October 17: |
Introduction to Turing Machines |
slides |
| October 20: |
Fun with Turing Machines |
slides |
| October 22: |
Turing Machine Variants |
slides |
| October 24: |
Decidability |
slides |
| October 27: |
Universal Turing Machines and Diagonalization |
slides |
| October 29: |
The Halting Problem for Turing Machines |
slides |
| October 31: |
Reductions |
slides |
| November 3: |
Midterm Review |
no slides |
| November 5: |
Midterm 2 |
questions |
answers |
| November 7: |
Reductions Redux |
slides |
| November 10: |
Computational Histories |
slides |
| November 12: |
The Post Correspondence Problem |
slides |
| November 14: |
Time Complexity, P and NP |
slides |
| November 17: |
The Cook-Levin Theorem |
slides |
| November 24: |
Cryptography |
slides |
| November 26: |
More NP-Completenss Examples |
slides |
| November 28: |
Research Advertisement |
slides |