Introduction to Algorithms

MIT Open Courseware
|
23 Lectures
|
0 reviews

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.

This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).

Related Courses

Lectures:

Lecture 1

Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort

Lecture 2

Asymptotic Notation; Recurrences; Substitution, Master Method

Lecture 3

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

Lecture 4

Quicksort, Randomized Algorithms

Lecture 5

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

Lecture 6

Order Statistics, Median

Lecture 7

Hashing, Hash Functions

Lecture 8

Universal Hashing, Perfect Hashing

Lecture 9

Relation of BSTs to Quicksort - Analysis of Random BST

Lecture 10

Red-black Trees, Rotations, Insertions, Deletions

Lecture 11

Augmenting Data Structures, Dynamic Order Statistics, Interval Trees

Lecture 12

Skip Lists

Lecture 13

Amortized Algorithms, Table Doubling, Potential Method

Lecture 14

Competitive Analysis: Self-organizing Lists

Lecture 15

Dynamic Programming, Longest Common Subsequence

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 19

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

Lecture 20

Advanced Topics

Lecture 21

Advanced Topics (cont.)

Lecture 22

Advanced Topics (cont.)

Lecture 23

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

Citation

Leiserson, Charles, and Erik Demaine. 6.046J Introduction to Algorithms (SMA 5503), Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu

Instructors

Prof. Charles Leiserson
Prof. Erik Demaine

Additional Notes

schooX is not affiliated or endorsed by Massachusetts Institute of Technology. Please consider donating to MIT by clicking on the donation button below.

License

Donate