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

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 2024):
CS 170 – TuTh 14:00-15:29, Valley Life Sciences 2050 – Prasad Raghavendra, Sanjam Garg

Class Schedule (Spring 2025):
CS 170 – TuTh 14:00-15:29, Valley Life Sciences 2050 – John Wright, Nika Haghtalab

Class homepage on inst.eecs

---

Department Notes:

Course objectives: Provide familiarity with algorithms for recurring basic problems. Learn to design algorithms to solve novel problems. Learn about the concept of the intrinsic difficulty of certain computational problems.

Topics covered:

• Divide and conquer
• Graphs and trees
• Depth-first search
• Topological sort; strongly-connected components
• Breadth-first search
• Shortest paths; Dijkstra and Bellman-Ford
• Minimum spanning trees
• Union/find analysis
• Hufmann codes
• Lempel-Ziv codes
• Randomized min-cut
• Hashing
• Bloom filters
• Dynamic programming
• Linear programming; posing of combinatorial problems as LP problems
• Duality
• Network flows
• NP completeness
• Approximation algorithms
• Fast Fourier transform

Related Areas:

• Security (SEC)
• Theory (THY)