| Welcome |
|
Professor: Dr. Layne T. Watson Office: 630 McBryde Graduate Teaching Assistant: Name: Jinfei Zhang |
| 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 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.
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
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.
| 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. |
| 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. |