6.046J/ 18.410J Introduction to Algorithms

6.895 Randomness and Computation

The power and sources of randomness in computation. Topics include:
(1) Basic tools: polynomial zero testing, linearity testing, uniform generation and approximate counting, the influence of variables.
(2) Randomness in various computational settings: computational learning theory, communication complexity, probabilistic proofs.
(3) Generating randomness: pseudorandom generators, derandomization, expanders, extractors.

prerequisites: 6.046, 6.840 3-0-9 H Level Credit

18.409/ 6.443J Topics in Theoretical Computer Science

6.885 Distributed Algorithms for Mobile Wireless Ad Hoc Networks (H)

This subject qualifies as a Theoretical Computer Science Engineering Concentration subject. This course will cover distributed algorithms for mobile (and some non-mobile) wireless ad hoc networks, including those with interesting interactions with the real world. Focusing on algorithms that can be described precisely, and that have relatively well-defined correctness, fault-tolerance, and performance requirements. Aiming to understand the existing theory of wireless network algorithms and contribute to its further development. Thus, we would like to:
1. Understand the nature of wireless ad hoc network settings. What are typical correctness, reliability, and performance properties that can be assumed? What are the ``right'' complexity measures to use for evaluating algorithms?
2. Identify important, well-defined problems and subproblems that must be solved by distributed algorithms in wireless ad hoc networks. These will include problems of low-level and higher-level communication, time synchronization, localization, network configuration, resource allocation, tracking, and data management.
3. Learn about the most important existing algorithms for many of these problems, and identify places where additional algorithmic work is needed.
4. Identify some inherent limitations (lower bound and other impossibility results) on the solvability of problems in wireless networks.
5. Identify useful abstraction layers for programming wireless networks.
The course will involve reading a series of recent research papers, proceeding roughly from lower to higher layers in the ``protocol stack'': MAC layer: Collision avoidance, backoff strategies; Collision detection. Local infrastructure: Local consensus, leader election; Local reliable broadcast, replicated state machines; Localization; Time synchronization. Broadcast Point-to-point routing Location-based communication services: Location services; Geographical routing. Global infrastructure: Power-aware topology control; Clustering; Maximal independent set, spanning trees. Middleware services: Mutual exclusion, resource allocation; Token circulation; Group membership, group communication; Synchronization, consensus. Virtual node layers. Applications: Data aggregation; Implementing shared memory; Tracking; Robot motion coordination.

Prereq.: 6.046, 6.033, 6.852 or equivalent of each
3-0-9

6.338J/18.337J Applied Parallel Computing

 TBA

NOTE: The class this year will be involved in a supercomputing productivity study.

Advanced interdisciplinary introduction to applied parallel computing on modern supercomputers. Numerical topics include dense and sparse linear algebra, N-body problems, multigrid, fast-multipole, wavelets and Fourier transforms. Geometrical topics include partitioning and mesh generation. Other topics include applications oriented architecture, software systems, MPI, Cilk, data parallel systems, Parallel MATLAB, caches and vector processors with hands-on emphasis on understanding the realities and myths of what is possible on the world's fastest machines.

6.857 Computer and Network Security

18.338J/ 16.394J The Mathematics and Applications of Infinite Random Matrices

6.876/18.426 Cryptographic Game Theory

6.885 Algebra and Computation

This course studies the interplay between algebra and computation. The course will be divided in two parts.

* The first part will cover algorithms in Algebra, Number Theory, and Group Theory. Some topics include algorithms for factoring polynomials (Berlekamp, Lenstra-Lenstra-Lovasz etc.) and algorithms for testing primes (Agarwal-Kayal-Saxena), multiplying matrices (Cohn-Umans), Solving systems of polynomial equations etc.

* The second part of the course will focus on the interplay between complexity theory and algebra as highlighted by algebraic versions of the P vs. NP question.

See http://theory.csail.mit.edu/~madhu/FT98 for notes from an earlier version of this course. Prereq: 6.840 + 6.046 + 18.703

6.896 Sublinear time Algorithms

6.895 Essential Coding Theory

6.885: Folding and Unfolding in Computational Geometry

I will also organize an optional problem-solving session, during which we can jointly try to solve open problems in folding. Results from this session would likely lead to class projects, and hopefully also paper submissions, but this is not the only way to do a class project. Class projects can also take the form of well-written descriptions of one or more papers in the area; formulations of clean, new open problems; or implementations of existing algorithms. Projects can be purely mathematical (geometric) and/or theoretical computer science (algorithmic/complexity theoretic). There may also be a project presentation and/or a small number of problem sets.

This is a graduate class but both undergraduate and graduate students are welcome. A background in discrete mathematics and algorithms (e.g., 6.046) is required. Refer to the class webpage for more details and updates.

6.852J/18.437J Distributed Algorithms

Design and analysis of concurrent algorithms,
emphasizing those suitable for use in distributed networks. Process synchronization, allocation of computational resources, distributed consensus, distributed graph algorithms, election of a leader in a network, distributed termination, deadlock detection, concurrency control, communication, and clock synchronization. Special consideration given to issues of efficiency and fault tolerance. Formal models and proof methods for distributed
computation.

6.854/18.415J: Advanced Algorithms

The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are "efficient," and even the model of computation can vary widely from area to area. In this second course in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to mathematical maturity.

The coursework will involve problem sets and a final project that is research-oriented.

Thorough treatment of linear programming and combinatorial optimization. Topics include matching theory, network flow, matroid optimization, and how to deal with NP-hard optimization problems. Prior exposure to discrete mathematics (such as 18.310) helpful.

18.409 Convex Geometry and Random Walks