The design of algorithms is studied, according to methodology and application. Methodologies include: divide and conquer, dynamic programming, and greedy strategies. Applications involve: sorting, ordering and searching, graph algorithms, geometric algorithms, mathematical (number theory, algebra and linear algebra) algorithms, and string matching algorithms. Analysis of algorithms is studied - worst case, average case, and amortized - with an emphasis on the close connection between the time complexity of an algorithm and the underlying data structures. NP-Completeness theory is examined along with methods of coping with intractability, such as approximation and probabilistic algorithms.

This module introduces approximation and projections in Hilbert space.

This course teaches simple reasoning techniques for complex phenomena: divide and conquer, dimensional analysis, extreme cases, continuity, scaling, successive approximation, balancing, cheap calculus, and symmetry. Applications are drawn from the physical and biological sciences, mathematics, and engineering. Examples include bird and machine flight, neuron biophysics, weather, prime numbers, and animal locomotion. Emphasis is on low-cost experiments to test ideas and on fostering curiosity about phenomena in the world.

Accuracy of measurement in navigation depends very much on the situation. If a sailor's target is an island 200 km wide, sailing off center by 10 or 20 km is not a major problem. But, if the island were only 1 km wide, it would be missed if off just the smallest bit. Many of the measurements made while navigating involve angles, and a small error in the angle can translate to a much larger error in position when traveling long distances.

Accuracy of measurement in navigation depends very much on the situation. If a sailor's target is an island 200 km wide, sailing off center by 10 or 20 km is not a major problem. But, if the island were only 1 km wide, it would be missed if off just the smallest bit. Many of the measurements made while navigating involve angles, and a small error in the angle can translate to a much larger error in position when traveling long distances.

In this lesson, students will investigate error. As shown in earlier activities from navigation lessons 1 through 3, without an understanding of how errors can affect your position, you cannot navigate well. Introducing accuracy and precision will develop these concepts further. Also, students will learn how computers can help in navigation. Often, the calculations needed to navigate accurately are time consuming and complex. By using the power of computers to do calculations and repetitive tasks, one can quickly see how changing parameters likes angles and distances and introducing errors will affect their overall result.

In this lesson, students will learn that math is important in navigation and engineering. Ancient land and sea navigators started with the most basic of navigation equations (Speed x Time = Distance). Today, navigational satellites use equations that take into account the relative effects of space and time. However, even these high-tech wonders cannot be built without pure and simple math concepts basic geometry and trigonometry that have been used for thousands of years. In this lesson, these basic concepts are discussed and illustrated in the associated activities.

The course focuses on the problem of supervised learning within the framework of Statistical Learning Theory. It starts with a review of classical statistical techniques, including Regularization Theory in RKHS for multivariate function approximation from sparse data. Next, VC theory is discussed in detail and used to justify classification and regression techniques such as Regularization Networks and Support Vector Machines. Selected topics such as boosting, feature selection and multiclass classification will complete the theory part of the course. During the course we will examine applications of several learning techniques in areas such as computer vision, computer graphics, database search and time-series analysis and prediction. We will briefly discuss implications of learning theories for how the brain may learn from experience, focusing on the neurobiology of object recognition. We plan to emphasize hands-on applications and exercises, paralleling the rapidly increasing practical uses of the techniques described in the subject.

Studies how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Models of randomized computation. Data structures: hash tables, and skip lists. Graph algorithms: minimum spanning trees, shortest paths, and minimum cuts. Geometric algorithms: convex hulls, linear programming in fixed or arbitrary dimension. Approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.

Doctoral student seminar covering current topics related to operations research not otherwise included in the curriculum. In keeping with the tradition of the last twenty-some years, the Readings in Optimization seminar will focus on an advanced topic of interest to a portion of the MIT optimization community: randomized methods for deterministic optimization. In contrast to conventional optimization algorithms whose iterates are computed and analyzed deterministically, randomized methods rely on stochastic processes and random number/vector generation as part of the algorithm and/or its analysis. In the seminar, we will study some very recent papers on this topic, many by MIT faculty, as well as some older papers from the existing literature that are only now receiving attention.

The earliest explorers did not have computers or satellites to help them know their exact location. The most accurate tool developed was the sextant to determine latitude and longitude. In this activity, the sextant is introduced and discussed with the class. Students will learn how a sextant can be a reliable tool that is still being used by today's navigators and how computers can help assure accuracy when measuring angles. Also, this activity will show how computers can be used to understand equations even when knowing how to do the math is unknown.