CS 4124–Theory of Computation

Welcome | Syllabus | Assignments | Announcements


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

Graduate Teaching Assistant:

Name: Jinfei Zhang
Office: 133 McBryde
Email: jinfei@vt.edu
Office Hours: 13:00–15:00 MW, 9:00–10: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 10:10–11:00 MCB 307 CRN 15104

Instructor: L. T. Watson, 630 McBryde, 231-7540,ltw@cs.vt.edu

Office Hours: 11:00–12:00 MWF, and by appointment.

Prerequisites: Math 3134 or Math 3034.

Text: J. E. Savage, Models of Computation Addison-Wesley, 1998. Textbook corrections.

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: 07:45--9:45 Monday, May 6, 2002.


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.

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

Due 01/18/02 1.3, 1.5, 1.10, 1.13.

Due 01/25/02 1.14, 1.18, 1.19, 1.21.

Due 02/01/02 2.3, 2.5, 2.8, 2.9.

Due 02/08/02 2.11, 2.12, 2.13.

Due 02/22/02 2.17, 2.18, 2.20, 2.26.

Due 03/15/02 3.4, 3.7, 3.17, 3.20.

Due 03/29/02 3.23, 3.30, 3.34.

Due 04/05/02 4.5, 4.9, 4.17, 4.18.

Due 04/12/02 4.22, 4.25, 4.32, 4.47.

Due 04/29/02 5.13, 5.17, 5.18, 5.24.

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.
Homework Grades will not be posted. And if you do want me to make no mistake to grade: 1) Please write your answer clearly, at least discernable. 2) Use math formula as possible as you can, eliminate natural language as possible as you can. -Jinfei, Feb.,5,2002.
Sample exams for Exam 1 (Postscript, PDF) and Exam 2 (Postscript, PDF) are now available.
Temporary TA office hours for your preparation of Exam 1: 1:00pm-3:00pm, Tue, Feb.,26. Good luck for your exam. -Jinfei, Feb.,25,2002.

To the top!

L. T. Watson <ltw@cs.vt.edu>
Last modified: THU Jan 24 11:30:04 EST 2002