EECS 335: Intro to the Theory of Computation

Quarter Offered

Fall : 9:30-10:50 TuTh ; De


EECS 212 (Mathematical Foundations of Computer Science) or permission of instructor.


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.

  • This course fulfills the Theory Breadth & Theory Depth requirement.

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.

INSTRUCTOR: Prof. Anindya De

RECOMENDED TEXTBOOK: "Introduction to the Theory of Computation" by Michael Sipser, Course Technology, 2nd Edition, The MIT Press,  ISBN-13: 978-0534950972; ISBN-10: 0534950973.

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 212 (Mathematical Foundations of Computer Science) or permission of instructor.


  • 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


      • 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.