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

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.

Compression

Web page

Readings

Slides

Error Correcting Codes

Web page

Scribe Notes

  • Error Detecting and Correcting Codes (scribe notes by Daniel Maynes-Aminzade and Andrew Faulring).
  • Reed-Solomon Codes (scribe notes by Anton Likhodedov and Trey Smith).
  • Decoding Reed-Solomon Codes (scribe notes by Amitabh Sinha).
  • Tornado Codes (scribe notes by Sonesh Surana).

    • Readings

  • 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.

    • Cryptography

    Web page

    Readings

    Slides

    Internet Algorithms and Protocols

    Web page

    Scribe Notes

  • Telephony, Modems, and Ethernet (scribe notes by Monica Rogati).
  • Internet Protocols (scribe notes by Rob Miller).
  • Routing Protocols (scribe notes by Daniel Blanford and Carl Eastlund).
  • Multicast Protocols (scribe notes by Simon Goldsmith).
  • Caching and Consistent Hashing (scribe notes by Bianca Schroeder).

    • Indexing and Searching

    Web page

    Slides

    Readings

  • Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images, Chapter 3: Indexing. Van Nostrand Reinhold, 1994.
  • 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, 46(5), 1999.

    • Additional Readings

    These two readings are on the notion of resemblance discussed in class on Dec 7.
  • 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

    From when the course was given in 1997.
  • Indexing 1 (Helen Wang) -- the first half of these notes are left over from the previous topic that was covered (pattern matching in computational biology).
  • Indexing 2 (Ben Horowitz)
  • Evolutionary Trees and Indexing 3 (draft) (Amar Chaudhary)
    • Back to the Algorithms in the Real World page (V. 2000).
    Guy Blelloch, guyb@cs.cmu.edu.