Winda

MIT 6.006: Introduction to Algorithms

Contents · 41

  1. 01-Algorithms and ComputationIntroduces algorithmic problem solving, correctness proofs by induction, asymptotic efficiency, the Word-RAM model, and data structures, with birthday matching as a running example.
  2. 01-Algorithms and ComputationIntroduces computational problems and algorithms, emphasizing correctness proofs, efficiency analysis, and clear communication of solutions.
  3. 02-Data Structures and Dynamic ArraysIntroduces sequence and set interfaces, array and linked-list representations, dynamic arrays, and amortized analysis of insertion and deletion costs.
  4. 02-Data Structures and Dynamic ArraysIntroduces sequence interfaces and the distinction between interfaces and data structures, focusing on static sequences and their build, length, iteration, get, and set operations.
  5. 03-Sets and SortingSorting algorithms and their efficiency, including permutation, selection, insertion, and merge sort, with recurrence analysis.Sorting algorithms and their efficiency, including permutation, selection, insertion, and merge sort, with recurrence analysis.
  6. 03-Sets and SortingSet interfaces and their operations, including construction, lookup, insertion, and deletion, and how data structures implement them with different efficiency tradeoffs.
  7. 04-HashingExplains hashing for dynamic sets, including direct-access arrays, collision handling with chaining, universal hash functions, expected performance, and amortized resizing.
  8. 04-HashingIntroduces hashing in set data structures, reviews find and update operations, and begins proving comparison-based lower bounds for search.
  9. 05-Linear SortingStable counting sort and radix sort achieve linear-time sorting for bounded integer keys, bypassing comparison-sort lower bounds.
  10. 05-Linear SortingCompares search structures, explaining direct-access arrays and hash tables, their space tradeoffs, expected versus worst-case performance, and hash-table collision handling.
  11. 06-Binary Trees, Part 1Explains binary-tree structure, traversal and navigation, insertion and deletion, and applications to binary search sets and indexed sequences.Covers binary-tree structure, traversal, navigation, insertion and deletion, and applications to sets and sequences.
  12. 06-Binary Trees, Part 1Introduces rooted binary trees, their nodes, parent and child pointers, and the invariant linking them. Explains how trees aim to support efficient sequence and ordered-set operations.
  13. 07-Binary Trees, Part 2: AVLExplains AVL height balance, tree rotations, and how insertion and deletion restore balance in logarithmic time.
  14. 07-Binary Trees, Part 2: AVLIntroduces binary search trees for ordered sets and motivates AVL height balancing to achieve logarithmic-time operations.
  15. 08-Binary HeapsExplains priority queues, complete-tree array representations, binary heap properties, and heap insertion and deletion.
  16. 08-Binary HeapsIntroduces the priority queue interface and compares arrays and AVL trees as approaches to it, motivating binary heaps and their use in efficient sorting.
  17. 09-Breadth-First SearchDefines graphs, adjacency-list representations, paths, and shortest-path trees, then introduces BFS for computing single-source shortest paths.
  18. 09-Breadth-First SearchIntroduces graph theory, defining vertices, edges, and directed versus undirected graphs, with examples of networks.
  19. 10-Depth-First SearchExplains DFS and full-graph traversal, connected components, topological sorting, cycle detection, and their correctness and running times.
  20. 10-Depth-First SearchGraph theory fundamentals, graph representations, adjacency and neighbors, paths, reachability, and the meaning of linear-time complexity; introduces breadth-first search.
  21. 11-Weighted Shortest PathsDefines weighted shortest paths, negative-weight cycles, shortest-path trees, and the DAG relaxation algorithm for single-source distances.
  22. 11-Weighted Shortest PathsIntroduces weighted graphs, edge-weight representations, and applications such as road distances, network latency, and social relationships.
  23. 12-Bellman-FordBellman-Ford computes shortest-path distances in directed graphs with negative edge weights, detects reachable negative-weight cycles, and runs in O(|V||E|) time.
  24. 12-Bellman-FordIntroduces Bellman–Ford for directed graphs with negative weights, including negative-cycle effects, and shows how reachability pruning yields an O(VE) algorithm.
  25. 13-DijkstraCompares single-source shortest-path algorithms by graph and weight restrictions, and explains Dijkstra’s algorithm, correctness, and priority-queue running times.
  26. 13-DijkstraIntroduces Dijkstra’s algorithm for single-source shortest paths with nonnegative edge weights, building on BFS and contrasting its complexity with Bellman–Ford.
  27. 14-APSP and JohnsonJohnson’s algorithm solves all-pairs shortest paths with negative edge weights when no negative cycle exists, using reweighting, Bellman–Ford, and repeated Dijkstra runs. It explains correctness and running time.
  28. 14-APSP and JohnsonIntroduces all-pairs shortest paths, compares repeated single-source algorithms, and motivates faster methods for weighted directed graphs.
  29. 15-Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, BowlingIntroduces recursive algorithm design using SRT BOT, then develops merge sort, Fibonacci, memoization, dynamic programming, and shortest paths in DAGs.
  30. 15-Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, BowlingIntroduces dynamic programming and the SORT BOT framework for designing recursive algorithms, covering subproblems, dependencies, topological order, base cases, and running time. Uses merge sort as an example.
  31. 16-Dynamic Programming, Part 2: LCS, LIS, CoinsDynamic programming methods and subproblem design, illustrated with longest common subsequence, longest increasing subsequence, and an alternating coin game.
  32. 16-Dynamic Programming, Part 2: LCS, LIS, CoinsIntroduces longest common subsequence and dynamic programming for multiple sequences, including subproblems, recurrence relations, and topological order.
  33. 17-Dynamic Programming, Part 3: APSP, Parens, PianoDynamic programming methods for shortest paths and Floyd–Warshall, plus arithmetic parenthesization and piano fingering.
  34. 17-Dynamic Programming, Part 3: APSP, Parens, PianoDynamic programming subproblem expansion for Bellman–Ford, all-pairs shortest paths, arithmetic parenthesization, and instrument fingering.
  35. 18-Dynamic Programming, Part 4: Rods, Subset Sum, PseudopolynomialExplains dynamic programming, rod cutting, subset sum, and pseudopolynomial versus polynomial running time.
  36. 18-Dynamic Programming, Part 4: Rods, Subset Sum, PseudopolynomialDynamic programming on integer inputs, including rod cutting, subset sum, and pseudo-polynomial time.
  37. 19-ComplexityDefines decision problems, decidability, P and NP, reductions, NP-completeness, and examples of computationally hard problems.
  38. 19-ComplexityIntroduces computational complexity, P and EXP, polynomial versus exponential time, decision problems, and examples such as chess and negative-weight-cycle detection.
  39. 20-Course ReviewReviews algorithm design, correctness, and efficiency, including complexity classes and core techniques for searching, sorting, graphs, recursion, dynamic programming, and greedy methods. Surveys advanced algorithms and related applications.
  40. 20-Course ReviewReviews 6.006’s goals: designing algorithms, proving correctness, analyzing efficiency and communicating solutions, while connecting the course to complexity theory and future study.
  41. 21-Algorithms—Next StepsComputational origami and geometric folding algorithms, including origami design, crease patterns, foldability, and deployable structures.