http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/
Video Lectures
Audio/video for lectures 20 and 21 are not available.
Lecture notes files.
| SES # |
TOPICS |
| 1 |
Administrivia
- Introduction - Analysis of Algorithms, Insertion Sort, Mergesort |
| 2 |
Asymptotic
Notation - Recurrences - Substitution, Master Method |
| 3 |
Divide-and-Conquer:
Strassen, Fibonacci, Polynomial Multiplication |
| 4 |
Quicksort,
Randomized Algorithms |
| 5 |
Linear-time
Sorting: Lower Bounds, Counting Sort, Radix Sort |
| 6 |
Order
Statistics, Median |
| 7 |
Hashing,
Hash Functions |
| 8 |
Universal
Hashing, Perfect Hashing |
| 9 |
Relation
of BSTs to Quicksort - Analysis of Random BST |
| 10 |
Red-black
Trees, Rotations, Insertions, Deletions |
| 11 |
Augmenting
Data Structures, Dynamic Order Statistics, Interval Trees |
| 12 |
Skip
Lists |
| 13 |
Amortized
Algorithms, Table Doubling, Potential Method |
| 14 |
Competitive
Analysis: Self-organizing Lists |
| 15 |
Dynamic
Programming, Longest Common Subsequence |
| 16 |
Greedy
Algorithms, Minimum Spanning Trees |
| 17 |
Shortest
Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search |
| 18 |
Shortest
Paths II: Bellman-Ford, Linear Programming, Difference Constraints |
| 19 |
Shortest
Paths III: All-pairs Shortest Paths, Matrix Multiplication,
Floyd-Warshall, Johnson |
| 20 |
Quiz 2 Review
Note: No audio or video is available for this session. |
| 21 |
Ethics, Problem Solving (Mandatory
Attendance)
Note: No audio or video is available for this session. |
| 22 |
Advanced
Topics |
| 23 |
Advanced
Topics (cont.) |
| 24 |
Advanced
Topics (cont.) |
| 25 |
Advanced
Topics (cont.) - Discussion of Follow-on Classes |
|
