Sunday Week 1 (evening only)
|
- Welcome Letter ()
- Course Description (pdf, doc)
- Calendar (page link)
- Survey ()
- Pre-assessment test ()
- Daily Student Feedback Form (pdf, doc)
[Back to calendar]
|
Monday Week 1
|
Topics:
- Introductions
- Deterministic finite automata (DFAs)
- Set theory
- Proofs and higher math
Readings & Handouts:
- DFA Summary ()
- Moore's automaton recognizing leap years (page link)
- Designing finite automata (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, pp. 41-43)
- Definitions, theorems, proofs (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, Introduction to the Theory of Computation, 2nd edition, pp. 17-22)
Problems:
- Begin: Set theory problems (pdf, doc) & solutions (pdf, doc)
- DFA problems ()
- Proofs problems (pdf, doc)
[Back to calendar]
|
Tuesday Week 1
|
Topics:
- Nondeterministic finite automata (NFAs)
- Set theory II
- Regular expressions
- DFAs = NFAs proof
Readings & Handouts:
- Every NFA has an equivalent DFA (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, Theorem 1.39, pp. 55-56)
Problems:
- NFA problems ()
- Complete from previous day: Set theory problems (pdf, doc) & solutions (pdf, doc)
- Regular expressions (pdf, doc)
[Back to calendar]
|
Wednesday Week 1
|
Topics:
- Regular expressions = NFAs proof
- Combinatorics
- Change of bases
Problems:
- Combinatorics problems (pdf, doc)
- Fun with bases problems ()
[Back to calendar]
|
Thursday Week 1
|
Topics:
- Pigeonhole principle
- Pumping lemma for regular languages
- Context-free grammars (CFGs)
Readings & Handouts:
- The pumping lemma as a poem (page link)
- Pumping lemma summary ()
- Tips for picking a good s (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, p. 80)
- Natural languages, programming languages, algebraic expressions, and others ()
Problems:
- Pumping lemma problems ()
- CFG problems ()
[Back to calendar]
|
Friday Week 1
|
Topic:
Problems:
[Back to calendar]
|
Sunday Week 2 (evening only)
|
Problems:
- Week 1 challenge problems ()
[Back to calendar]
|
Monday Week 2
|
Topics:
- Proof by induction
- PDAs = CFGs proof
- Countability and uncountability
Readings & Handouts:
- Proof by induction (pdf, doc)
- Equivalence with context-free grammars (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, pp. 115-122)
- Hotel Infinity (Martin Gardner, Aha! Gotcha: Paradoxes to Puzzle and Delight, pp. 50-51)
- The ladder of alephs (Martin Gardner, Aha! Gotcha: Paradoxes to Puzzle and Delight, pp. 52-53)
Problems:
- Proof by induction problems (pdf, doc)
[Back to calendar]
|
Tuesday Week 2
|
Topics:
- Orders of growth
- Pumping lemma for context-free languages (CFLs)
Readings & Handouts:
- Table comparing several polynomial and exponential time complexity functions (Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Figure 1.2, p. 7)
- Table comparing effect of improved technology on several polynomial and exponential time algorithms (Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Figure 1.3, p.8)
Problems:
- Orders of growth problems ()
- CFL pumping lemma problems ()
[Back to calendar]
|
Wednesday Week 2
|
Topics:
- Algorithms
- Turing machines (TMs)
- Church-Turing thesis
- TM variations
Readings & Handouts:
- Selections from Wikipedia's sorting algorithms entry (page link)
Problems:
[Back to calendar]
|
Thursday Week 2
|
Topics:
- ATM is undecidable diagonalization proof
- Post Correspondence Problem (PCP)
Readings & Handouts:
- Index of example languages in Sipser's book ()
- PCP is undecidable (Michael Sipser, Introduction to the Theory of Computation, 2nd edition, Theorem 5.15, pp. 200-205)
[Back to calendar]
|
Friday Week 2
|
Topics:
- Undecidable languages
- Polynomial-time reducibility
Readings & Handouts:
- Decidable and undecidable languages summary ()
Problems:
- Decidability problems (pdf, doc)
- Undecidability problems (pdf, doc)
[Back to calendar]
|
Sunday Week 3 (evening only)
|
Topics:
- Time complexity
- Polynomial time decidable languages (P)
- Logarithms
Readings & Handouts:
- Rules for exponents and logarithms (pdf, doc)
Problems:
- Logarithms problems (pdf, doc)
[Back to calendar]
|
Monday Week 3
|
Topics:
- Nondeterministic polynomial time decidable languages (NP)
- NP-completeness
- SAT is NP-complete
- HAM-PATH is NP-complete
Readings & Handouts:
Problems:
- P & NP problems (pdf, doc)
- NP-completeness problems ()
[Back to calendar]
|
Tuesday Week 3
|
Topics:
- More NP-complete languages
- Survey of complexity theory's current status
- National Plumbers Association skit
Readings & Handouts:
- The History of the National Plumbers Association ()
Problems:
- National Plumbers Association Telephone Operator Exam ()
[Back to calendar]
|
Wednesday Week 3
|
Topic:
Readings & Handouts:
- Math review (pdf, doc)
- Computability theory review (pdf, doc)
- Complexity theory review (pdf, doc)
Problems:
- Math review problems (pdf, doc)
- Computability theory review problems (pdf, doc)
- Turing machines & complexity theory review problems (pdf, doc)
[Back to calendar]
|
Thursday Week 3
|
Topics:
- Catalan numbers
- Quantum computing
- Approximation algorithms
- Decidability of logical systems
Problems:
- Catalan numbers ()
- Quantum key exchange protocol activity ()
[Back to calendar]
|
Friday Week 3
|
Topic:
Readings & Handouts:
- Solutions to challenging problems ()
- Further Explorations in TCOM Recommendations (pdf, doc)
[Back to calendar]
|