CSE 203A  Advanced Algorithms
Syllabus
 Linear programming
 Semidefinite programming
 Convex programming
 Approximation algorithms
Problems and Techniques
Textbooks
 Approximation algorithms and semidefinite programming, Bernd Gärtner and Jiří Matoǔsek; Internet copy at the UC San Diego library
 Lectures on modern convex optimization, Aharon BenTal and Arkadi Nemirovski; Internet copy at the UC San Diego library
Books
Linear, Semidefinite, Convex Programming
 A course in convexity, Alexander Barvinok; Internet copy at the UC San Diego library
 Undergraduate convexity, Niels Lauritzen; Internet copy at the UC San Diego library
 Lectures on modern convex optimization, Aharon BenTal and Arkadi Nemirovski; Internet copy at the UC San Diego library
 An easy path to convex analysis and applications, Boris Mordukhovich and Nguyen Mau Nam; Internet copy at the UC, San Diego library
 Convex optimization, Stephen Boyd and Lieven Vandenberghe, 2004.
 Understanding and using linear programming, Jiří Matoǔsek and Bernd Gärtner; Internet copy at the UC, San Diego library
Approximation Algorithms
 Approximation algorithms and semidefinite programming, Bernd Gärtner and Jiří Matoǔsek; Internet copy at the UC San Diego library
 The design of approximation algorithms, Shmoys and Williamson, 2001. Internet copy from the authors
 Approximation algorithms, Vijay Vazirani, 2003.
Randomized Algorithms
 Probability and Computing, Mitzenmacher and Upfal, Cambridge University Press, 2005
 The random projection method, Santosh Vempala, American Mathematical Society, 2004
 Randomized Algorithms, Motwani and Raghavan, Cambridge University Press, 1995
 Concentration of measure for the analysis of randomized algorithms, Devdatt P. Dubhashi, Alessandro Panconesi; Internet copy at the UC, San Diego library
 Spectral algorithms, Kannan and Vempala; Internet copy at the UC, San Diego library
Combinatorics and Probablility
 Extremal Combinatorics, Stasys Jukna, Springer, 2001
 Probabilistic Methods, Alon and Spencer, John Wiley, 2000
 Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Bollobas, Cambridge University Press, 1986
 Combinatorics of Finite Sets, Ian Anderson, Oxford University Press, 2005
 The discrepancy method: randomness and complexity, Chazelle, Cambridge University Press, 2000
Basic Algorithms
 Algorithm Design by Kleinberg and Tardos, 1st edition
 Introduction to Algorithms by Cormen, Leiserson, and Rivest
 Algorithms by Dasgupta, Papadimitriou, and Vazirani
 Algorithmic Puzzles, Anany Levitin and Maria Levitin, Oxford University Press
Notes
 Linear programming solution types
 Perceptron Classifiers (Charles Elkan)
