2024 Fall
COMPSCI 172 001 - LEC 001
Computability and Complexity
Avishay Tal
Class #:31387
Units: 4
Instruction Mode:
In-Person Instruction
Time Conflict Enrollment Allowed
Offered through
Electrical Engineering and Computer Sciences
Current Enrollment
Total Open Seats:
3
Enrolled: 65
Waitlisted: 0
Capacity: 68
Waitlist Max: 100
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
THU, DECEMBER 19TH
11:30 am - 02:30 pm
Cory 277
Other classes by Avishay Tal
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.
Class Notes
* Time conflicts ARE allowed.
* NO Alternate final exam offered.
* NO Alternate final exam offered.
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