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:

  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

  • 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