Lecture: 3 hours
Discussion: 1 hour

Catalog Description:
Fundamental ideas in the theory of computation, including formal languages, computability and complexity. Reducibility among computational problems.

Prerequisite: (ECS 020 or MAT 108); (ECS 32B or ECS 36C Recommended)

Credit restrictions, cross listings: None

Summary of course contents

  1. Automata Theory and Formal Languages
    1. 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.
    2. Context-free languages. Grammars and pushdown automata. Normal forms. The pumping lemma for CFLs.
  2. Computability Theory
    1. The Turing-machine model, RAM model, and other equivalent models of effective computability. The Church-Turing thesis.
    2. Decidable and undecidable problems. Recursively-enumerable sets. The halting problem and other examples of undecidable problems.
    3. Reducibility. Examples of many-one reductions.
  3. Complexity Theory
    1. Time complexity. P and NP. Polynomial-time reducibility. NP-Completeness. The Cook-Levin Theorem. Example reductions among NP-hard sets.
    2. Any of the following topics, as time permits:
      1. Parallel models of computation
      2. The role of randomness in computation
      3. Interactive proofs

Goals: students will (1) learn core ideas in computer science theory, including how to define and investigate a formalized model of computation, and what it means to reduce one problem to another; and (2) deepen their ability to think clearly, originally and devise correct proofs.

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

Computer Usage:

ABET Category Content:
Engineering Science: 4 units
Engineering Design: 0 unit

Science & Engineering V. Filkov, M. Franklin, D. Gusfield, and P. Rogaway
Quantitative Literacy

Overlap: NP-completeness is also covered in course 122A, but at a more superficial level and without attending to its “membership in NP” aspect.

Instructors: V. Filkov, M. Franklin, D. Gusfield, and P. Rogaway

History: Reviewed 2018.9.7 (CSUGA): prerequisites updated to include new lower division ECS series courses. 2012.09.28 (P. Rogaway): changed prerequisites from “20; Mathematics 108 recommended” to “20 or Math 108”; dropped “Introduction to the” in the title; mentioned the single-topic overlap with course 122A; populated ICMS expanded course description, which had been missing.  Prior version by V. Filkov and P. Rogaway (2007.09).


1 X an ability to apply knowledge of mathematics, science, computing, and engineering
2 an ability to design and conduct experiments, as well as to analyze and interpret data
3 an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
4 an ability to function on multi-disciplinary teams
5 X an ability to identify, formulate, and solve computer science and engineering problems  and define the computing requirements appropriate to their solutions
6 an understanding of professional, ethical, legal, security and social issues and responsibilities
7 an ability to communicate effectively with a range of audiences
8 the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context
9 X a recognition of the need for, and an ability to engage in life-long learning
10 knowledge of contemporary issues
11 X an ability to use current techniques, skills, and tools necessary for computing and engineering practice
12 an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices
13 an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity