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 (Spring 2025):
CS 170 – TuTh 14:00-15:29, Valley Life Sciences 2050 – John Wright, Nika Haghtalab

Class Notes
* Time conflicts ARE allowed but NO ALTERNATE FINAL EXAM.

* Lecture will be recorded for playback later.

* Limited seats have been set aside for Data Science majors.

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

Class Notes
* Time conflicts ARE allowed, but NO alternate final will be offered.

* The lecture WILL be recorded for playback later.

Class homepage on inst.eecs

Links:

• CS enrollment policies
• EE enrollment policies
• HKN course maps