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