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