CS 513: Design and Analysis of Data Structures and Algorithms

Fall 2024, Rutgers University

Time and Location
Monday, Wednesday, 2:00pm – 3:20pm, Hill 116

Instructor
Roie Levin, Core 306

Office Hours
Monday 10:00am – 12:00pm

Teaching Assistant
Songhua He – Monday 7:00pm – 8:00pm, Zoom, Wednesday 3:30pm - 4:30pm, Hill 410.

Course Description

The course covers a broad set of topics in algorithms design and analysis. The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) become reasonably proficient at using these tools, (c) be able to reason about the correctness and performance of the resulting algorithms. Towards the end of the course, students will get some exposure to modern trends in algorithms research.

I will expect students with undergraduate algorithms knowledge. There will be a Homework 0: if you plan to take this course, please make sure you are comfortable with the material therein.

Topics I plan to cover include:

  1. Divide and conquer.
  2. Dynamic programming.
  3. Randomized algorithms.
  4. NP-hardness and intractability.
  5. Linear Programming.
  6. Approximation algorithms.
  7. Online algorithms.

Homework

All homework is due at 11:59 pm on the specified day. The lowest homework grade will be dropped.

(Tentative) Schedule

Date Topic Lecture Notes Optional Reading
Divide and Conquer      
Sep 04 Course Overview and Basics Review, Karatsuba Multiplication notes Possible textbooks for an undergrad course: Tim Roughgarden’s textbook, CLRS textbook, DPV textbook
Sep 09 Strassen’s Algorithm, Median of Medians notes Some (advanced) intuition for Strassen’s algorithm: 1, 2
Dynamic Programming      
Sep 11 Edit Distance, Knapsack notes More fun examples of DP from Kleinberg Tardos textbook (slides from Kevin Wayne): 1, 2
Data Structures and Amortized Analysis      
Sep 16 Dijkstra’s and Amortized Analysis Techniques notes Anupam Gupta’s amortization notes and shortest path slides, Jeff Erickson’s notes
Sep 18 Binomial Heaps, Fibonacci Heaps notes Kevin Wayne’s slides on binary & binomial heaps and on Fibonacci heaps
Greedy Algorithms      
Sep 23 Fibonacci Heaps Wrapup, Minimum Spanning Trees and Union Find notes Animations of Kruskal & Prim’s algorithm, Notes from CMU class taught by Acar, Blelloch, Reid-Miller, Michel Goemans’ intro to matroid theory notes
Randomized Algorithms      
Sep 25 Probability Review, Karger’s min-cut Algorithm, Quicksort notes Online probability textbook by Pishro-Nik, Chapters 0-5. Textbooks on randomized algorithms: Mitzenmacher & Upfal, Motwani & Raghavan
Sep 30 Concentration of Measure and Applications notes Pishro-Nik textbook, Chapter 6. Many great books on concentration of measure: Dubhasi & Panconesi, Boucheron, Lugosi, Massart, Vershynin. Also 5 proofs of Chernoff bounds, pick your favorite!
Oct 02 Applications of Chernoff bounds, Valiant Hypercube Routing notes Chapter 4.6.1 in Mitzenmacher & Upfal 2nd edition, Valiant’s original paper
Oct 07 Wrap-up Hypercube Routing, Hashing notes Anupam Gupta’s lecture notes on hashing and discussion of other collision resolution schemes
Oct 09 Perfect Hashing, Bloom Filters notes Why the classic Bloom Filter analysis is a little wrong and how to fix it
Linear Programming and Optimization      
Oct 14 Flows and Matchings notes Animations of basic flow algorithms. Kleinberg & Tardos textbook has good chapters on flow. David Williamson’s textbook for more advanced flow algorithms.
Oct 16 Linear Programming I: Modeling, Intuition behind algorithms notes Excellent textbook by Matoušek/Gärtner. Online LP solver, more serious solvers: CVXOPT, COIN-OR. Commerical solvers: Gurobi, CPLEX.
Oct 21 Linear Programming II: Duality notes Proof of Strong duality from Anupam Gupta and Ryan O’Donnell’s course on linear and semidefinite programming. Also applications of duality I II from the same course. Notes on duality in more general convex programs from Ryan Tibshirani’s course.
Oct 23 Intro to Gradient Descent notes Potential Function Proofs of Gradient Descent variants by Bansal and Gupta, Boyd and Vandenberghe’s comprehensive textbook on convex optimization, More advanced survey by Sébastien Bubeck.
Limits of Computation      
Oct 28 Limits of Computation and the Complexity Hierarchy notes Excellent undergrad textbook on formal models of computation by Michael Sipser. More advanced graduate level textbook on modern complexity theory by Arora and Barak.
Oct 30 NP-Completeness, the Cook-Levin Theorem, Reductions notes Karp’s 21 NP-Complete Problems, and his original paper. Garey and Johnson’s calatogue of NP complete problems.
Combatting Intractability      
Nov 04 More Reductions, Approximation Algorithms I - Vertex Cover notes Shmoys and Williamson textbook on approximation algorithms.
Nov 06 Approximation Algorithms II - Set Cover notes Chapter 1 of Shmoys and Williamson textbook. Ola Svensson’s course on Set Cover.
Nov 11 Approximation Algorithms III - More Set Cover, TSP notes Chapter 1 and 2.4 of Shmoys and Williamson textbook.
Nov 13 FPT Algorithms notes Parameterized Algorithms textbook by Cygan et al.
Nov 18 Fast(er) Exponential Time Algorithms notes Moser & Scheder paper on derandomizing Schoening’s algorithm
Decision Making Under Uncertainty      
Nov 20 Online Algorithms and Competitive Analysis    
Nov 25 Thanksiving Break, No Class    
Nov 27 Thanksiving Break, No Class    
Dec 02 The Experts Problem and Multiplicative Weights    
Dec 04 The Online Primal Dual Method    
Misc Topics      
Dec 09 Locality Sensitive Hashing    
Dec 11 Final Exam, In-class