Theory of Computation (TCOM)

DFA
Johns Hopkins Center for Talented Youth (JHU-CTY) summer program
Franklin & Marshall College, Lancaster, PA
35 class hours/week for 3 weeks (June 24 - July 20, 2007)
Aimed at bright 8-10th graders without prior experience with formal mathematics or computer science
Co-instructors: Kayla Jacobs and Adam Groce. Contact them at cty-tcom2007 *AT* mit *DOT* edu

Beyond basic computer literacy lies a deeper understanding of computational power. We worked with a series of mathematical models of computation -- deterministic and nondeterministic finite automata (DFAs and NFAs), push-down automata (PDAs), and finally Turing machines (TMs) -- to better understand the strengths and limitations of actual computers. Turning then from the question of what computers can do to how quickly they can do it, we explored the field of complexity theory through analyses of algorithm run-times, NP-completeness and the famous "Does P=NP?" question. The course concluded with a survey of advanced topics such as quantum computing, approximation algorithms, and Godel’s Incompleteness Theorem. Mathematical fluency and maturity were emphasized heavily throughout the course, incorporating formal set theory, counting arguments, and proof techniques like induction and Cantor diagonalization -- all both for their applicability to the subject matter and for their own mathematical sake.

Unofficial course textbook: Sipser, Michael. Introduction to the Theory of Computation, 2nd ed. Boston, MA: Thomson Course Technology, 2006 (ISBN: 0534950973).


TCOM Calendar at a Glance

Click on a day to skip to the associated materials
Sunday
(evening only)
Monday
Tuesday
Wednesday
Thursday
Friday
* General info
* Pre-test
* Introduction
* Deterministic finite automata (DFAs)
* Set theory
* Proofs & higher math
* Nondeterministic finite automata (NFAs)
* Set theory II
* Regular expressions
* DFAs = NFAs proof
* Regular expressions = NFAs proof
* Combinatorics
* Change of bases
* Pigeonhole principle
* Pumping lemma for regular languages
* Context-free grammars (CFGs)
* Pushdown automata (PDAs)
* Challenge problems * Induction proofs
* PDAs = CFGs proof
* Countability & uncountability
* Orders of growth
* Pumping lemma for CFLs
* Algorithms
* Turing Machines (TMs)
* Church-Turing thesis
* TM variations
* ATM is undecidable
* Post Correspondence Problem (PCP)
* Undecidable languages
* Polynomial-time reducibility
* Time complexity
* Polynomial time (P)
* Logarithms
* Nondeterministic polynomial time (NP)
* NP-completeness
* SAT is NP-complete
* HAM-PATH is NP-complete
* More NP-complete languages
* Complexity theory today
* National Plumbers Association skit
* Review
* Examination
* Catalan numbers
* Quantum computing
* Approximation algorithms
* Decidability of logical systems
* Wrap-up

Creative Commons License You're encouraged to use these materials for your own learning or teaching.
Creative Commons Attribution-Noncommercial-Share Alike 3.0 License.

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:
  • Pushdown automata (PDAs)
Problems:
  • CFL & PDA problems (pdf, doc)

[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:
  • Algorithms 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:
  • Review
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:
  • Course wrap-up
Readings & Handouts:
  • Solutions to challenging problems ()
  • Further Explorations in TCOM Recommendations (pdf, doc)

[Back to calendar]


Creative Commons License You're encouraged to use these materials for your own learning or teaching.
Creative Commons Attribution-Noncommercial-Share Alike 3.0 License.

Contact the instructors at cty-tcom2007 *AT* mit *DOT* edu