2022 Fall
COMPSCI 172 001 - LEC 001
Computability and Complexity
Avishay Tal
Class #:32336
Units: 4
Instruction Mode:
In-Person Instruction
Time Conflict Enrollment Allowed
Offered through
Electrical Engineering and Computer Sciences
Current Enrollment
Total Open Seats:
19
Enrolled: 45
Waitlisted: 0
Capacity: 64
Waitlist Max: 40
No Reserved Seats
Hours & Workload
3 hours of instructor presentation of course materials per week, 8 hours of outside work hours per week, and 1 hours of the exchange of opinions or questions on course material per week.
Final Exam
TUE, DECEMBER 13TH
08:00 am - 11:00 am
Soda 306
Course Catalog Description
Finite automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.
Rules & Requirements
Requisites
- Undergraduate Students: College of Engineering declared majors and L&S Computer Science
Repeat Rules
Course is not repeatable for credit.
Reserved Seats
Current Enrollment
No Reserved Seats
Textbooks & Materials
See class syllabus or https://calstudentstore.berkeley.edu/textbooks for the most current information.
Guide to Open, Free, & Affordable Course Materials