# Introduction to Algorithms

MIT Course , Fall 2005 , Prof. Erik Demaine

477 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 8: Universal Hashing, Perfect Hashing

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

0 Rates
1
0%
0
2
0%
0
3
0%
0
4
0%
0
5
0%
0