**Format**

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: **Course 20 or Mathematics 108

**Credit restrictions, cross listings**: None

**Summary of course contents**

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

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

- 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

*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,

**Computer Usage:
**None

**ABET Category Content:
**Engineering Science: 4 units

Engineering Design: 0 unit

**GE3**

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: **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).

**Outcomes**

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 |