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 318A
Office Hours
TBD
Teaching Assistants
TBD
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
- Homework 0 (due Wednesday Sep 11)
- Homework 1 (due Wednesday Sep 25)
- Homework 2 (due Wednesday Oct 9)
- Homework 3 (due Wednesday Oct 23)
- Homework 4 (due Wednesday Nov 6)
- Homework 5 (due Wednesday Nov 13)
- Homework 6 (due Wednesday Dec 4)
(Tentative) Schedule
Date | Topic | Links |
---|---|---|
Sep 04 | Course Overview and Basics Review | |
Divide and Conquer | ||
Sep 09 | Karatsuba Multiplication, Strassen’s Algorithm | |
Sep 11 | Median of Medians, FFT | |
Dynamic Programming | ||
Sep 16 | Edit Distance, Knapsack | |
Data Structures and Amortized Analysis | ||
Sep 18 | Binomial Heaps | |
Randomized Algorithms | ||
Sep 23 | Probability Review, Quicksort | |
Sep 25 | Concentration of Measure and Applications | |
Sep 30 | Hashing | |
Linear Programming and Optimization | ||
Oct 02 | Linear Programming I | |
Oct 07 | Linear Programming II | |
Oct 09 | Flows and Matchings | |
Oct 14 | Intro to Gradient Descent | |
Limits of Computation | ||
Oct 16 | Limits of Computation and the Complexity Hierarchy | |
Oct 21 | NP-Hardness and Reductions | |
Combatting Intractability | ||
Oct 23 | Approximation Algorithms I | |
Oct 28 | Approximation Algorithms II | |
Oct 30 | Fast(er) Exponential Time Algorithms | |
Nov 04 | Beyond Worst-Case Algorithms | |
Decision Making Under Uncertainty | ||
Nov 06 | Online Algorithms and Competitive Analysis | |
Nov 11 | The Experts Problem and Multiplicative Weights | |
Nov 13 | The Online Primal Dual Method | |
Nov 18 | Random Order Online Algorithms | |
Misc Topics | ||
Nov 20 | Beyond Worst Case Analysis | |
Nov 25 | Dimensionality Reduction, Johnson-Lindenstrauss | |
Nov 27 | Thanksiving Break, No Class | |
Dec 02 | Locality Sensitive Hashing | |
Dec 04 | Low Recourse Algorithms | |
Dec 09 | TBD | |
Dec 11 | TBD |