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.

Units: 4

Related Areas:

• Security (SEC)
• Theory (THY)

Prerequisites: COMPSCI 61B and COMPSCI 70.

Formats:
Spring: 3.0 hours of lecture and 1.0 hours of discussion per week
Summer: 6.0 hours of lecture and 2.0 hours of discussion per week
Fall: 3.0 hours of lecture and 1.0 hours of discussion per week

Grading Basis: letter

Final Exam Status: Written final exam conducted during the scheduled final exam period

---

Class Schedule (Fall 2025):
CS 170 – TuTh 14:00-15:29, Wheeler 150 – John Wright, Sanjam Garg

Class Notes
* Time conflicts are NOT allowed.

* The lecture WILL be recorded for playback later.

Class Schedule (Spring 2026):
CS 170 – TuTh 15:30-16:59, Stanley 105 – Lijie Chen, Umesh V Vazirani

Class Notes
- Lectures will be recorded.

- Seats reserved for students with enrollment permission are not open. They are reserved for students in internal programs. Please DO NOT ask faculty or staff for one of these seats. The students who qualify have already been notified.

Links:

• EECS Course Archives (CalNet authentication required)
• CS enrollment policies
• EE enrollment policies
• HKN course maps