Course Number *: 765-434            Effective: FALL 2001 

Course Title: Theory of Computation
15 Character Abbreviation: Computation
25 Character Abbreviation: Theory of Computation

Sponsor: Jonathan Kane
E-mail Address: kanej@mail.uww.edu
Department: Mathematical and Computer Sci.
College: Letters & Sciences

Other Programs Affected: Mathematics Major, Computer Science Minor

Check if course is to meet any of the following requirements:
None Writing Computer Diversity General Ed and Area

Contact hours/credits: 16               Total lecture hours: 48
Total lab hours: 0                           Total contact hours: 48
Number of credits 3

Check if course is repeatable: No Yes (if yes answer the following questions)
No of times in major                       No of credits in major
No of times in degree                      No of credits in degree

Enter the appropriate titles if the course is required in any of the following:
Major Title(s)
Minor Title(s)
Emphasis Title(s) Computer Mathematics Major

Course Justification:
To understand which mathematical operations are possible to calculate using a computer and to estimate the efficiency of solving those problems, one needs to develop a model of computation and investigate what problems those models can solve. Two standard models to investigate are finite automata and Turing machines. The first gives a simple to investigate model allowing the student to see mathematical proofs related to the abilities of these machines. The second, Turing machines, are now accepted as the general model for investigating which functions are computable. Their study leads to the basis of the theory of computation, efficiency of algorithms, and complexity theory. This course would provide the main theoretical component of the proposed Computer Mathematics emphasis in the Mathematics Major and would also serve as an elective course in a future major in Computer Science, a long term goal of the Department of Mathematical and Computer Sciences.

Relationship to program assessment objectives:
The study of computation exposes the student to the abstract concepts of modeling a computer and investigating the capabilities of that model. A wide variety of new problem solving techniques are introduced. Student also see many theorems related to the computability of functions and the undecidability of some questions. Thus, this course provides students with the challenge of dealing with abstract models of real world devices, a new set of problem solving strategies, and practice in proving theorems.

Budgetary impact:
The Department of Mathematical and Computer Sciences currently has faculty prepared to teach this course. If the Computer Mathematics emphasis in the Mathematics major is approved, this course would have to be taught on a biannual basis. The department is currently involved in searches for new faculty with expertise in Computer Science. The filling of these positions will allow the new course to be offered.

Course description:
This course is an introduction to the theory of computation. It discusses finite automata and Turing machines as models of computation. It includes discussions of regular sets, recursive and partially recursive functions, context free grammars, the halting problem, undecidable problems, complexity, and Np-completeness.

Course requisites:
Prerequisite 760-280

Course objectives and tentative course syllabus:
This course will introduce two models of computation: finite automata and Turing machines. These theoretical models give us tools with which we can investigate the theory of computation. We will see that there are functions which cannot be computable. Other functions cannot be computed in a small amount of time. We will see that there is often a tradeoff between space and time when constructing efficient routines.

Weeks         Topic
2                Finite Automata
2                Regular sets
1                Context free grammars
1                Algorithms and Computable functions
2                Turing machines, the universal Turing machine, Church’s thesis
3                Recursive and partially recursive functions
2                Decidablility and the halting problem
2                Efficiency, complexity, and NP-completeness

Bibliography:

Cutland, N. J., Computability: An Introduction to Recursive Function Theory Cambridge University Press, 1980.
*Mikhail J. Atallah Algorithms and theory of computation handbook CRC Press, 1999.
*Lewis, Harry R. and Christos H. Papadimitriou Elements of the theory of computation Prentice-Hall, 1988.
*Hopcroft, John E. and Jeffrey D. Ullman Introduction to automata theory, languages, and computation Addison-Wesley, 1979.
*Machtey, Michael and Paul Young An introduction to the general theory of algorithms North-Holland, 1978.
*Denning, Peter J., Jack B. Dennis, and Joseph E. Qualitz Machines, languages, and computation Prentice-Hall, 1978.
Greenlaw, Raymond, H. James Hoover Fundamentals of the theory of computation: principles and practice Morgan Kaufmann, 1998.
Atallah, Mikhail J., Algorithms and theory of computation CRC Press, 1999.
Sipser, Michael Introduction to the theory of computation PWS Pub. Co., 1997.
Smith, Carl A recursive introduction to the theory of computation Springer-Verlag, 1994.
Howie, John M. Automata and languages Oxford University Press, 1991.
Martin, John C. Introduction to languages and the theory of computation McGraw-Hill, 1991.Gurari, Eitan An introduction to the theory of computation Computer Science Press, 1989.
Brookshear, J. Glenn Theory of computation : formal languages, automata, and complexity Benjamin/Cummings Pub. Co., 1989.

*Currently available in the UW-Whitewater Library