CSE 203A - Advanced Algorithms

Syllabus

  1. Linear programming
  2. Semi-definite programming
  3. Convex programming
  4. Approximation algorithms

Problems and Techniques

Textbooks

  1. Approximation algorithms and semidefinite programming, Bernd Gärtner and Jiří Matoǔsek; Internet copy at the UC San Diego library
  2. Lectures on modern convex optimization, Aharon Ben-Tal and Arkadi Nemirovski; Internet copy at the UC San Diego library

Books

Linear, Semidefinite, Convex Programming

  1. A course in convexity, Alexander Barvinok; Internet copy at the UC San Diego library
  2. Undergraduate convexity, Niels Lauritzen; Internet copy at the UC San Diego library
  3. Lectures on modern convex optimization, Aharon Ben-Tal and Arkadi Nemirovski; Internet copy at the UC San Diego library
  4. An easy path to convex analysis and applications, Boris Mordukhovich and Nguyen Mau Nam; Internet copy at the UC, San Diego library
  5. Convex optimization, Stephen Boyd and Lieven Vandenberghe, 2004.
  6. Understanding and using linear programming, Jiří Matoǔsek and Bernd Gärtner; Internet copy at the UC, San Diego library

Approximation Algorithms

  1. Approximation algorithms and semidefinite programming, Bernd Gärtner and Jiří Matoǔsek; Internet copy at the UC San Diego library
  2. The design of approximation algorithms, Shmoys and Williamson, 2001. Internet copy from the authors
  3. Approximation algorithms, Vijay Vazirani, 2003.

Randomized Algorithms

  1. Probability and Computing, Mitzenmacher and Upfal, Cambridge University Press, 2005
  2. The random projection method, Santosh Vempala, American Mathematical Society, 2004
  3. Randomized Algorithms, Motwani and Raghavan, Cambridge University Press, 1995
  4. Concentration of measure for the analysis of randomized algorithms, Devdatt P. Dubhashi, Alessandro Panconesi; Internet copy at the UC, San Diego library
  5. Spectral algorithms, Kannan and Vempala; Internet copy at the UC, San Diego library

Combinatorics and Probablility

  1. Extremal Combinatorics, Stasys Jukna, Springer, 2001
  2. Probabilistic Methods, Alon and Spencer, John Wiley, 2000
  3. Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Bollobas, Cambridge University Press, 1986
  4. Combinatorics of Finite Sets, Ian Anderson, Oxford University Press, 2005
  5. The discrepancy method: randomness and complexity, Chazelle, Cambridge University Press, 2000

Basic Algorithms

  1. Algorithm Design by Kleinberg and Tardos, 1st edition
  2. Introduction to Algorithms by Cormen, Leiserson, and Rivest
  3. Algorithms by Dasgupta, Papadimitriou, and Vazirani
  4. Algorithmic Puzzles, Anany Levitin and Maria Levitin, Oxford University Press

Notes

  1. Linear programming solution types
  2. Perceptron Classifiers (Charles Elkan)