# The Department of Electrical Engineering & Computer Science

## EECS 335 - Introduction to the Theory of Computation

Catalog Description: This course gives an introduction to the mathematical foundations of computation. The course will look at Turing machines, universal computation, the Church-Turing thesis, the halting problem and general undecidability, Rice’s theorem, the recursion theorem, efficient computation models, time and space (memory) bounds, deterministic and nondeterministic computation and their relationships, the P versus NP problem and hard problems for NP and beyond.

Note: This course will replace Math 374 (Theory of Computability and Turing Machines) which is listed as a recommended way to fulfill the undergraduate theory breadth requirement in CS but hasn’t been taught in several years. The Math department is happy to give it up.

Required Textbook: Computability and Complexity Theory by Steve Homer and Alan Selman

Course Goals: A firm background in the basic principles of theoretical computer science with a particular understanding of undecidability and intractability, the theoretical limitations of computation.

Prerequisites: EECS 310 (Discrete Mathematics) or permission of instructor.

Detailed Course Topics:

• Alphabets, Strings, Languages and Classes

• Turing Machines

• Multiple Tapes and RAMs

• Nondeterministic

• Church-Turing Thesis

• Computability Theory

• Decision Problems

• Computable and Computably Enumerable Sets

• Universal Turing Machines

• Undecidability

• Halting Problem

• Rice’s Theorem

• Recursion Theorem

• Complexity Theory

• Time and Space (memory)

• Multiple Tapes and RAMs

• Nondeterministic

• DTIME, DSPACE, NTIME, NSPACE

• Basic relationships

• Savitch’s Theorem

• Nondeterministic Space closed under complement

• Time and Space Hierarchies

• The P versus NP problem

• Definitions of P and NP

• Robustness of definitions

• NP-completeness of Satisfiability and other problem

• Implications of NP-completeness and how to handle it

• Beyond NP

• PSPACE

• Exponential-Time

• Provably Intractable Problems

• Other Models of Efficient Computation

• Brief discussion of probabilistic, parallel and quantum computation

• Weekly homework assignments (33%)

• Midterm Exam (33%)

• Final Exam (34%)

Course Objectives: When a student completes this course, he/she should be able to prove that various computational problems are undecidable or NP-complete and understand the implications of those results.

### Search course subsets

 Select a category CS Core Course CS Project Course CS Depth-Theory CS Depth-Systems CS Depth-AI CS Depth-Interfaces CS Depth-Security CS Breadth-Theory CS Breadth-Systems CS Breadth-AI CS Breadth-Interfaces CS Breadth-Software Development