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: By appointment.
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.
Homeworks::
Homework 1 (due Thurs. Feb. 13, 11:59 PM.).
Problem Set 2 (due Thurs. Feb. 27, 11:59 PM.).
| Lecture # | Topic | Reading | Homework |
|---|---|---|---|
| Approximation and Online Algorithms Part I (Prof. Gupta) | |||
| 1. 1/23 | Approximation
Algorithms I:
Set Cover Solved in Several Styles |
Williamson-Shmoys Chap.1 Anupam's handwritten notes |
|
| Stochastic Probing and Sequencing Problems (Prof. Hellerstein) | |||
| 2. 1/30 | Approximation algorithms for generalizations and variants of set cover | Lecture notes. | Homework 1 released. Due Thurs. Feb. 13, 11:59 PM. Must work with a partner and submit one copy! |
| 3. 2/6 | Stochastic Function Evaluation I: Exact algorithms and major open questions in Stochastic Boolean Function Evaluation |
Lecture notes. | |
| 4. 2/13 | Stochastic Function Evaluation II:
Approximation algorithms, examples and techniques |
Lecture notes. | |
| Approximation and Online Algorithms Part II (Prof. Gupta) | |||
| 5. 2/20 | Online I: Online Set Cover and Competitive Analysis | Notes on MTF, potential functions, slides on online set cover. |
|
| 6. 2/27 | Approx and Online: Beyond Worst-Case Analysis for Set Cover |
Slides. | |
| Randomized Data Structures (Prof. Farach-Colton) | |||
| 7. 3/6 | Background: Concentration Bounds and Explicit Construction of Hash Functions | ||
| 8. 3/13 | Hash Tables (Prof. Farach-Colton) | ||
| Graph Algorithms (Prof. Bernstein) | |||
| 9. 3/20 | TBD | ||
| 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 | ||