Behavior of algorithms

Lectures: 2 sessions / week, 1.5 hours / session

In this course, we will discuss rigorous approaches to explaining the typical performance of algorithms. In particular, we examine alternatives to the traditional worst-case and average-case analyses. Such analyses must necessarily make assumptions about the inputs to algorithms.

We will develop this theory together, and I expect we will debate the merits of various approaches, as well as the names I have tentatively assigned to them.

My lectures will center around the following three approaches.

Analyzing algorithms assuming their inputs are subject to noise. That is, we measure the maximum over inputs of the expected performance of an algorithm under slight random perturbations of those inputs. This is the intersection of Shannon Theory (PDF) with Analysis of Algorithms by assuming inputs come through a noisy channel.

In this approach, we find a simple parameter of the input that is predictive of the running time of the algorithm. This parameter should be significantly simpler than "the running time of the algorithm".

Examples could include

In many practical problem domains, the inputs to algorithms have special structure, and may form a proper subclass of the possible inputs. If it is known an algorithm in a particular application only sees inputs from this subclass, then it is natural to analyze the performance of this algorithm on the subclass.

Students will perform class projects examining the applicability of these analyses to some problem area, and will present their findings to the class as well as writing up their findings. Some students may wish to choose their project from a list of tractable open problems that will be circulated within the class.

Students will also be responsible for scribing lectures.

At least one graduate course in algorithms or numerical analysis.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare