Recent Developments in Algorithm Design
An exploration of some recent research directions in algorithm design, with each topic covered in a set of 2-3 lectures by NYU faculty who are specialists in these areas.
Course Team:
Lectures: Thursday 2:00pm-4:30pm, 202 CIWW
Professors office hours: TBA
Course Format: Each topic will be discussed over a set of 2-4 lectures. The instructors will introduce the problems of interest, and discuss material will often be based on (recent) research papers. The goal of the course is to expose students to interesting algorithmic techniques, and also to the latest research trends in algorithm design. We hope that students will get a broad sense of the questions and techniques arising in algorithm design, and can then decide to focus on one of these topics for further research.
Prerequisites: Graduate level knowledge of algorithms required. For example, Honors Analysis of Algorithms (CSCI-GA.3520-001), Algorithms 2 (CS-GY 6043), Algorithmic Machine Learning and Data Science (CS-GY 6763), or similar graduate-level Algorithms courses. The material relies on not just algorithm design, but also probability, linear algebra, and calculus, so mathematical maturity is a must.
Grading breakdown: The course evaluation will be based on 4-5 homework sets, and a research project/presentation at the end of the course.
Resources: There is no textbook to purchase. We will post readings from books and research papers, which will be available free online or via the NYU library.
| Lecture # | Topic | Reading | Homework |
|---|---|---|---|
| Approximation Algorithms Part I (Prof. Gupta) | |||
| 1. 1/23 | Approximation
Algorithms I:
Set Cover Solved in Several Styles |
Williamson-Shmoys Chap.1 | |
| Stochastic Probing and Sequencing Problems (Prof. Hellerstein) | |||
| 2. 1/30 | Approximation algorithms for generalizations and variants of set cover | ||
| 3. 2/6 | Stochastic Function Evaluation I:
Exact algorithms and major open questions in Stochastic Boolean Function Evaluation |
||
| 4. 2/13 | Stochastic Function Evaluation II:
Approximation algorithms, examples and techniques |
||
| Approximation Algorithms Part II (Prof. Gupta) | |||
| 5. 2/20 | Approximation Algorithms II: Clustering and Routing Problems |
||
| 6. 2/27 | Approximation Algorithms III: Network Design |
||
| Randomized Data Structures (Prof. Farach-Colton) | |||
| 7. 3/6 | Background: Concentration Bounds and Explicit Construction of Hash Functions | ||
| 8. 3/13 | Hash Tables | ||
| 9. 3/20 | History independent Data Structures | ||
| Graph Algorithms (Prof. Bernstein) | |||
| 3/27 | Spring break, no class. | ||
| 10. 4/3 | Graph Decompositions and Shortest Paths, I | ||
| 11. 4/10 | Graph Decompositions and Shortest Paths, II | ||
| Algorithms for Modern Machine Learning (Prof. Musco) | |||
| 12. 4/17 | Fast Generative AI I: Diffusion Models + Sampling | ||
| 13. 4/24 | Fast Generative AI II: Autoregressive Language Models | ||
| 14. 5/1 | High-dimensional Vector Search | ||