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:
- Divide and conquer.
- Dynamic programming.
- Randomized algorithms.
- NP-hardness and intractability.
- Linear Programming.
- Approximation algorithms.
- Online algorithms.
Homework
All homework is due at 11:59 pm on the specified day. The lowest homework grade will be dropped.
- Homework 0 (due Wednesday Sep 11). Solutions.
- Homework 1 (due Wednesday Sep 25). Solutions.
- Homework 2 (due
Wednesday Oct 9Friday October 11). - Homework 3 (due Thursday Oct 31).
- Homework 4 (due Wednesday Nov 6).
- Homework 5 (due Wednesday Nov 13).
- Homework 6 (due Wednesday Dec 4).
(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 | 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 | ||
| Oct 23 | Intro to Gradient Descent | ||
| Limits of Computation | |||
| Oct 28 | Limits of Computation and the Complexity Hierarchy | ||
| Oct 30 | NP-Hardness and Reductions | ||
| Combatting Intractability | |||
| Nov 04 | Approximation Algorithms I | ||
| Nov 06 | Approximation Algorithms II | ||
| Nov 11 | Fast(er) Exponential Time Algorithms | ||
| Nov 13 | Beyond Worst-Case Algorithms | ||
| Decision Making Under Uncertainty | |||
| Nov 18 | Online Algorithms and Competitive Analysis | ||
| Nov 20 | The Experts Problem and Multiplicative Weights | ||
| Nov 25 | The Online Primal Dual Method | ||
| Nov 27 | Thanksiving Break, No Class | ||
| Dec 02 | Thanksiving Break, No Class | ||
| Misc Topics | |||
| Dec 04 | Dimensionality Reduction, Johnson-Lindenstrauss | ||
| Dec 09 | Locality Sensitive Hashing | ||
| Dec 11 | Low Recourse Algorithms | ||
| Final Exam, In-class |