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:
Summer: 6.0 hours of lecture and 2.0 hours of discussion per week
Spring: 3.0 hours of lecture and 1.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 2022):
TuTh 09:30-10:59, Dwinelle 155 –
James W DEMMEL, Jelani Nelson, Param Nagda, Tianchen Liu
Class Schedule (Spring 2023):
MoWeFr 11:00-11:59, Lewis 100 –
John Wright, Prasad Raghavendra
Fall 2021 class homepage on bCourses
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: