Welcome  Last Updated September 29 
Welcome to the wonderful world of computation ....
Friday, September 29
10:56 ET
Jiang
Office: McBryde 630 Phone: (540) 231  7540 Email: ltw@cs.vt.edu Office Hours: 11:00  12:00 MWF; and by appointment. Graduate Teaching Assistant: Jiang Shu Office: McBryde 133 Email: jishu@csgrad.cs.vt.edu Office Hours: 12:30  14:00 PM TR

Syllabus  Last Updated September 29 
Class contract .... Friday, September 29 10:56 ET Jiang 
CS4124 Theory of Computation MWF 10:1011:00 McBryde 216  
Instructor: L. T. Watson, 630
McBryde,
2317540,ltw@cs.vt.edu Office Hours: 11:0012:00 MWF, and by appointment. Prerequisites: Math 3134 or Math 3034. 

Text: J. E. Savage, Models of Computation AddisonWesley, 1998.  
Topics Covered: Logic circuits, Boolean function normal forms, prefix computations, arithmetic, circuit complexity, finitestate machines, randomaccess machines, Turing machines, simulation, pushdown automata, regular and contextfree languages, models of computability, reducibility and insolvability, recursive function theory, parallel computation, spacetime tradeoffs.  
Grading: FINAL GRADE will be the
average of two inclass exams (50%), a final examination (25%), and homework and class participation (25%). 

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

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, PrenticeHall, 1978. Gill, Introduction to the Theory of Finite State Machines, McGrawHill, 1962. Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, AddisonWesley, 1979. Kain, Automata Theory, Machines, and Languages, McGrawHill, 1972. Kfoury, Moll, Arbib, A Programming Approach to Computability, SpringerVerlag, 1982. Manna, Mathematical Theory of Computation, McGrawHill, 1974. McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982. Minsky, Computation: Finite and Infinite Machines, PrenticeHall, 1967. B. M. Moret, The Theory of Computation, AddisonWesley, 1998. Rogers, Theory of Recursive Functions and Effective Computability, McGrawHill, 1967. R. G. Taylor, Models and Computation and Formal Languages, Oxford, 1998. 
Announcements  Last Updated December 15 
