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.

IntroductionAlgorithmComplexitySortingAlgorithmsSearchingAlgorithmsGraphTraversalString Matchingand CompressionShortestPathsMinimumSpanningTreesNetwork FlowAdvanced StringAlgorithmsTries
Figure 1: The course map. Each arrow points from a topic to one that builds on it. From analysis the path leads to sorting and searching, and from there to graph algorithms on the left and string algorithms on the right.

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.

Table 1: The connections on the map.
Topic (chapter)Builds onConnection
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)IntroductionAsymptotic notation, loop analysis, recurrence relations and the Master Theorem: the yardstick for every later chapter.
Sorting Algorithms (3)Algorithm ComplexityThe 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 AlgorithmsBinary search in a sorted array; average O(1) search with hashing.
Graph Traversal (5)Algorithm Complexity, Searching AlgorithmsSearching is carried over to graphs: DFS and BFS, strongly connected components, topological sorting.
Shortest Paths (6)Graph TraversalWeights are added to traversal: relaxation, Dijkstra, Bellman-Ford, Floyd-Warshall and A*.
Minimum Spanning Trees (7)Graph Traversal, Shortest PathsThe tree that connects all vertices at the lowest cost; Prim uses the same priority-queue pattern as Dijkstra.
Network Flow (8)Graph TraversalAugmenting paths are found by traversal (BFS in Edmonds-Karp); the max-flow min-cut theorem.
String Matching and Compression (9)Algorithm Complexity, Searching AlgorithmsPattern search in text: KMP, Boyer-Moore, Rabin-Karp; compression with RLE and LZW.
Advanced String Algorithms (10)Sorting Algorithms, String Matching and CompressionString sorting (radix sort), regular expressions and automata, edit distance, the suffix array.
Tries (11)String Matching and Compression, Advanced String AlgorithmsA 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.