Fall 2014

CS 4124–Theory of Computation

Welcome | Syllabus | Assignments | Announcements


Welcome

Professor: Dr. Layne T. Watson
Office: 2000 Torgersen
Phone: (540) 231–7540
Email: ltwatson@computer.org
Office Hours: 122 McBryde Hall, 11:15–12:30 MW, and by appointment in 2000 Torgersen.

Graduate Teaching Assistant:

Name: Mohammad Islam
Office: 106 McBryde
Email: raihan8@vt.edu
Office Hours: Monday, Wednesday 11:00–13:30.

Undergraduate Teaching Assistant:

Name: Michael Levet
Office: 106 McBryde
Email: mlevet@vt.edu
Office Hours: Tuesday, Thursday 14:00–17:00.

To the top!

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 9:05–9:55 WMS 320 CRN 82160

Instructor: L. T. Watson, 2000 Torg, 231-7540, ltwatson@computer.org

Office Hours: 11:15–12:15 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: 10:05--12:05 Tuesday, Dec. 16, 2014.

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.

Goddard,
Introducing the Theory of Computation, Jones and Bartlett, 2008.

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.

To the top!

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. Assignments are due at the beginning of class (9:05) on the due dates. See the syllabus files linked above for problem point values and which problems are extra credit.

Due 08/29/14: 1.3, 1.5, 1.10, 1.13.

Due 09/05/14: 1.14, 1.18, 1.19, 1.21.

Due 09/12/14: 2.3, 2.5, 2.8, 2.9.

Due 09/19/14: 2.11, 2.12, 2.13.

Due 10/03/14: 2.17, 2.18, 2.20, 2.26.

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

Due 10/31/14: 3.23, 3.30, 3.34.

Due 11/07/14: 4.5, 4.9, 4.17, 4.18.

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

Due 12/08/14: 5.12, 5.13, 5.17, 5.18, 5.24, 5.25.


To the top!

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.

To the top!



L. T. Watson <ltwatson@computer.org>
Last modified: Mon Aug 25 20:44:15 EDT 2014