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

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.

Error Correcting Codes

Web page

Readings

  • Scribe notes from Fall 2000 and Fall 2002.
  • Error Detecting and Correcting Codes (scribe notes by Daniel Maynes-Aminzade and Andrew Faulring, 2000).
  • Reed-Solomon Codes (scribe notes by Anton Likhodedov and Trey Smith, 2000).
  • Tornado Codes (scribe notes by Cha Zhang, 2002).
  • Error-correcting Codes (lecture notes of Steve Linton at U. St Andrews). This gives a reasonably nice overview of linear and Hamming codes.
  • 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.

    • Slides

    Graph Separators

    Readings

  • Scribe notes:
  • 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) Nested Dissection: A Survey and comparison of various nested dissection algorithms, Khaira, Miller and Sheffler.
  • (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.
  • (Optional) Compact Representations of Separable Graphs (Draft) D. Blandford, G. Blelloch, and I. Kash. Describes a version of the graph compression application of separators discussed in class.
  • (Optional) Improving The Run Time And Quality Of Nested Dissection Ordering. Bruce Hendrickson and Edward Rothberg. (Describes a multilevel vertex separator.)

    • Logistics

    Readings

  • Scribe notes:
  • Lecture 1, by Krithika Venkataramani (DRAFT in ps)
  • Lecture 2, by Zhong Xiu (DRAFT in ps or pdf)
  • Slides from a talk on Approximation Algorithms for Buy-at-bulk Network Design by R. Ravi. This talk covers much of what was covered in class.
  • The following two papers are also relevant: On the Integrality Gap of a Natural Formulation of the Single-Sing Buy-at-bulk Network Design Problem (2001) and Single-sing Buy-at-bulk LP had Constant Integrality Gap (2002).
  • Adam Meyerson's paper on Buy At Bulk. This pretty much covers the lecture of October 23.

    • Content Delivery Networks

    Readings

  • Paper on "Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web", by Karger et. al.

    • Slides

    Indexing and Searching

    Web page

    Readings

  • 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.
  • Michael W. Berry, Zlatko Drmac, Elizabeth R. Jessup. Matrices, Vector Spaces, and Information Retrieval. SIAM Review, 41(2), 1999.
  • Jon M. Kleinberg, Authoritative sources in a hyperlinked environment JACM, 1999.
    • The following two are for the lecture on Novermber 25.
  • Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey Zweig, Syntactic Clustering of the Web, SRC Technical Note 1997-015, July 25, 1997
    Mostly discusses the systems aspects.
  • 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.
    Discusses the theory behind it.

    • Scribe Notes

    Slides

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