This course provides an introduction to the design and analysis of algorithms. It covers a variety of classical algorithms and data structures and their complexity and will equip students with the intellectual tools to design, analyze, implement, and evaluate their own algorithms.

This course studies randomized algorithms: algorithms where randomness plays an essential role in constructing efficient solutions to computational problems. We will cover a variety of algorithms where randomness is obvious, such as hash functions and sampling, and others where randomness is helpful despite not being inherent, such as sorting, routing, and satisfying Boolean formulas. Topics covered include probability theory fundamentals, core principles of randomized algorithm design and analysis, noteworthy examples of randomized algorithms, tools for analyzing running times, random walk-based algorithms, Las Vegas methods, the Monte Carlo method, large deviation inequalities such as Chernoff’s bound, martingales, Multi-Armed Bandit problems, the exploration-exploitation tradeoff, and applications to reinforcement learning. The emphasis is on applications of these techniques to solve new problems.

Computational Geometry is a subfield of algorithm theory that involves the design and analysis of efficient algorithms for problems involving geometric input and output. In this course the focus will be largely on problems in 2-dimensional space (lines, line segments, polygons, planes, polyhedral, curved objects, etc.) with occasional inclusion of higher dimensional problems. There are many fields of computer science that deal with solving problems of a geometric nature. These include computer graphics, computer vision and image processing, robotics, computer-aided design and manufacturing, computational fluid-dynamics, and geographic information systems, to name a few. One of the goals of this computational geometry course is to provide the basic geometric tools necessary to solve problems in these fields. Note: Programming projects are required.