Related Courses
| Intro to Algorithms: Examines the basic principles of algorithm analysis; techniques of efficient programming; analysis of sorting and searching; graph algorithms; string-matching algorithms; matrix algorithms; integer and polynomial arithmetic; the fast Fourier transform; and NP-hard and NP-complete problems. |
| Elements of the Theory of Computation: The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church’s thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems. |
| Advanced Algorithms: Studies the design and efficiency of algorithms in several areas of computer science. Topics are chosen from graph algorithms, sorting and searching, NP-complete problems, pattern matching, parallel algorithms, and dynamic programming. |
| Complexity Theory: Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems. |
| Randomness in Computing: Survey of probabilistic ideas of the theory of computation. Topics may include Monte Carlo and Las Vegas probabilistic computations; average case complexity and analysis; random and pseudorandom strings; games and cryptographic protocol; information; inductive inference; reliability;others. (Offered alternate years.) |
| Iterative Methods in Graph Algorithms and Network Analysis: Iterative methods allow us to trade-off precision and running time to produce theoretically sound, fast algorithms for many problems in Convex Optimization. These methods rely on a very “continuous” interpretation of the problem, incorporating techniques such as steepest-descent and coordinate descent that strongly rely on geometric intuition. In this class, we will turn this perspective on his head and show that iterative methods can be extremely useful in understanding and solving fundamental combinatorial problems on discrete structures such as graphs and networks (i.e. directed graphs). |
| Optimization Methods & their Applications: At their core, many real-world problems involve optimization problems that are complex and challenging, and they require principled mathematical and algorithmic solutions. Companies such as Google and Facebook use powerful algorithmic primitives such as gradient descent to solve a host of challenging problems. These primitives in turn are based on a beautiful mathematical theory developed in the context of convex and discrete optimization. In this class, we will explore several of these optimization primitives that have found significant applications and we will develop a mathematical toolkit that can be used to tackle real-world problems. . |