15-853: Algorithms in the Real World (Spring 14)

Readings, Notes and Slides



Compression


Readings

Slides


Hashing


Lecture Notes and Pointers


Dimension Reduction and Near-Neighbor Searching


Lecture Notes


Parallel Algorithms


Readings

  • Parallel Algorithms by Guy Blelloch and Bruce Maggs. From Computer Science Handbook, Second Edition, Allen B. Tucker (Editor).
  • The connectivity algorithm Guy described on March 4th: "A Simple and Practical Linear-Work Parallel Algorithm for Connectivity" and based on low-diameter decompositions: "Parallel Graph Decomposition Using Random Shifts".
  • 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


    Linear and Integer Programming


    Readings


    String Searching


    Readings (supplementary, but you must understand suffix trees)

    Slides


    Computational Biology


    Readings

    Slides



    Coding and Error Correction


    Readings (supplementary)

    Slides



    Guy Blelloch and Anupam Gupta, guyb@cs.cmu.edu.