Announcments
- Class begins January 21.
- Class textbook:
Introduction
to the Theory of Computation, Second Edition
by Mike Sipser.
- Practicum is CSC 402-01, one credit.
It is optional and will cover more language and compiler issues in a sequence of 3 or 4
projects.
- The grader is Wenghui Lin. linwh0520 _at_ hotmail.com
- Papers handed in hard copy in class, Mondays. Returned Fridays.
- Late papers are accepted for reduced credit.
- Writing credit given. Essay assignments for writing credit
are not counted in letter grade.
- This is opt-out Writing Credit, let me know
if you do not want Writing Credit.
- Final grade is 30% homeworks, 20% first test, 20% second test, 30% final.
- First Test: Monday, Feb 23
- First Test Histogram
- Second Test: Friday April 3
- Second Test Histogram
- Final: Monday, May 11, 8:00--10:30 AM.
Full exam schedule (PDF)
- Calendar
Syllabus Post Hoc
- Jan 21: Introduction, notation, proofs.
- Jan: Deterministic Finite Automata.
- Jan: Non-deterministic Finite Automata.
- Feb 4: Theorem 1.39, the equivalence of DFA and NFA.
- Feb 6: Theorems 1.45, 47 and 49. Definition of Regular Expressions.
- Feb 9: Equivalence of NFA's and Regex's, GNFA's, Theorem 1.54.
- Feb 11: Pumping lemma, Theorem 1.70.
- Feb 16: Context free languages
- Feb 18: Chomsky Normal Form
- Feb 20: Push down automata.
- Feb 23: **Test**
- Mar 2: Equivalence of PDA and CFG's
- Mar 6: Pumping lemma for CFL's
- Mar 9: Turing machines
- Mar 13: Enumerators, Hilberts 10-th problem
- Mar 16-20: Spring break.
- Mar 23: Decidability chapter 4
- Mar 27: Countable and uncountable infinities
- Mar 30: The Halting Problem
- Apr 1: Undecidabilty and reductions, chapter 5.
- Apr 3: **Test**
- We do not cover the second half of 5.1 and 5.2
- Apr 6: Reductions, time complexity, chapter 7.
- We do not cover chapter 6.
- Apr 13: The class P.
- Apr 15: The class NP.
- Apr 20: Reductions.
- Apr 22: NP completeness, Cook-Levin
- Apr 24: Cook-Levin, concluded
- Apr 27: NP complete problems
- Apr 29: NP complete problems
- Mayday: Randomized complexity, IP, Zero-knowledge.
Assignments
-
Exercises: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7;
Problems: 0.12, 0.14;
Due: Feb 2, 2009.
-
Exercises: 1.6, 1.7, 1.8, 1.9, 1.10, 1.12;
Problems: 1.32, 1.37, 1.43, 1.51, 1.52;
Due: Feb 9, 2009.
-
Exercises: 1.5, 1.13, 1.14, 1.18, 1.20, 1.28, 1.29;
Problems: 1.46, 1.49, 1.53, 1.54;
Due: Feb 16, 2009.
-
Exercises: 2.1, 2.2, 2.4, 2.5, 2.8, 2.9.
Problems: 2.25.
Due: 2 March
-
Exercises: 2.11, 2.12, 2.14, 2.16.
Problems: 2.20, 2.30, 2.31.
Due: 9 March
-
Exercises: 3.1, 3.2, 3.5, 3.6, 3.7, 3.8.
Problems: 3.11, 3.15, 3.16, 3.21.
Due: 23 March
-
Exercises: 4.3, 4.5, 4.6, 4.7
Problems: 4.10, 4.12, 4.15, 4.16
Due: 30 March
-
Exercises: 5.1, 5.2
Problems: 5.9
Extra Credit: 5.16 (For this problem, look on internet for known values of BB(n).)
Due: April 6
-
Exercises: 7.1, 7.2, 7.3.
Problems: 7.12, 7.13 (permutation notation hint)
Due: April 13
-
Exercises: 7.4, 7.5, 7.6, 7.7, 7.8, 7.9.
Problems: 7.14, 7.15.
DueL April 20
-
Exercises: 7.11.
Problems: 7.16, 7.17, 7.19, 7.20, 7.21.
Due: April 27
-
Problems: 7.26, 7.27, 7.28.
Due: May 1
Essays
- Write an essay on an early automaton. Example topics:
or whatever else you can come up with. I would emphasize the historical side, when, and what
people thought of it. Other topics welcome, especially unusual examples of early automata.
Three page double spaced is fine.
Due: 6 March.
- Write an essay about the day after P is discovered to be equal to NP.
Oddly, nothing actually changes, since a proof does not establish truth, only
makes a truth believed, or be known. Regardless of that caveat, what would be the
consequences of now viewing the world through P=NP glasses?
The essay can be fiction or non-fiction.
Due: 1 May.
Practicum
- The first assignment will be a regular expression parser.
Details here.
Due: 6 March.
- A Turing Machine simulator.
Details here.
Due: 1 May.
References