2023 Fall
COMPSCI 170 001 - LEC 001
Efficient Algorithms and Intractable Problems
John Wright, Nika Haghtalab
Class #:28121
Units: 4
Instruction Mode:
In-Person Instruction
Time Conflict Enrollment Allowed
Offered through
Electrical Engineering and Computer Sciences
Current Enrollment
Total Open Seats:
32
Enrolled: 716
Waitlisted: 0
Capacity: 748
Waitlist Max: 300
Open Reserved Seats:
31 unreserved seats
1 reserved for Undergraduate Data Science Majors
Hours & Workload
1 hours of the exchange of opinions or questions on course material per week, 3 hours of instructor presentation of course materials per week, and 8 hours of outside work hours per week.
Final Exam
FRI, DECEMBER 15TH
08:00 am - 11:00 am
RSF Fieldhouse
Dwinelle 145
Physics Building 1
Physics Building 4
Evans 7
Evans 72
Dwinelle 189
Dwinelle 263
Dwinelle 89
Course Catalog Description
Concept and basic techniques in the design and analysis of algorithms; models of computation; lower bounds; algorithms for optimum search trees, balanced trees and UNION-FIND algorithms; numerical and algebraic algorithms; combinatorial algorithms. Turing machines, how to count steps, deterministic and nondeterministic Turing machines, NP-completeness. Unsolvable and intractable problems.
Class Notes
* Pre-reqs are NOT enforced for this class but ARE strongly recommended.
* The lecture will be recorded for playback later.
* Time conflicts ARE allowed but NO alternate final exam will be offered.
* A limited number of seats will eventually be reserved for DS student.. show more
* The lecture will be recorded for playback later.
* Time conflicts ARE allowed but NO alternate final exam will be offered.
* A limited number of seats will eventually be reserved for DS student.. show more
* Pre-reqs are NOT enforced for this class but ARE strongly recommended.
* The lecture will be recorded for playback later.
* Time conflicts ARE allowed but NO alternate final exam will be offered.
* A limited number of seats will eventually be reserved for DS students in this class. show less
* The lecture will be recorded for playback later.
* Time conflicts ARE allowed but NO alternate final exam will be offered.
* A limited number of seats will eventually be reserved for DS students in this class. show less
Rules & Requirements
Requisites
- Undergraduate Students: College of Engineering declared majors or L&S Computer Science or Data Science BA
Repeat Rules
Course is not repeatable for credit.
Reserved Seats
Current Enrollment
Open Reserved Seats:
31 unreserved seats
1 reserved for Undergraduate Data Science Majors
Textbooks & Materials
See class syllabus or https://calstudentstore.berkeley.edu/textbooks for the most current information.
Guide to Open, Free, & Affordable Course Materials