Introduction to Algorithms

MIT Course , Fall 2005 , Prof. Erik Demaine

453 students enrolled

Overview

Introduction - Analysis of Algorithms, Insertion Sort, Merge sort - Asymptotic Notation | Recurrences | Substitution, Master Method - Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication- Quick sort, Randomized Algorithms- Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort - Order Statistics, Median-Hashing, Hash Functions-Universal Hashing, Perfect Hashing-Relation of BSTs to Quick sort | Analysis of Random BST - Red-black Trees, Rotations, Insertions, Deletions - Augmenting Data Structures, Dynamic Order Statistics, Interval Trees-Skip Lists - Amortized Algorithms, Table Doubling, Potential Method - Competitive Analysis: Self-organizing Lists-Dynamic Programming, Longest Common Subsequence - Greedy Algorithms, Minimum Spanning Trees - Shortest Paths I: Properties, Dijkstra,Bellman-Ford, Linear Programming, Difference Constraints,ll-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson-Advanced Topics

Lecture 1: Introduction - Analysis of Algorithms, Insertion Sort, Mergesort

Up Next
• 2x
• 1.5x
• 1x
• 0.5x
• 0.25x
COPY
PRIVATE CONTENT
OK
0:00
4.0 (58 Ratings)

58 Rates
5
62%
36
4
7%
4
3
12%
7
2
3%
2
1
16%
9