Algorithms

CSE 521p: Applied Algorithms (Winter 2019)

important announcements

homework submission: You will use gradescope to upload your homework solutions. (Here is gradescope help.) here are some instructions about how to submit. You should be enrolled in the CSEP521p Gradescope roster using your uw.edu email. You can change your gradescope password here (if you enter with your uw.edu email). If you do not see CSE521p on your dashboard, please send email to Alon (alonmil@cs.washington.edu) right away.
probability and linear algebra review info
programming resources
project: Here are the guidelines. due March 17.

lectures

January 10: Administrivia, online algorithms, matching and mini probability review
- References:
  - List update: Section 1.1 of Adam Kalai's thesis
  - Online algorithms notes by Susanne Albers (Check out section 5, and page 26)
  - Auction algorithm for bipartite matching, description by Noam Nisan
January 17: Finish matching + intro to universal hashing (my messy notes)
- References:
  - Lecture notes on hashing by Sanjeev Arora (Sections 2-4).
  - Hashing notes from [AIRW] (Sections 1-3)
  - High speed hashing for integers and strings by Thorup.
January 24 : Bloom filters, intro streaming, heavy hitters and the count-min sketch
- References:
  - Bloom Filter survey by Broder and Mitzenmacher
  - Lecture notes on heavy hitters and Count-Min sketch by Roughgarden and Valiant.
  - Chapter from data mining book on streaming by Rajaraman, Leskovec and Ullman. (See especially sections 4.4 and 4.5.)
  - 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.
January 31 : Tail bounds + normal r.v.s, distinct elements, dimension reduction (my messy notes)
- References:
  - Distinct elements by Arora
  - Lecture notes on similarity metrics and kd-trees by Roughgarden and Valiant.
  - Lecture notes on dimensionality reduction and more by Roughgarden and Valiant.
February 7: Locality sensitive hashing (my messy 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.
February 14: Principal components analysis (PCA) (my messy notes)
- References:
  - Understanding and using PCA by Roughgarden and Valiant.
  - How PCA works by Roughgarden and Valiant.
February 21: Singular value decomposition (SVD) and low rank approximations; the Perceptron algorithm (my messy notes)
- References:
  - SVD and low-rank matrix approximations by Roughgarden and Valiant.
  - Notes on Perceptron Algorithm by Kilian Weinberger
February 28: PAC learning, Gradient descent and SGD (my messy notes)
- References:
  - Generalization, or how much data is enough? by Roughgarden and Valiant.
  - Gradient descent (and beyond) by Kilian Weinberger
  - Gradient descent by Sanjeev Arora.
March 7: Online learning and applications (my messy notes)
- References:
  - Online learning and the multiplicative weights algorithms by Tim Roughgarden
  - Applications of multiplicative weight updates by Sanjeev Arora.
  - Intro to boosting, by Freund and Schapire.
March 14: Student presentations

probability and linear algebra review resources

Probability: Although I will review a bit in class, if you are rusty, I highly recommend that you spend a bit of time reviewing basics of probability. here are some resources:
- probability review from Andrew Ng's, machine learning class
- Here are two videos that do a quick review of probability: video 1 and video 2
Linear algebra resources:
- linear algebra review from CS 229 at Stanford.
- These 3Blue1Brown videos on the essence of linear algebra are wonderful.

programming references

Programming: For the programming portions of the homeworks, you are welcome to use any programming language you like, though you are encouraged to use either matlab or Python together with the Numpy and Pyplot packages. Here are some programming resources:

course description

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

Teaching assistants:

Alon Milchgrub: send email.
Guanghao Ye: send email.
Office hours:
- Thursdays, 5:30-6:20pm. In CSE305 for the remote students and in CSE303 for the local students
- Also by appointment -- just send email.

If you are having trouble logging into the discussion board: Try logging into gmail.uw.edu using your UW NetID. Then go to the Groups App. The class group should appear under "My Groups". (If this still doesn't work, send Anna email.)

Course evaluation: 4-5 homeworks, mix of programming and theoretical exercises (~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 are likely to include hashing (e.g., perfect hashing, load balancing, consistent hashing, bloom filters, applications to streaming), data with distances (similarity search, nearest neighbor, dimension reduction, locality sensitive hashing), linear algebraic techniques such as principal components analysis, linear programming and basics of convex optimization and decision making under uncertainty. etc. The material will overlap significantly with this wonderfully cool class at Stanford.

related material

Courses at other universities: