2022 Spring COMPSCI 172 001 LEC 001

Spring 2022

COMPSCI 172 001 - LEC 001

Computability and Complexity

Avishay Tal

Jan 18, 2022 - May 06, 2022
Tu, Th
05:00 pm - 06:29 pm
Class #:22721
Units:4

Instruction Mode: In-Person Instruction
Time Conflict Enrollment Allowed

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

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.

Textbook Lookup

Guide to Open, Free, & Affordable Course Materials

eTextbooks

Associated Sections