## Advanced Algorithms (COMS 4232, Spring'23)

- Instructor: Alexandr Andoni
- TAs: Imanol Uribe Echevarria, Yiming Fang, Hantao Yu.
- Lectures: MW 2:40-3:55pm
- Office hours: see LionMail calendar in CourseWorks.

#### Class Description

**Official course
information.**

The class covers classic and modern algorithmic ideas that are central
to many areas of Computer Science. The focus is on most powerful
paradigms and techniques of how to design algorithms, and measure
their efficiency. The topics will include hashing, sketching,
dimension reduction, spectral graph theory, optimization (linear
programming, gradient descent, IPM), multiplicative weights, compressed sensing, and others.

The class is designed as a “grad intro to algorithms” class, with
focus on algorithmic ideas that had impact both in theory and in
practice. Compared to “Analysis of Algorithms” (COMS 4231), this
class is faster paced and requires more mathematical mastery, but
otherwise is not intersecting with 4231 topic-wise (almost at
all). You can take this class without having taken 4231, but some
algorithmic exposure is expected (see prerequisites below).

#### Prerequisites

Mathematical maturity is a must: the class is based on
theoretical ideas and is proof-heavy. You are expected to be able
to read and write formal mathematical proofs. Some familiarity
with algorithms and randomness will be assumed as well. COMS 4231
(Analysis of Algorithms) or equivalent is recommended, but
not required if you have solid math background.

Self-Evaluation test:
to check for yourself if you have the right background, you should complete the self-evaluation test asap (ideally before
the class starts). It will help you identify potential parts to brush
up before the class starts. Once completed, take a look at
the solutions key.

#### (Tentative) List of Topics

- Hashing
- Sketching/Streaming
- Nearest Neighbor Search
- Graph Algorithms
- Spectral Graph Algorithms
- Optimization: linear programming, gradient descent, IPM
- Multiplicative Weights Update, online algorithms
- Large-scale computation models