| TCOM Theory of Computation - CTY Lancaster 2007 Session 1 - Kayla Jacobs & Adam Groce | ||||||
| Monday | Tuesday | Wednesday | Thursday | Friday | ||
| Week 1 | Morning | * Introduction * Deterministic Finite Automata (DFAs) * Basic set theory |
*
Nondeterministic Finifte Automata (NFAs) * More set theory |
* Regular expressions = NFAs proof | * Pigeonhole
principle * Pumping lemma for regular languages |
* Pushdown
Automata (PDAs) * Problems |
| Afternoon | * Proofs and higher math | *
Regular expressions * Problems |
*
Basic combinatorics * Change of bases |
* Problems | * Problems | |
| Evening | * Problems | *
Problems * DFAs = NFAs proof |
* Problems | *
Context-Free Grammars (CFGs) * Problems |
Sunday
evening: * Problems |
|
| Week 2 | Morning | * Proof by
induction * Problems |
*
Orders of growth * Problems |
* Algorithms | * Problems | * Undecidable languages |
| Afternoon | * PDAs = CFGs proof | *
Pumping lemma for context-free languages * Problems |
*
Turing machines (TMs) * Church-Turing thesis * TM variations |
* ATM is undecidable diagonalization proof | *
Polynomial-time reducibility * Problems |
|
| Evening | * Countability and uncountability | * Problems | * Problems | * Post Correspondence Problem | Sunday
evening: * Time complexity * P * Logarithms |
|
| Week 3 | Morning | * NP * NP-completeness * SAT is NP-complete |
* More NP-complete languages | * Review * Review problems |
* Catalan numbers | * Course wrap-up |
| Afternoon | * Problems |
* Survey of complexity theory's current status | * Review problems | * Quantum computing | ||
| Evening | * Problems * HAM-PATH is NP-complete |
* National Plumbers Association skit | * Examination | *
Approximation algorithms * Decidability of logical systems |
||