CSE 521: 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.
  • 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 31: Overview, List update, Matching
  • References:
    • Adam Kalai's thesis (see Section 1.1)
    • Online algorithms notes by Susanne Albers (see page 26 and section 5).
    • Auction algorithm for bipartite matching, by Noam Nisan
• April 2: Hashing overview, intro and perfect hashing notes
  • 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 7: Linear probing (slides (29-51) + notes), Bloom filters.
  • References:
    • Notes on tail bounds by Jeff Erickson.
    • Notes from [AIRW]
    • Bloom Filter survey by Broder and Mitzenmacher
    • Hash based techniques for high-speed packet processing by Kirsch, Mitzenmacher and Varghese
    • Analysis of linear probing, video of first lecture by Rasmus Pagh, roughly from minute 37 on.
• April 9: No class

• April 14: Load balancing and power of two choices (notes) and streaming algorithms: (intro slides), heavy hitters (notes).
  • References:
    • 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 streaming by Rajaraman, Leskovec and Ullman. (See especially sections 4.4 and 4.5.)
    • Power of two choices, original paper.
    • Power of two, survey by Mitzenmacher, Richa and Sitaraman.
    • Notes from [AIRW].
    • 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 16: More streaming: distinct elements (notes), and frequency moments [AMS] (notes).
  • References:
    • Distinct elements: lecture notes, part 1 and lecture notes, part 2.
    • Notes on frequency moments by Roughgarden. (See sections 2-6).
    • Original paper on space complexity of frequency moments by Alon, Matias and Szegedy.
• April 21: Locality sensitive hashing (notes)
  • References:
    • 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.
    • Origins of document similarity algorithm at Alta Vista by Broder.
• April 23: Intro to linear programming (notes)
  • References:
    • chapter from algorithms textbook by DasGupta, Papadimitriou and Vazirani.
    • great introduction to linear programming book by Matousek and Gartner.

• April 26, 28 and May 5: 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 7, 12: LP Based Approximation Algorithms (notes)
  • References:
    • Notes by Sanjeev Arora
    • Chapter 1 and Sections 4.1-4.3 of book by Williamson and Shmoys
    • Section 11.7 of Kleinberg and Tardos Algorithms Textbook.
    • Chapter 1, and Sections 2.1 and 3.1 of book by Lau, Ravi and Singh
• May 14 and 19: Adaptive decision making, multiplicative weights update algorithm, zero-sum games, applications (notes)
  • References:
    • Notes #1 and Notes #2 by Sanjeev Arora
    • Arora Hazan, Kale survey

• May 21, 26 and 28: intro to spectral graph theory
  • References:
    • Lecture notes by Luca Trevisan
    • Chapter by Dan Spielman

• June 2: Presentations: Black and Kaufmann, Cai and Golub, Campbell and Morgan, Levey.

• June 4: Presentations: Elliott and Xu, Garlapati and Holynski, Lebeck and Whitmire, Lu and Yu, Dubinets.

• Wednesday, June 10 (10:30 -- 12:20pm): Chen and Nied, Jaech and Vashistha, Goldner, Seo, Lee and Teo, Hixon and Rashkin.

course description

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Tuesdays and Thursdays in , 9:30-10:50pm
Office hours:  By appointment -- send email.

Teaching assistant: Jeffrey Hon
Office hours:

• Mondays (CSE 218) and Wednesdays (CSE 220). Both days 3-3:45pm
• 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 subfield 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 schools:

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