CSE 521p: Algorithms (Spring 2015)

[course description | lectures | project | discussion board] | related material] | important announcements]

important announcements

• Reminder that your final project report is due June 6 and comments on other people's projects are due June 11. No late projects accepted!
• Although I will review a bit in class, if you are rusty, I suggest you spend a bit of time reviewing basics of probability. here are some resources:
  • probability review from Andrew Ng's, machine learning class
  • Notes on tail bounds by Jeff Erickson.
  • Chapters 17-19 (you may also need to look at Chapter 15) of book by Lehman, Leighton and Meyer.
  • Video lectures from MIT course: see lectures 18-24, possibly you'll also need 16-17
  • Chapters 1-3 of Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal.
• Here are the guidelines for the project.
• Here is how you can send email to the class.

lectures

• [AIRW] -- Algorithms in the Real World (Blelloch/Gupta)

• March 30: Overview, List update (notes + slides), Matching (notes + slides), Hashing (slides)
  • References:
    • Section 1.1 of Adam Kalai's thesis (See section 1.1)
    • Online algorithms notes by Susanne Albers (Check out section 5, and page 26)
    • Auction algorithm for bipartite matching, description by Noam Nisan
    • Hashing References:
      • Notes by Jeff Erickson
      • Lecture notes by Sanjeev Arora
      • Notes and pointers from [AIRW]
      • Summer School on Hashing - Theory and Applications at the University of Copenhagen

• April 5: Universal hashing and perfect hashing, linear probing (slides (29-51) + notes), Bloom filters, max load and power of two choices notes
  • References:
    • Lecture notes by Sanjeev Arora (See sections 4 and 5)
    • Notes from [AIRW] (See section 2.3)
    • Notes from [AIRW] (See sections 1-3)
    • Bloom Filter survey by Broder and Mitzenmacher
    • Hash based techniques for high-speed packet processing by Kirsch, Mitzenmacher and Varghese
    • Notes on tail bounds by Jeff Erickson.
    • Analysis of linear probing, video of first lecture by Rasmus Pagh, roughly from minute 37 on.
    • Power of two choices, original paper.
    • Power of two, survey by Mitzenmacher, Richa and Sitaraman.

• April 13: Streaming algorithms: ( intro slides), Heavy hitters, (notes), Distinct elements and document similarity (notes).
  • References (read in this order):
    • Lecture notes on heavy hitters and Count-Min sketch by Roughgarden and Valiant.
    • Lecture notes on distinct elements, minhash, and document similarity by Arora.
    • Chapter from data mining book on finding similar items by Rajaraman, Leskovec and Ullman. (See sections 3.1- 3.4).
    • Chapter from data mining book on streaming by Rajaraman, Leskovec and Ullman. (See especially sections 4.4 and 4.5.)
    • Notes from [AIRW].
    • Origins of document similarity algorithm at Alta Vista by Broder.
    • Survey on data streams, algorithms and applications by Muthukrishnan.
    • Survey on sketch techniques for approximate query processing by Cormode.
    • Lecture notes on streaming algorithms by Chakrabarti.

• April 20: More streaming -- second frequency moment [AMS] (notes) and locality sensitive hashing (notes)
  • References (read in this order):
    • Notes on frequency moments by Roughgarden. (See sections 2-6).
    • Survey on locality sensitive hashing by Andoni and Indyk (with opening by Chazelle) -- follow references from here.
    • Chapter from data mining book on finding similar items and LSH by Rajaraman, Leskovec and Ullman.
    • Original paper on space complexity of frequency moments by Alon, Matias and Szegedy.

• April 27: Linear programming (notes)
  • References:
    • chapter from algorithms textbook by DasGupta, Papadimitriou and Vazirani.
    • great introduction to linear programming book by Matousek and Gartner.

• May 4: More on linear programming, including duality. (notes)
  • References:
    • Lecture notes from course taught by Anupam Gupta and Ryan O'Donnell:
      • LPs: an algebraic view
      • Geometry of LPs
      • LP examples: max-flow, matching, vertex-cover
      • Duality
      • Applications of duality
    • great introduction to linear programming book by Matousek and Gartner.
• May 11: LP Based Approximation Algorithms (notes), Intro to adaptive decision-making (notes).
  • References:
    • Notes by Sanjeev Arora
    • Chapter 1 and Sections 4.1-4.3 of book by Williamson and Shmoys
    • Notes #1 and Notes #2 by Sanjeev Arora
    • Arora Hazan, Kale survey
• May 18: More on adaptive decision making, multiplicative weights update algorithm, zero-sum games, applications, etc. (notes)

• June 1: Presentations:
  1. Jonathan Barone and Matt Cohn: Efficient Use of One-Way Functions for Program Obfuscation
  2. Arjit Basu and David Straily: Tries and Efficient Hash Tables - A Comparison
  3. Kevin Binz and Seja Filipi: Studying Nash Equilibria in game theoretic problems from an algorithmic perspective
  4. Shabinaz Chemnad P and Andrew Gawronski: Exploring the TRIE data structure and its various optimizations
  5. Yi Li and Calvin Hopkins: Sequence Alignment Problems
  6. Matthew Smith and Daniel Leita: Theoretical and Practical Limits of Clock Synchronization over a Network
  7. Ioana Pop and Vasily Tarasov: Properties of the Traffic Light Problem

• June 8:
  1. Daniel Mejia and Perry Zheng: Locality Sensitive Hashing on Algebird
  2. Nick Walker and Swagat Mishra: Coding theory and forward error correction with a focus on Reed-Solomon coding
  3. Weiping Zhang and Kefu Zhao: Predicting NBA Game Outcomes using Linear SVMs
  4. Mayank Mishra and Abdul Salama: RNA Secondary Structure Prediction
  5. Aaron Roney and Matthew Williams: On LSH and Distance Measures
  6. Eric Orth: Parallel Algorithms
  7. Lon C. Lundgren: Surveying the Usage of Space Partitioning Data Structures and Algorithms
  8. Mukti Ranjan Sahoo: Cuckoo Hashing

course description

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Mondays, 6:30 -- 9:20pm in MGH 231
Office hours:  By appointment -- send email.

Teaching assistant: Kira Goldner
Office hours:

• Mondays, 5:30-6:20pm in CSE 218.
• Also by appointment -- send email.

Course evaluation: homework (~60%), project (~40%).

About this course:
We will study the design and analysis of algorithms from a modern perspective with a particular focus on techniques that find use in many subfields of computer science. The modern perspective means that there will be extensive use of randomization and approximation. Topics will include hashing and its many applications, linear programming and basics of convex optimization, decision making under uncertainty, dimension reduction, streaming, load balancing, etc.

related material

Courses at other universities:

• Algorithms in the Real World (Guy Blelloch and Anupam Gupta)
• Advanced Algorithms (Sanjeev Arora)