NYU Advanced Algorithms

Lecture: Wednesdays at 2:45-5:15pm ET, 202 Warren Weaver
Course Numbers: CSCI-GA.3033-147

Professors office hours: TBA.

Overview: This is an intensive graduate course on the design and analysis of algorithms. This course is primarily aimed at graduate and advanced undergraduate students interested in doing research in theoretical computer science, and the goal is to expose these students to many of the ideas being used in algorithms research today. It is more specialized and in-depth than the graduate and undergraduate level Algorithms courses being offered: we will cover a broad set of advanced algorithmic ideas (some classical, some very recent), and the theory behind it (theorems, proofs). The goal is to cover advanced content, proofs, and new techniques --- topics include (near)-linear time algorithms for spanning trees, shortest paths, and matchings, linear and convex optimization, continuous methods for discrete optimization, online learning and the connection to measure concentration. A major focus will be on the use of linear/convex programming duality, and how it arises in many contexts in algorithm design.

The focus of this course is to present both the algorithmic ideas, and the ideas behind their analysis, so we expect the students to have mathematical maturity and strong problem-solving abilities. A detailed syllabus will be posted as the course progresses.

Previous versions of the course: 2023, 2020, 2018. These were all offered at CMU. Here are the lecture notes and videos from 2023.

Prerequisites: We expect students to have a good background in algorithm design. 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. Solid understanding of probability, linear algebra, and calculus, and mathematical maturity is a must.

Enrollment: If you are an NYU student wishing to enroll for the course and need permission, please remember to send me a CV and a current transcript, and give some background on your preparation for the course.

Grading breakdown: The course evaluation will be based on 3-4 homework sets, and some in-class exams TBD. Depending on the class size, some of the homeworks may be oral homeworks. Most of the weight will be on the in-person components.

GenAI Policy: You are allowed (and encouraged) to use Generative AI to learn the materials. However, their use is at your own risk: indiscriminate use will mean that you don't learn how to solve problems, which may adversarially affect your performance in the in-person evaluations.

We may also use GenAI in the evaluation process, e.g., to administer HWs/exams, to give you feedback on your homework submissions, etc. This is a rapidly evolving area, and we will update you with the latest details.

Course Infrastructure: We will use Ed for course discussions, Gradescope for homework submissions, and Brightspace for all course material. In addition, we will post as much material here as possible.

Collaboration: For some of the problems, we will ask you to work solo, whereas for others we will allow collaboration in small groups. Each person must write their own solutions to submit.

Resources: There is no textbook for the course. Most of our material is not in textbooks (yet) and some of it is evolving even as we speak. We will rely on lecture notes, readings from monographs and research papers, which will be available free online or via the NYU library.

Homeworks: