CSE521 - Design and Analysis of Algorithms - Fall 2024
Course information
- Class schedule: MW
10:00 - 11:20am in MGH 271
- Instructor: Thomas Rothvoss,
rothvoss@uw.edu.
Office hour: We, 1-2pm in CSE 556
- Teaching assistant: Daogao Liu,
dgliu@cs.washington.edu
Office hour: Th 4-5pm on Zoom, see https://washington.zoom.us/j/5631952179
- Course description: 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, linear algebra, and
optimization. Topics will include randomized algorithms,
streaming, advanced data structures, dimensionality reduction,
clustering, low rank approximation, markov decision processes,
linear programming, etc.
The preliminary plan is to cover the following chapters:
- Randomized algorithms
- The curse of dimensionality and dimension reduction
- Algebraic algorithms
- Linear algebra
- Spectral graph theory
- Linear programming
- Submodular functions
- Prerequisites: This is a math-heavy theory graduate
class. Formally CSE major and CSE 326 or equivalent
is the requirement.
- Lecture notes: Lecture notes can be
found here. Updates will
be posted later. I would appreciate an email if you find a
mistake/typo.
- Additional reading: All required information will be in
the provided lecture notes. However, for the interested student,
additional material can be found in the following related
textbooks:
- Required Work:
- Your grade will be calculate as:
- 80%: Weekly homework assignments that will be submitted
via GradeScope
plus a take home midterm exam. The midterm will count with
the same weight as one of the homeworks.
- 20%: Final presentation project. More details later.
- Students are expected to read the lecture notes in parallel
to the lecture.
- Collaboration policy: You may work with other students
in finding solutions to homework problems, but please write up
solutions on your own. Please do not search the internet for
solutions. Solutions written in latex are preferred but not
required. For the take home mid term no collaboration is
allowed.
- Discussion forum: Other than in office hours, you may
ask questions on course content and homework on the course discussion
forum.
Covered material
- Wednesday, Sep 25, 2024. First day of class. Chapter 1:
Karger's algorithm and the Karger-Stein algorithm.
- Monday, Sep 30, 2024. Chapter 1: Probability theory.
- Wednesday, Oct 2, 2024: Hoeffding inequality
Last day of class will be Wednesday, Dec 4, 2024.
Problem sets
You can check your points on the GradeScope webpage.
Updates to the lecture notes
- Sep 25, 2024: Chapter 1. Index n-1 -> n-2. Event A_i to
E_i.
- Sep 27, 2024: Cleaned up the proof of Karger-Stein.
- Sep 30, 2024: Last equation in Lemma 1.2 needs to be <= and
not >=. Proof of Theorem 1.8 (Karger-Stein analysis) the
nominator should be (alpha*n-1)*alpha*n instead of
(alpha*n-2)*(alpha*n-1)
- Oct 2, 2024: Hoeffding inequality: Added remark that proof
gives weaker constant of 1/4 instead of 1/2.