— Theory of Computation

Prerequisites & course information

This version has ended; see updated course, below. Course Description: Fundamental ideas in the theory of computation, including formal languages, computability and complexity. Reducibility among computational problems. Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One restricted to Computer Science and Computer Science Engineering majors only. Grade Mode: Letter. General Education: Science & Engineering (SE); Quantitative Literacy (QL). ECS 120 — Theory of Computation (4 units) Course Description: Fundamental ideas in the theory of computation, including formal languages, computability and complexity. Reducibility among computational problems. Prerequisite(s): ( MAT 108 or MAT 108V ) or ( ECS 020 , ( ECS 032B or ECS 036C )). Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One open to Computer Science, Computer Science Engineering, Cognitive Science majors only. Grade Mode: Letter. General Education: Science & Engineering (SE); Quantitative Literacy (QL). This course version is effective from, and including: Winter Quarter 2027. Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One restricted to Computer Science and Computer Science Engineering majors only. Grade Mode: Letter. General Education: Science & Engineering (SE); Quantitative Literacy (QL). ECS 120 — Theory of Computation (4 units) Course Description: Fundamental ideas in the theory of computation, including formal languages, computability and complexity. Reducibility among computational problems. Prerequisite(s): ( MAT 108 or MAT 108V ) or ( ECS 020 , ( ECS 032B or ECS 036C )). Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One open to Computer Science, Computer Science Engineering, Cognitive Science majors only. Grade Mode: Letter. General Education: Science & Engineering (SE); Quantitative Literacy (QL). This course version is effective from, and including: Winter Quarter 2027.