CSE P521: Applied Algorithms

Winter, 2017

Professor: James R. Lee

Office hours: By appointment

TA (head): Evan McCarty (ejmcc@uw)

Office hours: Wed, 5:30-6:20pm (CSE 218 on Jan 11, CSE 220 after that)

TA: Jeffrey Hon (jhon@cs)

Office hours: Tue, 6-7pm, CSE 218

Wed 6:30-920pm JHN 075

Email and discussion:

Class email list: multi_csep521a_wi17@uw [click link to sign up]     [archives]
Discussion board

Reading material:

This course has no official textbook. You will find most of the content in the course lecture notes which will be posted below. Additionally, for certain lectures there will be required reading that should be completed before class. For optional reading and links to related courses, see the related material.


Lectures

A red label indicates the most important material to look over.

A green label indicates material that should be read before the lecture.

date topics slides notes reading
4-Jan
  • Randomized min-cuts
  • Perfect hashing
  • Universal hashing
pdf
11-Jan
  • Advanced hashing
  • Concentration inequalities
  • The power of two choices
pdf
18-Jan
  • Heavy hitters
  • The count-min sketch
pdf
25-Jan
  • Similarity search, metric spaces
  • k-d trees, cover trees, and intrinsic dimension
  • Locality-sensitive hashing
  • Dimension reduction
pdf
1-Feb
  • Gradient descent
  • Linear regression
  • Stochastic gradient descent
  • Regularization
8-Feb
  • Constrained optimization
  • Lagrangian multipliers
  • Entropy regularization
  • Online convex optimization
pdf
15-Feb Principal component analysis Power method still powerful
22-Feb Spectral graph theory and clustering pdf
1-Mar Incentives + algorithms
  • The price of anarchy
  • Mechanism design, auctions
  • Exchange networks
8-Mar Project presentations

Topics:

  • Hashing
  • Streaming
  • Sketching
  • Spectral analysis
  • Linear programming
  • Online optimization
  • Algorithmic game theory

Grading:

60% Homework, 40% Project

Homeworks:

« Instructions »

You may discuss problems with your classmates, but when you write down the solutions, you should do so by yourself. You can use the internet and books for reference material but you must cite every source that you consulted (the name of the book or web page suffices). You should also cite any classmates with whom you discussed solutions.

All homework should be turned in electronically to the Dropbox by the due date for the assignment. Homework should either be typeset or written very neatly and scanned.

Late days policy: Every student has three late days they may use throughout the course. Assignments are generally due at midnight; one late day means you have an additional 24 hours (until the next midnight).

Note on Bonus problems: These problems are usually quite challenging. If you do some of them, I will be impressed. But they are in no way required (or even suggested) for obtaining a good grade in the course.

[ Dropbox for assignments ]

  • Homework #1
    [Out: Thurs, 5-Jan; Due: Thurs, 12-Jan at midnight]
  • Homework #2
    [Out: Mon, 16-Jan; Due: Thurs, 26-Jan at midnight]
  • Homework #3
    [Out: Thurs, 26-Jan; Due: Thurs, 2-Feb at midnight]
  • Homework #4
    [Out: Fri, 3-Feb; Due: Fri, 10-Feb at midnight]
  • Homework #5
    [Out: Sat, 18-Feb; Due: Sat, 25-Feb at midnight]

Project:

Project is due by midnight on Sunday, March 5th. Proposal description

Related material: