| Welcome |
|
Professor: Dr. Layne T. Watson Office: 2000 Torgersen Graduate Teaching Assistant: Name: Monika Akbar |
| Syllabus |
Here are two printable versions of the official syllabus: in PostScript and in PDF. The following is an abbreviated version for your convenience.
CS4124 Theory of Computation MWF 10:10–11:00 MCB 238 CRN 91766
Instructor: L. T. Watson, 2000 Torg, 231-7540, ltw@cs.vt.edu
Office Hours: 09:00–10:00 MWF, and by appointment.
Prerequisites: Math 3134 or Math 3034.
Text: J. E. Savage, Models of Computation Addison-Wesley, 1998. Printed textbook corrections. Corrected online edition.
Topics Covered:
Logic circuits, Boolean function normal forms, prefix computations, arithmetic, circuit complexity, finite-state machines, random-access machines, Turing machines, simulation, pushdown automata, regular and context-free languages, models of computability, reducibility and insolvability, recursive function theory, parallel computation, space-time tradeoffs.
Grading: FINAL GRADE will be the average of two in-class exams (50%), a final examination (25%), and homework and class participation (25%). All questions regarding grades must be raised within three days of the date the assignment is returned.
Final Exam: 13:05--15:05 Friday, Dec. 12, 2008.
References:
Clark and Cowell, Programs, Machines, and Computation, McGraw Hill, 1976. D. I. A. Cohen, Introduction to Computer Theory, 2nd Ed., Wiley, 1997. Davis, Sigal, and Weyuker, Computability, Complexity, and Languages, 2nd Ed., Academic Press, 1994. Denning, Dennis, Qualitz, Machines, Languages, and Computation, Prentice-Hall, 1978. Gill, Introduction to the Theory of Finite State Machines, McGraw-Hill, 1962. Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Kain, Automata Theory, Machines, and Languages, McGraw-Hill, 1972. Kfoury, Moll, Arbib, A Programming Approach to Computability, Springer-Verlag, 1982. Manna, Mathematical Theory of Computation, McGraw-Hill, 1974. McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967. B. M. Moret, The Theory of Computation, Addison-Wesley, 1998. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. R. G. Taylor, Models and Computation and Formal Languages, Oxford, 1998.
| Assignments |
All problems are from the text unless otherwise indicated. All questions regarding grades must be raised within three days of the date the assignment is returned. See the syllabus files linked above for problem point values.
Due 08/29/08 1.3, 1.5, 1.10, 1.13.
Due 09/05/08 1.14, 1.18, 1.19, 1.21.
Due 09/12/08 2.3, 2.5, 2.8, 2.9.
Due 09/19/08 2.11, 2.12, 2.13.
Due 10/03/08 2.17, 2.18, 2.20, 2.26.
Due 10/17/08 3.4, 3.7, 3.17, 3.20.
Due 10/31/08 3.23, 3.30, 3.34.
Due 11/07/08 4.5, 4.9, 4.17, 4.18.
Due 11/14/08 4.22, 4.24, 4.25, 4.32, 4.47.
Due 12/08/08 5.12, 5.13, 5.17, 5.18, 5.24.
| Announcements |
| All versions of the textbook, hard and soft cover, are the same. The publisher erroneously failed to use the corrections when reprinting the book. The author profoundly apologizes. See the textbook corrections for printed copies of the book, or use the corrected online version. |
| Sample exams for Exam 1 (Postscript, PDF) and Exam 2 (Postscript, PDF) are now available. |