## Advanced Algorithms (COMS 4995-8, Spring'21)

- Instructor: Alexandr Andoni
- TAs: Akshat Agarwal, Eli Goldin.
- Lectures: TR 4:10-5:25pm (zoom link available through CourseWorks)
- Office hours: see calendar in CourseWorks/Course Info.

#### 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, and
is thus an advanced version of “Analysis of Algorithms” (COMS 4231),
both in terms of content as well as pace. You need not have taken
4231, but some algorithmic exposure is expected (see prerequisites
below). Hence it is suitable for those of you who have seen some
algorithms class (like 4231 or easier), and/or want to take an
in-depth algorithms class. The evaluation is based on homeworks and
a final project.

#### 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.

Undergradute students and students from other departments are welcome.

#### (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

#### Grading

Grading will be based on 5 problem sets (55%), scribing one
lecture (10%), and a final project (35%).
Homeworks: 5 in total (roughly once in 2 weeks). You can
collaborate on homeworks. In this case, you have to: 1) write
your own solutions, independently, 2) write clearly all the
persons you have collaborated with. There will also be an
automatic extension policy.
The final projects can be of three types: Reading-based: read
research papers on a topic and summarize them;
Implementation-based: implement some of the algorithms from the
class (or from other theoretical literature), and perhaps apply
if your area of interest/expertise; apply on real-world
datasets; Research-based: investigate a research topic on your
own (eg, develop an algorithm, and prove its properties).