Syllabus: The course will cover theoretical design and
analysis of algorithms, focusing on computational problems
involving combinatorial optimization, such as cuts, flows and
distances in graphs. The emphasis will be on modern algorithmic
approaches for finding either exact or approximate (near-optimal)
solutions, using tools such as mathematical programming, matrix
analysis, geometry, sparsification and compression.
Prerequisites: Students are expected to be familiar with
algorithms, complexity theory, probability theory, and linear
algebra, at an undergraduate level.
problem set 4 (posted Dec. 23, spectral
graph theory + prediction using experts)
clarification for question #2: Assume G has unit
edge-weights, and that the balance (1/2 or 2/3) is measured
with respect to vertex-weights (where weight=degree).