Curriculum
  /  
Descriptions
COMP_SCI 335: Intro to the Theory of Computation


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

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

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 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. Hartline, Prof. Vijayaraghavan, Jinshuo Dong, or Anjali Agarwal

COURSE COORDINATOR: Prof. Vijayaraghavan

TEXTBOOK REQUIRED NOT RECOMMENDED: "Introduction to the Theory of Computation" by Michael Sipser, Course Technology, 3rd Edition, The MIT Press,  ISBN-13: 978-1133187790; ISBN-10: 113318779X.

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: COMP_SCI 212 (Mathematical Foundations of Computer Science) 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

GRADING:

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