A first-year graduate course in algorithms. Emphasizes fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Data structures. Network flows. Linear programming. Computational geometry. Approximation algorithms.

A first-year graduate course in algorithms. Emphasizes fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Data structures. Network flows. Linear programming. Computational geometry. Approximation algorithms. Alternate years.

This course is a first-year graduate course in algorithms. Emphasis is placed on fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. 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.

Study of an area of current interest in theoretical computer science. Topic varies from term to term. This course is a study of Behavior of Algorithms and covers an area of current interest in theoretical computer science. The topics vary from term to term. During this term, we discuss rigorous approaches to explaining the typical performance of algorithms with a focus on the following approaches: smoothed analysis, condition numbers/parametric analysis, and subclassing inputs.

Carrier systems involve the design, operation, and management of transportation networks, assets, personnel, freight, and passengers. A number of different carrier systems are contrasted while models and tools for analyzing, optimizing, planning, managing, and controlling these systems are presented.

Thorough treatment of linear programming and combinatorial optimization. Topics include network flow, matching theory, matroid optimization, and approximation algorithms for NP-hard problems. 18.310 helpful but not required.

Introduction to the theory and application of large-scale dynamic programming. Markov decision processes. Dynamic programming algorithms. Simulation-based algorithms. Theory and algorithms for value function approximation. Policy search methods. Games. Applications in areas such as dynamic resource allocation, finance and queueing networks, among others.

Linear Algebra is both rich in theory and full of interesting applications; in this course the student will try to balance both. This course includes a review of topics learned in Linear Algebra I. Upon successful completion of this course, the student will be able to: Solve systems of linear equations; Define the abstract notions of vector space and inner product space; State examples of vector spaces; Diagonalize a matrix; Formulate what a system of linear equations is in terms of matrices; Give an example of a space that has the Archimedian property; Use the Euclidean algorithm to find the greatest common divisor; Understand polar form and geometric interpretation of the complex numbers; Explain what the fundamental theorem of algebra states; Determine when two matrices are row equivalent; State the Fredholm alternative; Identify matrices that are in row reduced echelon form; Find a LU factorization for a given matrix; Find a PLU factorization for a given matrix; Find a QR factorization for a given matrix; Use the simplex algorithm; Compute eigenvalues and eigenvectors; State Shur's Theorem; Define normal matrices; Explain the composition and the inversion of permutations; Define and compute the determinant; Explain when eigenvalues exist for a given operator; Normal form of a nilpotent operator; Understand the idea of Jordan blocks, Jordan matrices, and the Jordan form of a matrix; Define quadratic forms; State the second derivative test; Define eigenvectors and eigenvalues; Define a vector space and state its properties; State the notions of linear span, linear independence, and the basis of a vector space; Understand the ideas of linear independence, spanning set, basis, and dimension; Define a linear transformation; State the properties of linear transformations; Define the characteristic polynomial of a matrix; Define a Markov matrix; State what it means to have the property of being a stochastic matrix; Define a normed vector space; Apply the Cauchy Schwarz inequality; State the Riesz representation theorem; State what it means for a nxn matrix to be diagonalizable; Define Hermitian operators; Define a Hilbert space; Prove the Cayley Hamilton theorem; Define the adjoint of an operator; Define normal operators; State the spectral theorem; Understand how to find the singular-value decomposition of an operator; Define the notion of length for abstract vectors in abstract vector spaces; Define orthogonal vectors; Define orthogonal and orthonormal subsets of R^n; Use the Gram-Schmidt process; Find the eigenvalues and the eigenvectors of a given matrix numerically; Provide an explicit description of the Power Method. (Mathematics 212)

Scientific computing: Fast Fourier Transform, finite differences, finite elements, spectral method, numerical linear algebra. Complex variables and applications. Initial-value problems: stability or chaos in ordinary differential equations, wave equation versus heat equation, conservation laws and shocks, dissipation and dispersion. Optimization: network flows, linear programming. Includes one computational project.

Scientific computing: Fast Fourier Transform, finite differences, finite elements, spectral method, numerical linear algebra. Complex variables and applications. Initial-value problems: stability or chaos in ordinary differential equations, wave equation versus heat equation, conservation laws and shocks, dissipation and dispersion. Optimization: network flows, linear programming. Includes one computational project.

Introduces students to the theory, algorithms, and applications of optimization. The optimization methodologies include linear programming, network optimization, dynamic programming, integer programming, non-linear programming, and heuristics. Applications to logistics, manufacturing, transportation, E-commerce, project management, and finance.

Principles of Applied Mathematics is a study of illustrative topics in discrete applied mathematics including sorting algorithms, information theory, coding theory, secret codes, generating functions, linear programming, game theory. There is an emphasis on topics that have direct application in the real world.

Principles of Applied Mathematics is a study of illustrative topics in discrete applied mathematics including sorting algorithms, information theory, coding theory, secret codes, generating functions, linear programming, game theory. There is an emphasis on topics that have direct application in the real world. This course was recently revised to meet the MIT Undergraduate Communication Requirement (CR). It covers the same content as 18.310, but assignments are structured with an additional focus on writing.

This course surveys a variety of reasoning, optimization, and decision-making methodologies for creating highly autonomous systems and decision support aids. The focus is on principles, algorithms, and their applications, taken from the disciplines of artificial intelligence and operations research. Reasoning paradigms include logic and deduction, heuristic and constraint-based search, model-based reasoning, planning and execution, reasoning under uncertainty, and machine learning. Optimization paradigms include linear, integer and dynamic programming. Decision-making paradigms include decision theoretic planning, and Markov decision processes. This course is offered both to undergraduate (16.410) students as a professional area undergraduate subject, in the field of aerospace information technology, and graduate (16.413) students.

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.

This subject is on regional energy-environmental modeling rather than on general energy-environmental policies, but the models should have some policy relevance. We will start with some discussion of green accounting issues; then, we will cover a variety of theoretical and empirical topics related to spatial energy demand and supply, energy forecasts, national and regional energy prices, and environmental implications of regional energy consumption and production. Where feasible, the topics will have a spatial dimension. This is a new seminar, so we expect students to contribute material to the set of readings and topics covered during the semester.