The Algorithms Group

Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine Images from 6.046 class notes, E. Demaine
6.046J Introduction to Algorithms
Teacher:    Erik Demaine, Shafi Goldwasser
Meeting Time:    TBA
Brief Description:  Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing. Enrollment may be limited.

18.996 Random Matrix Theory and Its Applications
Teacher:    Prof. Alan Edelman
Meeting Time:    M W 9.30 - 11.00 Room 2-338
Brief Description:  This course provides a rigorous introduction to fundamentals of random matrix theory motivated by engineering and scientific applications while emphasizing the informed use of modern numerical analysis software. Topics include Matrix Jacobians, Wishart Matrices, Wigner's Semi-Circular laws, Matrix beta ensembles, free probability and applications to engineering, science, and numerical computing. Lectures will be supplemented by reading materials and expert guest speakers, emphasizing the breadth of applications that rely on random matrix theory and the current state of the art

Additional topics will be decided based on the interests of the students. No particular prerequisites are needed though a proficiency in linear algebra and basic probability will be assumed. A familiarity with MATLAB will also be useful.



6.896 Theory of Parallel Hardware

Teacher:   Prof. Charles E. Leiserson, Dr. Bradley C. Kuszmaul, Prof. Michael A. Bender
Meeting Time:    MW 10-11:30
Brief Description:  This class covers mathematical foundations of parallel hardware, from computer arithmetic to interconnection networks. We will focus on the algorithmic underpinnings of parallel hardware. The topics for the class will vary depending on student interest, but will likely include arithmetic circuits, parallel prefix, systolic arrays, retiming, clocking methodologies, sorting networks, interconnection networks, hypercubic networks, P-completeness, VLSI layout theory, reconfigurable wiring, fat-trees, area-time complexity, and advanced topics.

The class is suitable for both theory and systems students. Although it will focus on problem solving, students will also be exposed to VLSI-layout tools, such as Magic. M.Eng. students can use the class to satisfy their Engineering Concentration in either Theoretical Computer Science or Computer Systems and Architecture Engineering.



18.409 Convex Geometry and Random Walks

Teacher:    Santosh Vempala
Meeting Time:    TR 11-12:30, room 2-338
Brief Description:  Algorithmic problems in geometry often become tractable with the assumption of convexity (e.g. optimization, volume computation, learning, finding the average etc.). We will study this phenomenon in depth, beginning with classical topics such as the Brunn-Minkowski inequality and Gaussian isoperimetry, and then proceed to more recent developments in the field of geometric isoperimetric inequalities (e.g., if you cut a cylinder into two equal volume parts with a hyperplane, what is the minimum area of the separation? what is the maximum?), and their extensions to logconcave functions. One motivating problem will be that of efficiently sampling a geometric distribution by a random walk. Somewhat surprisingly, this problem plays a central role in the solution of all the algorithmic problems mentioned above.



* Please be advised that this is a partial list. Please refer to Course 6: Electrical Engineering and Computer Science, Course 18: Mathematics or the individual Faculty homepages for further details.


Massachusetts Institute
of Technology
77 Massachusetts Avenue
Cambridge, MA 02139