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:
  
  1. Randomized algorithms
     
  2. The curse of dimensionality and dimension reduction
     
  3. Algebraic algorithms
     
  4. Linear algebra
     
  5. Spectral graph theory
     
  6. Linear programming
     
  7. 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:
• Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
• Foundations of Data Science by John Hopcroft and Ravi Kannan
• Spectral Algorithms by Ravi Kannan and Santosh Vempala
• Sketching as a Tool for Numerical Linear Algebra by David Woodruff
  
  
• 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

1. Wednesday, Sep 25, 2024. First day of class. Chapter 1: Karger's algorithm and the Karger-Stein algorithm.
2. Monday, Sep 30, 2024. Chapter 1: Probability theory.
3. Wednesday, Oct 2, 2024: Hoeffding inequality
   

Last day of class will be Wednesday, Dec 4, 2024.

Problem sets

• Homework 1, due Friday, Oct 4, 2024, 11pm on GradeScope.
• Homework 2, due Friday, Oct 11, 2024, 11pm on GradeScope.
  

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.