Algorithms
Course Map
This page puts every chapter of the course on one map. Each chapter is a node, and an arrow shows which idea from an earlier topic the next one relies on. Read it before the course starts to see where the topics are heading, or during the course to see where you are.
Figure 1 shows the connections between the topics. Each node is a chapter, and an arrow indicates which idea of the earlier topic the later one relies on. Only the closest connections are drawn on the map; every chapter that a given chapter depends on is listed in Table 1.
| Topic (chapter) | Builds on | Connection |
|---|---|---|
| Introduction (1) | — | The notion of an algorithm, input size, and how running time grows with the input; counting operations line by line. |
| Algorithm Complexity (2) | Introduction | Asymptotic notation, loop analysis, recurrence relations and the Master Theorem: the yardstick for every later chapter. |
| Sorting Algorithms (3) | Algorithm Complexity | The first large class of problems; the move from O(n²) methods to O(n log n) methods is measured by analysis. |
| Searching Algorithms (4) | Algorithm Complexity, Sorting Algorithms | Binary search in a sorted array; average O(1) search with hashing. |
| Graph Traversal (5) | Algorithm Complexity, Searching Algorithms | Searching is carried over to graphs: DFS and BFS, strongly connected components, topological sorting. |
| Shortest Paths (6) | Graph Traversal | Weights are added to traversal: relaxation, Dijkstra, Bellman-Ford, Floyd-Warshall and A*. |
| Minimum Spanning Trees (7) | Graph Traversal, Shortest Paths | The tree that connects all vertices at the lowest cost; Prim uses the same priority-queue pattern as Dijkstra. |
| Network Flow (8) | Graph Traversal | Augmenting paths are found by traversal (BFS in Edmonds-Karp); the max-flow min-cut theorem. |
| String Matching and Compression (9) | Algorithm Complexity, Searching Algorithms | Pattern search in text: KMP, Boyer-Moore, Rabin-Karp; compression with RLE and LZW. |
| Advanced String Algorithms (10) | Sorting Algorithms, String Matching and Compression | String sorting (radix sort), regular expressions and automata, edit distance, the suffix array. |
| Tries (11) | String Matching and Compression, Advanced String Algorithms | A tree that stores strings by their common prefixes; autocomplete, the suffix trie and Aho–Corasick. |
The backbone of the map can be read as analysis → sorting and searching → graphs and strings. Counting operations and asymptotic analysis in the first two chapters are the yardstick for every later chapter. Sorting and searching are both the tools and the examples for what follows: traversing a graph is searching carried over to graphs, and the shortest path, spanning tree and flow algorithms are built on traversal. String matching is searching applied to text; advanced string algorithms and the trie grow out of this foundation. Design paradigms, hard problems and other models of computation are built on this foundation in the Advanced Algorithms course.
Course page: Algorithms · Glossary · © Sercan Külcü. All rights reserved.