MIT / Engineering / Electrical
Lecture : Competitive Analysis Self organizing Lists
By Erik Demaine | Introduction to Algorithms
Lecture 14 of 23
Rate this lecture -
 More Lectures - Select Lecture...1 : Administrivia Introduction Analysis of Algorithms Insertion Sort Mergesort2 : Asymptotic Notation Recurrences Substitution Master Method3 : Divide and Conquer Strassen Fibonacci Polynomial Multiplication4 : Quicksort Randomized Algorithms5 : Linear time Sorting Lower Bounds Counting Sort Radix Sort6 : Order Statistics Median7 : Hashing Hash Functions8 : Universal Hashing Perfect Hashing9 : Relation of BSTs to Quicksort Analysis of Random BST10 : Red black Trees Rotations Insertions Deletions11 : Augmenting Data Structures Dynamic Order Statistics Interval Trees12 : Skip Lists13 : Amortized Algorithms Table Doubling Potential Method14 : Competitive Analysis Self organizing Lists15 : Dynamic Programming Longest Common Subsequence16 : Greedy Algorithms Minimum Spanning Trees17 : Shortest Paths I Properties Dijkstras Algorithm Breadth first Search18 : Shortest Paths II Bellman Ford Linear Programming Difference Constraints19 : Shortest Paths III All pairs Shortest Paths Matrix Multiplication Floyd Warshall Johnson20 : Advanced Topics21 : Advanced Topics cont22 : Advanced Topics cont 123 : Advanced Topics cont Discussion of Follow on Classes

Course Description
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.
Courses Index
2 : Introduction to Digital Integrated Circuits   (Jan RABAEY / Berkeley)
4 : Introduction to Microelectronic Circuits   (Bernhard BOSER / Berkeley)
5 : The Fourier Transform and its Applications   (Brad Osgood / Stanford)
6 : Introduction to Linear Dynamical Systems   (Stephen Boyd / Stanford)
7 : Convex Optimization I   (Stephen Boyd / Stanford)
8 : Convex Optimization II   (Stephen Boyd / Stanford)
9 : Circuits and Electronics   (Anant Agarwal / MIT)
10 : Computer System Engineering   (Samuel Madden / MIT)
11 : Principles of Digital Communications I   (Lizhong Zheng / MIT)
12 : Principles of Digital Communication II   (David Forney / MIT)
13 : Understanding Lasers and Fiberoptics   (Shaoul Ezekiel / MIT)
14 : Electromagnetics and Applications   (Multiple Instructors / MIT)
15 : Information and Entropy   (Paul Penfield / MIT)
16 : Fundamentals of Laser   (Sabieh Anwar / LUMS)
17 : Synchrotron Radiation for Materials Science   (David Attwood / Berkeley)
18 : Linear Integrated Circuits   (Clark Nguyen / Berkeley)
19 : Digital Circuit Design   (Ken Boyd / University of New South Wales)
20 : Speech and Audio Processing   (Multiple Multiple / University of New South Wales)