Description
This
is a graduate course on algorithm design. We will explore two branches of this
field: combinatorial optimization algorithms and spectral algorithms. The
ultimate goal of the course is to see how the theme of “sparse approximations”
plays an important role in many areas. We will cover some advanced papers on
that topic.
Webpage: http://www.cs.ubc.ca/~nickhar/W13
Resources
There is no required text for this class. Some
relevant books:
·
W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver.
“Combinatorial Optimization”
·
J. Matousek
and B. Gartner. “Understanding and Using Linear Programming” Free at
UBC Libraries
·
D. Williamson and D. Shmoys. “The Design of Approximation Algorithms” Free online edition
·
A. Schrijver.
“Combinatorial Optimization: Polyhedra and
Efficiency”
·
M. Mitzenmacher
and E. Upfal. “Probability and Computing”
·
R. Motwani
and P. Raghavan. “Randomized Algorithms”
·
D. Dubhashi
and A. Panconesi. “Concentration of Measure for the
Analysis of Randomized Algorithms”
Some relevant lecture notes:
·
M. Goemans.
“Combinatorial
Optimization”
·
N. Harvey. “Randomized Algorithms”
·
D. Spielman.
“Spectral Graph Theory”
·
L. Lau. “Spectral Algorithms”
Grading Scheme
The
course grade is based on the following three components, weighted roughly
equally.
·
Assignments (one or two)
·
Scribing lectures
·
Project