printer friendly pageCS 161: Design and Analysis of Algorithms
Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching, amortized analysis, stable matchings and approximation algorithms. Prerequisite: 103 or 103B; 109 or
STATS 116.
Terms: Aut, Win, Spr, Sum
| Units: 3-5
| UG Reqs: GER:DB-EngrAppSci, WAY-FR
Instructors:
Anari, N. (PI)
;
Charikar, M. (PI)
;
Rubinstein, A. (PI)
...
more instructors for CS 161 »
Instructors:
Anari, N. (PI)
;
Charikar, M. (PI)
;
Rubinstein, A. (PI)
;
Tullis, I. (PI)
;
Wootters, M. (PI)
CS 261: Optimization and Algorithmic Paradigms
Algorithms for network optimization: max-flow, min-cost flow, matching, assignment, and min-cut problems. Introduction to linear programming. Use of LP duality for design and analysis of algorithms. Approximation algorithms for NP-complete problems such as Steiner Trees, Traveling Salesman, and scheduling problems. Randomized algorithms. Introduction to sub-linear algorithms and decision making under uncertainty. Prerequisite: 161 or equivalent.
Terms: Win
| Units: 3
Instructors:
Sidford, A. (PI)
Filter Results: