15-853: Algorithms in the Real World (Guy Blelloch and Jeremy Fineman, Fall 10)

Readings, Notes and Slides


Cryptography


Readings

Slides


Linear and Integer Programming


Readings

  • 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 useful 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.
  • Scribe notes on Primal-Dual Algorithms that Daniel wrote up once. Concise treatment of LP duality.
  • Slides


    Parallelism


    Readings

  • Parallel Algorithms by Guy Blelloch and Bruce Maggs. From Computer Science Handbook, Second Edition, Allen B. Tucker (Editor).
  • Slides


    Locality


    Readings

  • The Input/Output Complexity of Sorting and Related Problems by Aggarwal and Vitter (1988).
  • Cache-Oblivious Algorithms by Frigo, Leiserson, Prokop, and Ramachandran (1999).
  • The Buffer Tree: A Technique for Designing Batched External Data Structures by Arge (2003).
  • Slides


    Spatial Decompositions and Nearest Neighbors


    Readings

  • Cover Trees for Nearest Neighbor by Beygelzimer Kanade and Langford (2006)
  • A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields by Callahan and Kosaraju (1995).
  • Efficient collision detection using bounding volume hierarchies of k-DOPs, J.T. Klosowski, M. Held J. Mitchell, H. Sowizral, K. Zikan. This has some background on BVH in general.
  • Slides


    Computational Biology


    Readings

    Slides


    String Searching


    Slides

    Readings (supplementary, but you must understand suffix trees)


    Compression


    Readings

    Slides


    Introduction


    Slides


    Guy Blelloch, guyb@cs.cmu.edu.