Loading…

MIT OpenCourseWare

Introduction to Algorithms

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: 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. (from ocw.mit.edu )

Instructor

Professor Charles Leiserson and Professor Erik Demaine,

Computer science

2009

Lecture 01 - Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort

Lecture 03 - Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication

Lecture 05 - Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort

Lecture 06 - Order Statistics, Median

Lecture 07 - Hashing, Hash Functions

Lecture 08 - Universal Hashing, Perfect Hashing

Lecture 09 - Relation of BSTs to Quicksort - Analysis of Random BST

Lecture 12 - Skip Lists

Lecture 14 - Competitive Analysis: Self-organizing Lists

Lecture 16 - Greedy Algorithms, Minimum Spanning Trees

Lecture 17 - Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search

Lecture 18 - Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints

Lecture 23 - Advanced Topics (cont.)

Lecture 24 - Advanced Topics (cont.)

Lecture 25 - Advanced Topics (cont.) - Discussion of Follow-on Classes

Lecture 02 - Asymptotic Notation; Recurrences; Substitution, Master Method

Lecture 04 - Quicksort, Randomized Algorithms

Lecture 10 - Red-black Trees, Rotations, Insertions, Deletions

Lecture 11 - Augmenting Data Structures, Dynamic Order Statistics, Interval Trees

Lecture 13 - Amortized Algorithms, Table Doubling, Potential Method

Lecture 15 - Dynamic Programming, Longest Common Subsequence

Lecture 19 - Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

Lecture 22 - Advanced Topics