CS 4124 - Theory of Computation

Welcome | Syllabus | Assignments | Announcements | Textbook-Correction

Welcome - Last Updated September 29
Welcome to the wonderful world of computation .... Friday, September 29 10:56 ET Jiang

    This webpage is written for CS 4124 Theory of Computation MWF 10:10--11:00 McBryde 216 (Fall, 2000).

Syllabus - Last Updated September 29
Class contract .... Friday, September 29 10:56 ET Jiang

CS4124 Theory of Computation MWF 10:10--11:00 McBryde 216
Instructor: L. T. Watson, 630 McBryde, 231-7540,ltw@cs.vt.edu 
Office Hours:
11:00--12:00 MWF, and by appointment.
Math 3134 or Math 3034.
Text: J. E. Savage, Models of Computation Addison-Wesley, 1998.
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%).

Final Exam: 07:45--9:45am Wednesday, December 13, 2000.

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.

Announcements - Last Updated December 15

    12/15/2000 (9:00) - Answers to the final exam are posted by Dr. Watson's door. Final grades have been submitted, and should be available on the Hokie SPA.

This page is maintained by Jiang Shu (Homepage).

Made with Notepad! And Netscape Enhanced!
Here is Jiang's disclaimer.
These pages are 2000 - Jiang Shu Productions - all rights reserved.
Technological Servicesr is a registered trademark.
Any comments, questions, rants, submissions, etc.?

Email: jishu@csgrad.cs.vt.edu