COM S 381 - Introduction to Theory of Computing
COM S 381: Introduction to Theory of Computing
Summer 2007
- Instructor:
- James Worthington: worthing@cs.cornell.edu
- Office:
- 112 Malott
- Classes:
- MTWRF 8:30 - 9:45, Upson 207
- Office hours:
- Mo,Th 10:30-11:30
- Schedule:
- May 21 - Introduction (Chapter 1)
- May 22 - Deterministic Finite Automata (2.1, 2.2)
- May 23 - Nondeterministic Finite Automata (2.3, 2.4)
- May 24 - Finite Automata with Epsilon-Transitions (2.5)
- May 25 - Regular Expressions and Finite Automata (3.1 - 3.3)
- May 28 - Regular Expression cont'd, Algebraic Laws for Regular Expressions (3.3, 3.4)
- May 29 - The Pumping Lemma (4.1)
- May 30 - Closure Properties of Regular Languages, Decision Properties of Regular Languages (4.2, 4.3)
- May 31 - Equivalence and Minimization of Automata (4.4)
- June 1 - The Myhill-Nerode Theorem (Kozen, Lectures 15,16)
- June 4 - Context-Free Grammars (5.1)
- June 5 - Parsing (5.2, 5.3)
- June 6 - Pushdown Automata (6.1, 6.2)
- June 7 - Equivalence of PDA's and CFG's (6.3)
- June 8 - Midterm (on material May 21 - June 6)
- June 11 - Determinisitic Pushdown Automata (6.4)
- June 12 - Normal Forms for Context-Free Grammars (7.1)
- June 13 - Pumping Lemma for Context-Free Grammars (7.2)
- June 14 - Closure Properties and Decision Properties of Context-Free Languages (7.3, 7.4)
- June 15 - Decision Properties of Context-Free Languages cont'd, The CKY algorithm (7.4)
- June 18 - Introduction to Turing Machines (8.1, 8.2)
- June 19 - Equivalent Models (8.4, 8.5)
- June 20 - Decidability, Reduction, Universality (9.1-9.3)
- June 21 - Decidability, Reduction, Universality cont'd (9.1 - 9.3)
- June 22 - Post's Correspondence Problem (9.4)
- June 25 - Mu-recursion and the Lambda Calculus (Kozen, Lectures 36, 37)
- June 26 - Gödel's Incompleteness Theorem (Kozen, Lectures 38, 39, K)
- June 27 - Gödel's Incompleteness Theorem, cont'd. (Kozen, Lectures 38, 39, K)
- June 28 - Review
- June 29 - Final Exam (cumulative)
- Assignments:
- Prerequisite:
- COM S 280 or equivalent.
- Text:
- Introduction to Automata Theory, Languages, and Computation (Hopcroft, Motwani, and Ullman).
A few of the lectures will be based on material from Automata and Computability (Kozen). Both books
are on reserve in the Engineering Library.
- Grading:
- Homework is due at the beginning of class. No late homework will be accepted. Homework
will comprise 50% of your grade, the midterm 20%, and the final exam 30%.
- Collaboration Policy:
- Discussion and collaboration is encouraged, however, every student must write up his/her own solutions.