CS 4124–Theory of Computation

Welcome | Syllabus | Assignments | Announcements


Professor: Dr. Layne T. Watson
Office: 2000 Torgersen
Phone: (540) 231–7540
Email: ltw@cs.vt.edu
Office Hours: 122 McBryde Hall, 10:00–11:00 MWF, and by appointment.

Graduate Teaching Assistant:

Name: Tung Manh Dao
Office: 106 McBryde
Email: tungdm@vt.edu
Office Hours: 8:00–11:00 T, 8:00–11:00 and 13:00–14:00 Th, 13:00–16:00 F.


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 8:00–8:50 MCB 304 CRN 91919

Instructor: L. T. Watson, 2000 Torg, 231-7540, ltw@cs.vt.edu

Office Hours: 10:00–11:00 MWF in MCB 122, and by appointment in 2000 Torg.

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 unsolvability, 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: 07:45--09:45 Monday, Dec. 12, 2011.


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.

Introduction to the Theory of Finite State Machines, McGraw-Hill, 1962.

Introducing the Theory of Computation, Jones and Bartlett, 2008

Hopcroft, Ullman,
Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

Automata Theory, Machines, and Languages, McGraw-Hill, 1972.

Kfoury, Moll, Arbib,
A Programming Approach to Computability, Springer-Verlag, 1982.

Mathematical Theory of Computation, McGraw-Hill, 1974.

Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982.

Computation: Finite and Infinite Machines, Prentice-Hall, 1967.

B. M. Moret,
The Theory of Computation, Addison-Wesley, 1998.

Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.

R. G. Taylor,
Models and Computation and Formal Languages, Oxford, 1998.

To the top!


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/26/11: 1.3, 1.5, 1.10, 1.13.

Due 09/02/11: 1.14, 1.18, 1.19, 1.21.

Due 09/09/11: 2.3, 2.5, 2.8, 2.9.

Due 09/16/11: 2.11, 2.12, 2.13.

Due 09/30/11: 2.17, 2.18, 2.20, 2.26.

Due 10/14/11: 3.4, 3.7, 3.17, 3.20.

Due 10/28/11: 3.23, 3.30, 3.34.

Due 11/04/11: 4.5, 4.9, 4.17, 4.18.

Due 11/11/11: 4.22, 4.24, 4.25, 4.32, 4.47.

Due 12/05/11: 5.12, 5.13, 5.17, 5.18, 5.24, 5.25.

To the top!

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.

To the top!

L. T. Watson <ltw@cs.vt.edu>
Last modified: Sun Aug 30 18:01:53 EDT 2011