ECS 120 THEORY OF COMPUTATION (4 units)
Lecture: 3 hours
Discussion: 1 hour
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
- 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.
M. Sipser, Introduction to the Theory of Computation, 3rd ed. Course Technology, 2012
ABET Category Content:
Engineering Science: 4 units
Engineering Design: 0 unit
Science & Engineering V. Filkov, M. Franklin, D. Gusfield, and P. Rogaway
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|