CSE 521: Algorithms (Spring 2015)
| discussion board]
| related material]
| 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:
- Here are the guidelines for the project.
- Here is how you can send email to the class.
Key (see references below):
- [AIRW] -- Algorithms in the Real World (Blelloch/Gupta)
- March 31: Overview, List update, Matching
- April 2: Hashing overview,
intro and perfect hashing notes
- April 7:
(slides (29-51) +
- April 9: No class
- April 14:
Load balancing and power of two choices
and streaming algorithms: (intro slides),
- April 16:
More streaming: distinct elements
(notes), and frequency moments [AMS]
- April 21:
Locality sensitive hashing (notes)
- April 23: Intro to linear programming
- April 26, 28 and May 5: More on linear programming, including duality.
- May 7, 12: LP Based Approximation Algorithms
- May 14 and 19: Adaptive decision making, multiplicative weights update algorithm, zero-sum games, applications
- May 21, 26 and 28: intro to spectral graph theory
- 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.
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
- 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,
Courses at other schools: