2 Algorithms Preparatory Programs

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, amortized analysis, and randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, and string searching. Prerequisite: 103 or 103B; 109 or STATS 116.

Convex sets, functions, and optimization problems. The basics of convex analysis and theory of convex programming: optimality conditions, duality theory, theorems of alternative, and applications. Least-squares, linear and quadratic programs, semidefinite programming, and geometric programming. Numerical algorithms for smooth and equality-constrained problems; interior-point methods for inequality-constrained problems. Applications to signal processing, communications, control, analog, and digital circuit design, computational geometry, statistics, machine learning, and mechanical engineering.