Spring 2022
COMPSCI 172 001 - LEC 001
Computability and Complexity
Avishay Tal
Class #:22721
Units:4
Instruction Mode:
In-Person Instruction
Time Conflict Enrollment Allowed
Offered through
Electrical Engineering and Computer Sciences
Current Enrollment
Total Open Seats:
1
Enrolled: 64
Waitlisted: 0
Capacity: 65
Waitlist Max: 50
No Reserved Seats
Hours & Workload
3 hours of instructor presentation of course materials, 8 hours of outside work hours, and 1 hours of the exchange of opinions or questions on course material.
Final Exam
FRI, MAY 13TH
11:30 am - 02:30 pm
Valley Life Sciences 2040
Dwinelle 250
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
* This class will be webcast
* This class will be webcast
Rules & Requirements
Requisites
- Students not in the Master of Engineering Program
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