Special software is required to use some of the files in this section: .rm, mp3 .
In addition to downloadable lecture notes, video and audio files of each lecture are provided below.
Lecture notes files.
| SES # |
TOPICS |
VIDEO LECTURES |
AUDIO |
| L1 |
Administrivia
Introduction
Analysis of Algorithms, Insertion Sort, Mergesort (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 19.5MB) |
| L2 |
Asymptotic Notation (PDF)
Recurrences
Substitution, Master Method |
(RM - 56K)
(RM - 220K)
|
(MP3 - 17.1MB) |
| L3 |
Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 16.6MB) |
| L4 |
Quicksort, Randomized Algorithms (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 19.5MB) |
| L5 |
Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.6MB) |
| L6 |
Order Statistics, Median (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 16.7MB) |
| L7 |
Hashing, Hash Functions (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.9MB) |
| L8 |
Universal Hashing, Perfect Hashing (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 17.5MB) |
| L9 |
Relation of BSTs to Quicksort
Analysis of Random BST (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 19.7MB) |
| L10 |
Red-black Trees, Rotations, Insertions, Deletions (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.3MB) |
| L11 |
Augmenting Data Structures, Dynamic Order Statistics, Interval Trees (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.3MB) |
| L12 |
Skip Lists (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.7MB) |
| L13 |
Amortized Algorithms, Table Doubling, Potential Method (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 19.1MB) |
| L14 |
Competitive Analysis: Self-organizing Lists (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.0MB) |
| L15 |
Dynamic Programming, Longest Common Subsequence (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 17.2MB) |
| L16 |
Greedy Algorithms, Minimum Spanning Trees (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.3MB) |
| L17 |
Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.5MB) |
| L18 |
Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.7MB) |
| L19 |
Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson (PDF) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.2MB) |
| L20 |
Quiz 2 Review (PDF) |
|
|
| L21 |
Ethics, Problem Solving (Mandatory Attendance) (PDF) |
|
|
| L22 |
Advanced Topics |
(RM - 56K)
(RM - 220K)
|
(MP3 - 18.2MB) |
| L23 |
Advanced Topics (cont.) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 17.6MB) |
| L24 |
Advanced Topics (cont.) |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.5MB) |
| L25 |
Advanced Topics (cont.)
Discussion of Follow-on Classes |
(RM - 56K)
(RM - 220K)
|
(MP3 - 20.6MB) |