15-853: Algorithms in the Real World (Guy Blelloch and Bruce Maggs, Fall 03)

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.

Algorithms for the Web

  • load balancing in conent delivery networks. Course notes from a lecture given at MIT, on the same topic as Bruce covered on Nov 17.
  • Chapters 3 and 4 from: Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images.
    Only available in hardcopy. Handed out in class, and available outside of Wean 7116.
  • Andrei Broder, Moses Charikar, Alan Frieze, and Michael Mitzenmacher. Min-wise independent permutations. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 327-336, May 1998.
  • We actually neger got to this topic Michael W. Berry, Zlatko Drmac, Elizabeth R. Jessup. Matrices, Vector Spaces, and Information Retrieval. SIAM Review, 41(2), 1999.

    • Slides

    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.
  • Linear Programming 2 (Steven Czerwinski). Scribe notes on interior-point methods from a previous version of the course.
  • 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
  • E. L. Johnson and G. L. Nemhauser. Recent developments and future directions in mathematical programming. This is a good overview of optimization techniques including both linear and integer programming.
  • 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

    Separators

    Readings

  • Scribe notes from 2002: (not exactly what we are covering this year, but close)
  • Lecture 1, by Barbara Anthony (in ps)
  • Lecture 2, by Flavio Lerda (in pdf or ps).
  • Lecture 3, by Ryan Williams (in pdf or ps).
  • Lecture 4, by Hubert Chan (in ps).
  • A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs. George Karypis, Vipin Kumar
  • R.J. Lipton, D.J. Rose, and R.E. Tarjan.
    Generalized Nested Dissection.
    SIAM J. Numer. Anal., 16 (1979), 346--358.
    (As far as I can tell, this is not available online.)
  • (Optional) Spectral Partitioning Works: Planar graphs and finite element meshes, Daniel Spielman and Shang-Hua Teng. In addition to proving properties about spectral partitioning, this gives a very good history of spectral partitioners and overview of the technique.

    • Slides

    Error Correcting Codes

    Web page

    Readings

  • Tornado Codes (scribe notes by Cha Zhang, 2002).
  • Coding Theory: Tutorial and Survey by Madhu Sudan at MIT.
  • The complexity of error correcting codes. An overview by Dan Spielman. This goes into more theory and gives an overview of some more recent results.
  • Error-correcting Codes (lecture notes of Steve Linton at U. St Andrews). This gives a reasonably nice overview of linear and Hamming codes. (I could not get throught last time I tried).

    • Slides

    Cryptography

    Web page

    Readings

    Slides

    Introduction

    Slides

    Graph Separators

    Linear and Integer Programming

    Web Algorithms

    Back to the Algorithms in the Real World page (V. F2003).
    Guy Blelloch, guyb@cs.cmu.edu.