CSE 203A - Advanced Algorithms
Syllabus
- Linear programming
- Semi-definite 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 Ben-Tal 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 Ben-Tal 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)
|