Computer Science @ UC Davis | Course Descriptions

ECS 120 INTRODUCTION TO THE THEORY OF COMPUTATION (4) I, II, III

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course ECS 20, Math 108 recommended

Grading: Letter; homework (30%), midterm (25%), final (45%)

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

Expanded Course Description:

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. The pumping lemma.
2. Context-free languages. Grammars and push-down automata. Normal forms. The pumping lemma.
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 andother examples of undecidable problems.
3. Reducibility. Examples of many-one reductions.
Complexity Theory
1. Time compexity. 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

Textbook:
M. Sipser, Introduction to the Theory of Computation, 2nd ed., Course Technology, 2005

Computer Usage:
None

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

Goals:
Students will:

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
deepen his/her ability to think clearly, originally and devise correct proofs

Student Outcomes:

An ability to apply knowledge of mathematics, science, and engineering
A recognition of the need for, and an ability to engage in life-long learning
An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice

Instructors: D. Gusfield, C. Martel, P. Rogaway, V. Filkov

Prepared by: P. Rogaway, V. Filkov (September 2007)

Overlap Statement:
This course does not duplicate any existing course.

Back to Course Descriptions