Syllabus for CPSC 536N (Sparse Approximations)
2012-13 Term 2


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.





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