ECS 120: Theory of Computation

Subject
ECS 120
Title
Theory of Computation
Status
Active
Units
4.0
Effective Term
2019 Winter Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Fundamental ideas in the theory of computation, including formal languages, computability and complexity. Reducibility among computational problems. GE Prior to Fall 2011: SciEng. GE: SE, QL.
Prerequisites
(ECS 020 or MAT 108); (ECS 32B or ECS 36C Recommended)
Enrollment Restrictions
Pass One open to Computer Science, Computer Science Engineering, and Cognitive Science Majors only.

Summary of Course Content

I. Automata Theory and Formal Languages

  • Regular languages. Finite automata and the class of languages they define. Closure properties of regular languages. Multiple-characterization of regular languages (DFAs, NFA, regular expressions). The pumping lemma for regular languages.
  • Context-free languages. Grammars and pushdown automata. Normal forms. The pumping lemma for CFLs.

II. Computability Theory

  • The Turing-machine model, RAM model, and other equivalent models of effective computability. The Church-Turing thesis.
  • Decidable and undecidable problems. Recursively-enumerable sets. The halting problem and other examples of undecidable problems.
  • Reducibility. Examples of many-one reductions.

III. Complexity Theory

  • Time complexity. P and NP. Polynomial-time reducibility. NP-Completeness. The Cook-Levin Theorem. Example reductions among NP-hard sets.
  • Any of the following topics, as time permits:
    • Parallel models of computation
    • The role of randomness in computation
    • Interactive proofs

Illustrative Reading
M. Sipser, Introduction to the Theory of Computation, 3rd ed. Course Technology, 2012 

Potential Course Overlap
none

Course Category

Upper Division