Introduction to Algorithms

Shows why plausible-looking O(n) 2D divide-and-conquer algorithms can silently fail correctness—and how proving an invariant rescues both correctness and O(n log n) runtime.

Defines the Word-RAM model vs. pointer machines and Python's CPython cost model by iteratively accelerating a document-similarity algorithm from minutes down to milliseconds.

Compares Θ(n²) in-place sorting against divide-and-conquer Merge Sort via recursion-tree cost accounting and auxiliary space trade-offs.

Visualizes implicit array-backed binary trees and proves why bottom-up Build-Max-Heap runs in linear O(n) time rather than O(n log n).

Motivated by real-time airport runway scheduling, Demaine builds augmented Binary Search Trees supporting O(h) rank and range queries.

Proves via Fibonacci recurrence bounds that height-balance invariants keep AVL trees strictly O(log n) tall, then derives single and double rotations cleanly.

Proves the information-theoretic Ω(n log n) comparison-sorting barrier via Stirling's approximation on n!, then breaks through it in linear time using integer Radix Sort.

Rigorous randomized algorithms lecture showing how universal hash functions defeat adversarial key collisions in expected O(1) time.

This lecture explores the table doubling technique for dynamic array resizing and introduces the Karp-Rabin string matching algorithm, examining its probabilistic hashing approach.

This session details open addressing collision resolution strategies in hash tables, including linear and quadratic probing, and introduces principles of cryptographic hashing.

This lecture delves into efficient algorithms for integer arithmetic, focusing on the divide-and-conquer Karatsuba algorithm for fast polynomial and integer multiplication.

This session introduces numerical methods for computing square roots, specifically applying Newton's method for iterative approximation and analyzing its convergence rate.

This lecture introduces Breadth-First Search (BFS) as a fundamental graph traversal algorithm, explaining its application for finding shortest paths in unweighted graphs.

This session covers Depth-First Search (DFS) for graph traversal, demonstrating its use in cycle detection and for performing topological sort on directed acyclic graphs (DAGs).

This lecture defines the single-source shortest paths problem and introduces foundational concepts for solving it on graphs with varying edge weights, setting up subsequent algorithms.

This session provides a detailed examination of Dijkstra's algorithm, analyzing its greedy approach for finding the single-source shortest paths in graphs with non-negative edge weights.

This lecture introduces the Bellman-Ford algorithm, contrasting its iterative relaxation approach with Dijkstra's and demonstrating its ability to handle negative edge weights and detect negative cycles.

This session explores advanced techniques for optimizing Dijkstra's algorithm, focusing on the use of Fibonacci heaps and other priority queue implementations to improve its time complexity.

This introductory dynamic programming lecture covers the Fibonacci sequence calculation and its application to shortest path problems in directed acyclic graphs.

This lecture continues dynamic programming, illustrating its versatility through optimal text justification algorithms and strategic decision-making in the game of Blackjack.

This advanced dynamic programming lecture examines optimal matrix chain parenthesization, calculates string edit distance using the Wagner-Fischer algorithm, and solves the 0/1 Knapsack problem.

This lecture showcases the broad applicability of dynamic programming through unique case studies including optimal guitar fingering, high-score strategies in Tetris, and pathfinding in Super Mario Bros.