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
4. Monday, Oct 7, 2024: Double hashing. Construction of pairwise independent hash functions.
5. Wednesday, Oct 9, 2024: Remainder of Chapter 1
6. Monday, Oct 14, 2024: Beginning of Chapter 2 until middle of Chapter 2.2
7. Wednesday, Oct 16, 2024: From Chapter 2.2 to the end of Chapter 2.6
8. Monday, Oct 21, 2024. Johnson-Lindenstrauss projection and beginning of Chapter 3 until (including) Matrix Identity testing
9. Wednesday, Oct 23, 2024: Schwarz-Zippel Lemma and testing for matching in bipartite graphs (we skipped the extensions to finding the matching and the extension ro general graphs). Beginning of Linear Algebra chapter until "A geometric interpretation"
10. Monday, Oct 28: Linear algebra until the end of Section 4.4
11. Wednesday, Oct 30: Finished Chapter 4. Started with basic def. in Chapter 5
12. Monday, Nov 4: Spectral Graph Theory
13. Wednesday, Nov 6: Proof of Cheeger's inequality and the power method. Finished the Spectral Graph Theory Chapter
14. Monday, Nov 11: Veterans Day (NO CLASS)
15. Wednesday, Nov 13: Linear Programming (remotely) until the ellipsoid method (end of Chapter 6.3)
    
16. Monday, Nov 18: Convex programming (Chapter 6.4) and semidefinite programming (Chapter 6.5)
17. Wednesday, Nov 20: LP-based approximation algorithms for vertex cover and set cover. MaxCut until the SDP integrality gap example.
18. Monday, Nov 25: Goemans-Williamson algorithm, LP duality, started with Nash equilibria in zero sum games
19. Wednesday, Nov 27: Proof of Nash equilibria in zero sum games
20. Monday, Dec 2: Submodular functions. LAST CLASS.
    

Problem sets

• Homework 1, due Friday, Oct 4, 2024, 11pm on GradeScope.
• Homework 2, due Friday, Oct 11, 2024, 11pm on GradeScope.
• Homework 3, due Friday, Oct 18, 2024, 11pm on GradeScope.
• Homework 4, due Friday, Oct 25, 2024, 11pm on GradeScope. Added clarification to Ex 1.(iii) on Oct 20 and corrected Ex 1.(ii).
• Take home midterm exam, due Friday, Nov 1, 11pm on GradeScope. Updated on Oct 30: depth(C_v) should be depth(v).
• Homework 5, due Friday, Nov 8, 2024 on GradeScope. Updated on Nov 6: The t >= 1 should be t >= 0 in Hanson-Wright.
• Homework 6, due Friday, Nov 15, 2024 on GradeScope.
• Homework 7, due Friday, Nov 22, 2024 on GradeScope.
• Homework 8, due Friday, Dec 6, 2024 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.
  
• Oct 8, 2024: Cleaned up the analysis of Double Hashing (the variables Y_ij were not needed here).
• Oct 17, 2024: In Johnson-Lindenstrauss projection, the matrix G is a k*d matrix and not k*n
• Oct 28, 2024: Fixed some indices and sums in Chapter 4
• Nov 3, 2024: Alternative def. of ||A||_F on page 72 needed square roots. Update to proof of Cheeger's inequality: it is not actually the AVERAGE cut S_t that works. x*(D-A) was missing a second x. The (x_i-x_j) missed a square. In the proof of Cheeger's inequality, several L_G's should be \tilde{L}_G.
• Dec 2, 2024: Marginal increase of a submodular function is f(A | B) := f(A \cup B) - f(B) instead of f(A | B) := f(A \cup B) - f(A)