Advanced Algorithms

Welcome to Advanced Algorithms, the most exciting class in CS! This class covers fundamental algorithmic ideas that have had (and continue to have) a major influence on the evolution of computer science and several other disciplines, ranging from mathematics to biology to the social sciences.

We will be covering a vast array of techniques, starting from rudimentary divide and conquer and greedy algorithms to advanced dynamic programming. We shall also cover randomized algorithms of various types, streaming, continuous optimization, intractability, approximation, distributed algorithms, and many more. Throughout this process, we will be analyzing everything we do. This will (eventually) involve some usage of the central limit theorem (we'll be using the Markov and Chebyshev inequalities, which we will briefly cover in class), amortized analysis (which we will cover in detail), and some more probability theory (which will be covered as and when necessary).

Because of the conceptual nature of the material, just attending lectures and recitations and doing the homework are unlikely to be sufficient for learning all the concepts.  Setting aside time to do the reading and to study your notes from lecture and recitation is generally necessary to truly learn and internalize the material, and to be able to apply it in new ways later in the course as well as for the rest of your life.

Homework is essential for learning the material.  Rather than thinking of problem sets as just a requirement, recognize them as an excellent means for learning the material, and for building upon it.  Spread out the time you have to work the problems. Many people learn best by reading the problems long before they are due, and working on them over the course of a whole week; they find that their minds make progress working the problems in the background or during downtime throughout the day.  Few people do their best learning the night before an assignment is due.  Work with others if that is helpful, but with the goal of learning first and solving the problems second. It is worth reading the posted homework solutions, even if you received full credit.  Often the clarity of explanation or details of implementation are different from the way you were thinking about things in ways that can improve your learning.