15-853: Algorithms in the Real World (Guy Blelloch and Anupam Gupta, Fall 06)

Readings, Notes and Slides

Note that we will not have slides from all the lectures. Some lectures will be given on the board, and some slides will be hand done.

Learning, Online Prediction and Games



Readings Slides

Error Correcting Codes

Readings: Some other potentially usefull readings
  • Introduction to expander graphs by Michel Nielsen.
  • Lecture slides:

    Dimension Reduction

    Graph Separators


    Linear and Integer Programming

  • Gilbert Strang. Linear Algebra and its Applications. Third Edition. Chapter 8 (Linear programming and game theory).
    This is the most concise and clear introduction to the simplex method I have read and it also contains a short description of Karmakar's interior-point method. If you have another source you have already used and feel comfortable with, feel free to read it instead.
  • Bradley, Hax and Magnanti Applied Mathematical Programming. Chapter 9 (Integer Programming).
  • G. L. Nemhauser. The age of optimization: solving large-scale real-world problems.
  • These are some other potentially usefull readings
  • Robert Freund and Shinji Mizuno. Interior Point Methods: Current Status and Future Directions This is a good overview of interior point methods, and is available online.
  • Slides

    Computational Biology





    Guy Blelloch, guyb@cs.cmu.edu.