CS 170. Efficient Algorithms and Intractable Problems
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:
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.
Links: