⚙ Algorithms and Data Structures
Based on Nievergelt & Hinrichs, licensed CC BY-SA.
With applications to graphics and geometry. Translated into runnable Scheme and Python with SVG diagrams.
| Chapter | |||
|---|---|---|---|
| 1. | Complexity and O-Notation | Big-O, big-Omega, big-Theta: how to compare algorithms by their growth rates | ⚙ |
| 2. | Recursion | Divide and conquer, recurrence relations, and the master theorem | ⚙ |
| 3. | Sorting | Insertion sort, merge sort, quicksort, heapsort, and the n log n lower bound | ⚙ |
| 4. | Searching | Binary search, hash tables, and interpolation search | ⚙ |
| 5. | Trees | BSTs, AVL trees, B-trees, and the three traversal orders | ⚙ |
| 6. | Graphs | BFS, DFS, topological sort, and connected components | ⚙ |
| 7. | Shortest Paths | Dijkstra, Bellman-Ford, Floyd-Warshall, and negative cycles | ⚙ |
| 8. | Geometric Algorithms | Convex hull, line intersection, closest pair, Voronoi diagrams | ⚙ |
| 9. | Dynamic Programming | Optimal substructure and memoization: Fibonacci, knapsack, edit distance | ⚙ |
| 10. | NP-Completeness | P vs NP, reductions, and the problems we believe are hard | ⚙ |
📺 Video lectures: MIT 6.006 Introduction to Algorithms
Neighbors
- 🔢 Discrete Math — graphs and combinatorics are the mathematical objects algorithms operate on
- 🔀 Theory of Computation — NP-completeness and complexity classes
- 🎰 Probability — randomized algorithms and expected complexity
- △ Geometry — computational geometry shares Voronoi and Delaunay structures