Algorithms

BSCS students taking a Design and Analysis of Algorithms course — or anyone who wants a rigorous, proof-oriented algorithms education — can read the complete textbook “Algorithms” by Jeff Erickson, free from its official source. It’s a 13-chapter, university-level text that builds from recursion and backtracking through dynamic programming, greedy algorithms, a full sequence of graph algorithms, network flow, and finally NP-hardness.

This edition is published directly by the author, a computer science professor at the University of Illinois at Urbana-Champaign, and grew out of the algorithms courses he has taught there for many years — covering recursion and backtracking (Chapters 1–2), dynamic programming (Chapter 3), greedy algorithms (Chapter 4), graph algorithms from basic traversal through all-pairs shortest paths (Chapters 5–9), maximum flow and its applications (Chapters 10–11), and NP-hardness (Chapter 12) — making it both a complete course textbook and a lasting reference.

Book Overview

Chapter List

Chapter 0: Introduction

Difficulty: Beginner · Early Semester · Algorithms Foundations · Key topics: what is an algorithm, multiplication algorithms, congressional apportionment, describing and analyzing algorithms

The opening chapter grounds the whole book in a simple question: what actually counts as an algorithm? Using everyday examples like grade-school multiplication and the real historical problem of congressional apportionment, it shows how a precise, unambiguous, finite procedure differs from a vague description of a task. It also sets expectations for how algorithms will be described (pseudocode over any particular programming language) and briefly previews what “analyzing” an algorithm’s correctness and running time actually means for the rest of the book.

Key Points:

• An algorithm must be a precise, unambiguous, finite sequence of steps — not just a vague description of what to do.
• Grade-school multiplication is used as a first concrete example of an algorithm most readers already know without having thought of it that way.
• The historical congressional apportionment problem shows that even a seemingly simple counting task can hide surprising algorithmic subtlety.
• Algorithms in the book are described in structured pseudocode, deliberately independent of any specific programming language.
• Analyzing an algorithm means reasoning formally about both its correctness (does it always give the right answer?) and its efficiency (how much time/space does it use?).

Memory Tip: Before calling any procedure you write an “algorithm”, ask whether every step is precise enough that two different people (or machines) following it would always produce the same result.

Common Mistake: Treating “I have an idea for how to solve this” as the same thing as having an algorithm — an idea becomes an algorithm only once every step is made precise and unambiguous enough to execute mechanically.

Important Questions:

• Q1: What distinguishes an algorithm from a general idea or strategy for solving a problem? An algorithm must be a precise, unambiguous, finite sequence of well-defined steps that can be followed mechanically to produce a correct result every time, whereas a general idea or strategy may be vague about exact steps, edge cases, or when it terminates.
• Q2: Why does the chapter use the historical congressional apportionment problem as an early example? It shows that even a task that sounds like simple counting or division (assigning a fixed number of congressional seats fairly among states based on population) can hide real algorithmic subtlety and historical controversy, motivating why precise algorithmic thinking matters even outside obviously “computational” problems.

Chapter 1: Recursion

Difficulty: Beginner · Early Semester · Algorithms Foundations · Key topics: reductions, simplify-and-delegate, Tower of Hanoi, mergesort, quicksort, recursion trees, linear-time selection

This chapter establishes recursion as the book’s central problem-solving pattern: reduce a problem to one or more smaller instances of the same problem, solve those recursively, and combine the results. Classic examples — Tower of Hanoi, mergesort, and quicksort — illustrate the “simplify and delegate” mindset, and recursion trees are introduced as a visual tool for analyzing recursive running time. The chapter closes with two less obvious recursive algorithms, linear-time selection and fast multiplication, showing recursion’s reach well beyond textbook sorting examples.

Key Points:

• Recursion works by reducing a problem to smaller instance(s) of the same problem, trusting the recursive call to solve those correctly (the “simplify and delegate” or reduction mindset).
• Tower of Hanoi is used as the cleanest illustration of pure recursive problem-solving, with an exponential number of moves as the cost of an elegant recursive structure.
• Mergesort and quicksort are presented as two contrasting divide-and-conquer sorting algorithms — one splitting arbitrarily and merging carefully, the other partitioning carefully and combining trivially.
• Recursion trees give a visual, level-by-level way to add up the total work done by a recursive algorithm across all levels of recursive calls.
• Linear-time selection (finding the k-th smallest element without fully sorting) and fast multiplication show that recursion can beat naive approaches even on problems that don’t look inherently recursive at first glance.

Memory Tip: When starting a recursive algorithm, explicitly answer three questions: what is the smaller subproblem, what do I trust the recursive call to already have solved, and how do I combine the recursive result(s) into a solution for the original problem.

Common Mistake: Trying to trace through every recursive call by hand to understand why an algorithm works, instead of trusting the recursive call (the “leap of faith”) and focusing only on how the current level correctly uses that trusted result.

Important Questions:

• Q1: What is the “simplify and delegate” mindset for designing a recursive algorithm? It means reducing the current problem to one or more strictly smaller instances of the same problem, trusting (“delegating” to) the recursive call to correctly solve those smaller instances, and focusing your own reasoning only on how to correctly combine those trusted results into a solution for the original, larger problem.
• Q2: Why are mergesort and quicksort both considered divide-and-conquer algorithms, despite working quite differently? Both divide the sorting problem into smaller subproblems and solve them recursively, but they split the work at different points: mergesort splits the array trivially in half and does the hard work while merging the two sorted halves back together, while quicksort does the hard work up front partitioning around a pivot and then combines the sorted results trivially, since no merging step is needed.

Chapter 2: Backtracking

Difficulty: Intermediate · Early-Mid Semester · Algorithms Foundations · Key topics: N Queens, game trees, subset sum, text segmentation, longest increasing subsequence, optimal binary search trees

Backtracking is introduced as systematic trial-and-error: build a candidate solution incrementally, and as soon as a partial candidate can no longer possibly lead to a valid full solution, abandon it and try something else instead of continuing down a doomed path. N Queens and game trees illustrate the core pattern, and Subset Sum, text segmentation, and longest increasing subsequence show how the same general recursive-exploration structure applies across very different-looking problems, setting up the motivation for dynamic programming in the next chapter.

Key Points:

• Backtracking systematically builds a candidate solution step by step, abandoning (“backtracking” out of) any partial candidate as soon as it is known to be unable to lead to a valid solution.
• N Queens is the canonical backtracking example: placing queens on a chessboard one row at a time, backtracking whenever a placement creates a conflict.
• Game trees extend the same idea to adversarial settings, where the recursive exploration alternates between two players’ choices.
• The general backtracking pattern reappears, differently dressed, in Subset Sum, text segmentation, and longest increasing subsequence — all explored recursively by trying each choice at each step.
• This chapter’s recursive-but-often-inefficient solutions to problems like Subset Sum and longest increasing subsequence directly motivate dynamic programming as a way to avoid repeating identical work.

Memory Tip: Backtracking = recursion + early abandonment: as soon as you can prove a partial solution cannot possibly be extended into a valid full solution, stop exploring that branch immediately rather than continuing to build on it.

Common Mistake: Confusing backtracking with brute force that always explores everything — the entire point of backtracking is to prune (skip) branches early once they are known to be hopeless, which is what keeps it far faster than exhaustive search in practice.

Important Questions:

• Q1: What is the core idea that defines a backtracking algorithm? A backtracking algorithm builds a candidate solution incrementally, one decision at a time, and as soon as a partial candidate is determined to be incapable of being extended into a valid complete solution, the algorithm abandons (“backtracks” out of) that branch and tries a different choice, rather than continuing to build on a doomed partial solution.
• Q2: Why does this chapter’s recursive approach to problems like Subset Sum and longest increasing subsequence motivate dynamic programming in the next chapter? Because the naive recursive/backtracking solutions to these problems often re-solve the exact same subproblems many times over as the recursion branches, doing a huge amount of duplicated work; dynamic programming (Chapter 3) addresses this directly by recognizing and reusing solutions to subproblems that recur, rather than recomputing them.

Chapter 3: Dynamic Programming

Difficulty: Intermediate · Mid Semester · Algorithms Foundations · Key topics: Fibonacci, memoization vs smart recursion, edit distance, subset sum, optimal binary search trees, DP on trees

Building directly on the previous chapter’s repeated-subproblem problem, this chapter frames dynamic programming as “recursion done smartly”: recognize that a recursive algorithm is solving identical subproblems repeatedly, then either cache those results (memoization) or restructure the computation bottom-up to fill in a table of subproblem answers directly. Using Fibonacci as the simplest possible illustration, it then works through meatier examples — edit distance, subset sum revisited, optimal binary search trees, and dynamic programming on trees — each showing how to identify the right subproblems and the recurrence relating them.

Key Points:

• Dynamic programming is “smart recursion”: the recursive structure of the problem stays the same, but repeated identical subproblems are solved once and reused, instead of recomputed from scratch every time.
• Fibonacci demonstrates the core lesson cleanly — naive recursion is exponential, but caching (memoizing) each computed value makes it linear.
• A famous chapter warning (“Warning: Greed is Stupid”) explicitly cautions against assuming a locally-greedy choice is always correct where a full dynamic-programming recurrence is actually required.
• Edit distance (the minimum number of insertions/deletions/substitutions to turn one string into another) is developed as a substantial worked example of building a DP table from a recurrence.
• Optimal binary search trees and dynamic programming on trees extend the same subproblem-and-recurrence thinking to more structurally complex inputs than simple sequences.

Common Mistake: The chapter itself warns against this directly: don’t assume the locally “greedy”, obviously-best choice at each step is always correct — several DP problems in this chapter have a tempting greedy shortcut that gives the wrong answer, which is exactly why a full recurrence over subproblems is needed instead.

Common Mistake: Writing a memoized recursive solution without first correctly identifying what a “subproblem” even is — memoization only produces speed and correct answers when it is caching the results of genuinely well-defined, correctly-parameterized subproblems, not an arbitrary cache of function calls.

Important Questions:

• Q1: What is the key difference between the naive recursive Fibonacci algorithm and its dynamic-programming version? The naive recursive version repeatedly recomputes the same Fibonacci values many times as the recursion branches, giving exponential running time; the dynamic-programming version computes each distinct Fibonacci value only once, either by caching results as they’re computed (memoization) or by filling a table bottom-up, giving linear running time instead.
• Q2: What warning does the chapter give about greedy-looking choices in dynamic programming problems? It explicitly warns (“Warning: Greed is Stupid”) that choosing whatever locally looks best at each step is often not correct for these problems — several examples in the chapter have a tempting greedy shortcut that produces a wrong final answer, which is precisely why a full dynamic-programming recurrence considering all relevant subproblems is required instead of a simple greedy rule.

Chapter 4: Greedy Algorithms

Difficulty: Intermediate · Mid Semester · Algorithms Foundations · Key topics: storing files on tape, scheduling classes, the greedy pattern, Huffman codes, stable matching

Having just warned that greedy reasoning fails for many dynamic-programming problems, this chapter turns to the flip side: problems where a simple, irrevocable, locally-optimal choice at each step actually does produce a globally optimal solution, and why. Using storing files on tape and scheduling classes as accessible warm-ups, it draws out the general pattern behind correct greedy algorithms, then covers two classic, more substantial greedy algorithms — Huffman coding for optimal prefix-free compression, and stable matching (the Gale-Shapley algorithm) for pairing two groups according to mutual preferences.

Key Points:

• A greedy algorithm makes one irrevocable, locally-optimal-looking choice at each step and never reconsiders it, which only produces a correct globally-optimal answer for problems with the right structural properties.
• Storing files on tape and scheduling classes are used as accessible problems where the greedy strategy can actually be proven correct, in contrast to the DP chapter’s warning examples.
• The general pattern for proving a greedy algorithm correct typically involves an exchange argument: showing any optimal solution can be transformed into the greedy solution without making it worse.
• Huffman coding builds an optimal prefix-free binary code by greedily and repeatedly merging the two least-frequent symbols/subtrees together.
• Stable matching (Gale-Shapley) greedily proposes and rejects matches according to preference lists, guaranteeing a stable pairing where no two participants would both prefer each other over their assigned partners.

Practice Tip: Before trusting a greedy strategy on a new problem, try to construct a small counterexample where the locally-best choice leads somewhere worse overall — if you can’t find one after real effort, that’s a hint (not a proof) that an exchange-argument correctness proof might actually go through for this problem.

Common Mistake: Assuming a greedy strategy is correct just because it “seems reasonable” or worked on a similar-looking problem — correctness of a greedy algorithm always requires an actual proof (typically an exchange argument), since many superficially similar problems have greedy strategies that fail.

Important Questions:

• Q1: What is the fundamental difference in approach between a greedy algorithm and dynamic programming? A greedy algorithm makes one locally-optimal-looking choice at each step and commits to it permanently without reconsidering, while dynamic programming considers and stores results across many subproblems (potentially many different choices) to guarantee a globally optimal answer — greedy is only valid when the specific problem’s structure guarantees the locally-best choice never needs to be revisited.
• Q2: What does Huffman coding greedily choose to do at each step, and why does that produce an optimal code? At each step, Huffman coding takes the two currently least-frequent symbols or subtrees and merges them into a new combined subtree; repeating this always merges the least-frequent items last (deepest in the resulting tree), which is exactly the structural property an optimal prefix-free code needs — frequent symbols get short codes and rare symbols get longer ones.

Chapter 5: Basic Graph Algorithms

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: graph definitions and representations, adjacency list/matrix, whatever-first search, flood fill

This chapter lays the graph-theoretic groundwork the rest of Part II depends on: formal definitions of graphs (directed/undirected, weighted/unweighted), the standard ways to represent a graph in code (adjacency lists and adjacency matrices, with their different space/time trade-offs), and the generic “whatever-first search” template that both depth-first and breadth-first search (covered in the following two chapters) turn out to be specific instances of. Flood fill is used as a simple, concrete graph-reduction example tying the abstract material to something visually intuitive.

Key Points:

• A graph consists of vertices and edges, and can be directed or undirected, weighted or unweighted — the right variant depends entirely on what real-world relationship is being modeled.
• Adjacency lists and adjacency matrices are the two standard graph representations, trading off space efficiency against the speed of checking whether a specific edge exists.
• “Whatever-first search” is presented as a single generic graph-traversal template, parameterized by which vertex is explored next — depth-first and breadth-first search are just two specific policies for that choice.
• Flood fill (as in a paint bucket tool) is used as a simple, visually intuitive application of basic graph traversal.
• Choosing the right graph representation for a given algorithm’s needs is presented as a genuine design decision, not a minor implementation detail.

Memory Tip: Remember “whatever-first search” as the parent template: depth-first search always explores the most recently discovered vertex next (a stack), and breadth-first search always explores the earliest discovered vertex next (a queue) — same skeleton, different exploration order.

Common Mistake: Defaulting to an adjacency matrix out of habit for every graph problem — for a sparse graph (relatively few edges compared to the number of possible ones), an adjacency list is typically far more space-efficient and often faster for the traversal algorithms covered in the next few chapters.

Important Questions:

• Q1: What is the key space/time trade-off between adjacency lists and adjacency matrices? An adjacency matrix uses space proportional to the square of the number of vertices regardless of how many edges actually exist, but allows checking whether a specific edge exists in constant time; an adjacency list uses space proportional to the actual number of edges (much less for sparse graphs), but checking whether a specific edge exists can take longer, proportional to that vertex’s degree.
• Q2: What does it mean that depth-first search and breadth-first search are both instances of “whatever-first search”? Whatever-first search is a single generic graph-traversal template that repeatedly picks some not-yet-visited discovered vertex to explore next; depth-first search and breadth-first search are simply two specific rules for which vertex to pick next (most-recently-discovered for DFS, using a stack; earliest-discovered for BFS, using a queue), rather than being fundamentally different algorithms.

Chapter 6: Depth-First Search

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: preorder/postorder, cycle detection, topological sort, DFS as dynamic programming, strong connectivity

This chapter develops depth-first search (DFS) as a surprisingly versatile tool, not just a traversal method. It covers preorder and postorder numbering of visited vertices, using DFS to detect cycles in a graph, and topological sorting of a directed acyclic graph (ordering vertices so every edge points forward). It draws an explicit connection between DFS and dynamic programming via memoization on a graph’s structure, and closes with strong connectivity — identifying groups of vertices in a directed graph that can all reach each other — computable in linear time using two carefully ordered depth-first searches.

Key Points:

• Preorder records when a vertex is first discovered during DFS; postorder records when DFS has finished fully exploring everything reachable from it — both orderings are useful for different purposes.
• A directed graph has a cycle if and only if DFS ever encounters a “back edge” — an edge to a vertex that is still actively on the current recursive DFS path.
• Topological sort (ordering vertices of a directed acyclic graph so every edge points from earlier to later in the order) falls directly out of reverse postorder DFS numbering.
• DFS is explicitly connected back to dynamic programming: memoizing values across a DAG’s structure is essentially a graph-shaped dynamic program, with DFS providing the traversal order.
• Strong connectivity (which vertices in a directed graph can all reach each other) can be computed for an entire graph in linear time using two passes of depth-first search.

Memory Tip: To detect a cycle with DFS, watch for an edge pointing to a vertex that is currently “on the stack” (an ancestor in the current recursive DFS path, not yet postorder-finished) — an edge to an already-fully-finished vertex is not a cycle.

Common Mistake: Confusing “already visited” with “currently on the DFS recursion stack” when detecting cycles — in a directed graph, an edge to a vertex that was visited and already fully finished (postorder-complete) via a different path is not a back edge and does not indicate a cycle.

Important Questions:

• Q1: How does depth-first search detect whether a directed graph contains a cycle? DFS detects a cycle by finding a “back edge” — an edge from the current vertex to some other vertex that is still actively on the current recursive DFS call stack (an ancestor in the DFS tree that has not yet finished being explored); if such an edge exists anywhere during the traversal, the graph contains a cycle.
• Q2: How is topological sort of a directed acyclic graph obtained from depth-first search? Topological sort is obtained by running DFS to completion and recording each vertex’s postorder number (the order in which DFS finishes exploring everything reachable from it), then listing the vertices in reverse postorder — this guarantees that every directed edge points from an earlier vertex to a later one in the resulting order.

Chapter 7: Minimum Spanning Trees

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: the minimum spanning tree, Borůvka’s algorithm, Jarník’s (Prim’s) algorithm, Kruskal’s algorithm

This chapter covers the minimum spanning tree (MST) problem — connecting all vertices of a weighted graph with the minimum total edge weight, using no cycles — and, notably, presents it not as three unrelated algorithms but as three different greedy strategies for solving the same underlying problem, all provably correct thanks to a shared cut property. It covers Borůvka’s algorithm (each component greedily picks its cheapest outgoing edge, in parallel), Jarník’s algorithm (commonly called Prim’s, growing one tree greedily from a single vertex), and Kruskal’s algorithm (greedily adding the globally cheapest edge that doesn’t create a cycle).

Key Points:

• A minimum spanning tree connects every vertex of a weighted graph using the minimum possible total edge weight, with no cycles — and for graphs with distinct edge weights, that MST is unique.
• All three classic MST algorithms in this chapter are correct because of the same underlying cut property, not because of three unrelated arguments — they are variations on one greedy theme.
• Borůvka’s algorithm has every current tree component simultaneously pick its own cheapest outgoing edge, repeating until everything is connected.
• Jarník’s algorithm (often called Prim’s algorithm) grows a single tree outward from one starting vertex, always adding the cheapest edge leaving the current tree.
• Kruskal’s algorithm ignores tree structure while building and instead greedily considers all edges from cheapest to most expensive, adding each one unless it would create a cycle.

Memory Tip: Keep the three algorithms straight by what each one is greedy about: Borůvka — every component picks its own cheapest edge at once; Jarník/Prim — one tree always grows by its single cheapest available edge; Kruskal — edges are considered globally, cheapest first, regardless of which component they touch.

Common Mistake: Assuming these three MST algorithms need three completely different correctness proofs because they look so different operationally — in fact all three are justified by the same cut property (the cheapest edge crossing any cut of the graph is always safe to include), which is the chapter’s key unifying insight.

Important Questions:

• Q1: What guarantees that a graph with distinct edge weights has a unique minimum spanning tree? When all edge weights in the graph are distinct (no ties), the cut property applies unambiguously at every step of any correct MST algorithm — there is always exactly one cheapest edge crossing any given cut, which forces every correct greedy MST algorithm to arrive at the same single unique tree, regardless of which of the three algorithms (Borůvka’s, Jarník’s, or Kruskal’s) is used.
• Q2: What is the key operational difference between Jarník’s (Prim’s) algorithm and Kruskal’s algorithm? Jarník’s algorithm grows a single connected tree outward from one starting vertex, at every step adding the cheapest edge that connects a new vertex to the tree already built so far; Kruskal’s algorithm instead considers all of the graph’s edges globally in increasing order of weight, adding each edge as long as it connects two currently-separate components (i.e., doesn’t create a cycle), regardless of whether those components were grown from the same starting vertex.

Chapter 8: Shortest Paths

Difficulty: Advanced · Mid-Late Semester · Graph Algorithms · Key topics: shortest path trees, negative edges, BFS for unweighted graphs, DAG shortest paths, Dijkstra’s algorithm, Bellman-Ford

This chapter tackles the single-source shortest path problem across a progression of increasingly general settings, showing that no single algorithm is best for every case. It starts with the simplest case (unweighted graphs, solved by plain breadth-first search), moves to directed acyclic graphs (solved via depth-first-search-based dynamic programming), then to general weighted graphs with non-negative weights (Dijkstra’s greedy best-first algorithm), and finally to graphs that may contain negative edge weights, where Dijkstra’s greedy assumption breaks and the more general, dynamic-programming-based Bellman-Ford algorithm is required instead.

Key Points:

• For unweighted graphs, breadth-first search alone already computes correct shortest paths, since every edge effectively has the same weight of 1.
• For a directed acyclic graph, shortest paths can be computed in linear time using a DFS-based dynamic program processed in reverse topological order — no need for Dijkstra’s or Bellman-Ford’s extra machinery.
• Dijkstra’s algorithm greedily finalizes the closest not-yet-finalized vertex at each step, which is correct only when all edge weights are non-negative.
• Negative edge weights break Dijkstra’s core greedy assumption (that once a vertex is finalized, its distance can never improve later), which is exactly why it can give wrong answers when negative edges are present.
• Bellman-Ford handles negative edge weights correctly (and can detect negative cycles, where no shortest path even exists) by repeatedly relaxing all edges rather than greedily finalizing vertices one at a time.

Common Mistake: Running Dijkstra’s algorithm on a graph that has any negative edge weights is a classic mistake — Dijkstra’s greedy “finalize the closest vertex” step assumes a vertex’s shortest distance can never improve after being finalized, and a later negative edge can violate exactly that assumption, producing a wrong answer without any error or warning.

Common Mistake: Reaching for Dijkstra’s algorithm out of habit as “the” shortest path algorithm regardless of the input — the chapter’s whole structure argues the opposite: the right algorithm (plain BFS, DAG dynamic programming, Dijkstra’s, or Bellman-Ford) depends entirely on the specific properties of the graph at hand.

Important Questions:

• Q1: Why does Dijkstra’s algorithm fail to produce correct results on graphs with negative edge weights? Dijkstra’s algorithm greedily finalizes the not-yet-finalized vertex with the smallest known tentative distance at each step, relying on the assumption that once a vertex is finalized, no later-discovered edge could ever produce a shorter path to it; a negative edge weight can violate this assumption by making a path through a vertex discovered later actually shorter than a distance already finalized, which the algorithm has no mechanism to correct.
• Q2: Why is plain breadth-first search sufficient to solve the shortest path problem on an unweighted graph, without needing Dijkstra’s algorithm at all? In an unweighted graph, every edge effectively contributes the same cost (1) to a path’s total length, so the shortest path in terms of total weight is exactly the path using the fewest edges; breadth-first search naturally explores vertices in increasing order of number of edges from the source, which is precisely what’s needed, making Dijkstra’s more general (and more expensive) machinery unnecessary.

Chapter 9: All-Pairs Shortest Paths

Difficulty: Advanced · Late Semester · Graph Algorithms · Key topics: lots of single sources, reweighting, Johnson’s algorithm, DP and divide-and-conquer approaches, Floyd-Warshall

This chapter extends shortest-path computation from a single source to all pairs of vertices at once. It starts with the naive “lots of single sources” approach (just run the previous chapter’s algorithm from every vertex), then introduces reweighting — adjusting edge weights so they become non-negative without changing which paths are shortest — as the key trick behind Johnson’s algorithm, letting the faster non-negative-weight algorithm (Dijkstra’s) be reused even when the original graph has negative edges. It also covers dynamic-programming and divide-and-conquer formulations, and closes with the compact, widely taught Floyd-Warshall algorithm.

Key Points:

• The naive “lots of single sources” approach solves all-pairs shortest paths by simply running a single-source algorithm once from every vertex, which is correct but often not the fastest option.
• Reweighting adjusts every edge’s weight (using a clever technique based on shortest distances from an added virtual source vertex) so that all weights become non-negative while every shortest path in the graph stays the shortest path.
• Johnson’s algorithm uses reweighting specifically so that Dijkstra’s algorithm (which requires non-negative weights) can be safely run from every vertex, even on a graph that originally had negative edges.
• A direct dynamic-programming formulation and a divide-and-conquer formulation are both shown to solve all-pairs shortest paths, illustrating that this problem, like earlier ones in the book, admits multiple valid algorithmic strategies.
• The Floyd-Warshall algorithm solves all-pairs shortest paths with a remarkably compact dynamic program that considers, for each possible intermediate vertex in turn, whether routing through it improves any pair’s shortest known distance.

Memory Tip: Remember reweighting’s purpose precisely: it does not change which path between any two vertices is shortest, it only shifts every edge weight so that all weights become non-negative, which is exactly what lets the faster Dijkstra-based approach be reused safely.

Common Mistake: Assuming all-pairs shortest paths always requires a fundamentally different, more complex algorithm than single-source shortest paths — the chapter shows the simplest correct approach is just running a single-source algorithm from every vertex; the more advanced techniques (reweighting, Floyd-Warshall) are about improving efficiency, not about correctness being otherwise unreachable.

Important Questions:

• Q1: What problem does reweighting solve, and how does it enable Johnson’s algorithm to use Dijkstra’s algorithm? Reweighting adjusts every edge’s weight, using distances computed from an added virtual source vertex, so that every edge weight becomes non-negative while every shortest path between any two original vertices remains the shortest path under the new weights; this matters because Dijkstra’s algorithm is only correct on graphs with non-negative weights, so reweighting lets Johnson’s algorithm safely run the faster Dijkstra’s algorithm from every vertex even when the original graph had negative edges.
• Q2: What is the core idea behind the Floyd-Warshall algorithm’s dynamic program? Floyd-Warshall considers each vertex in turn as a potential intermediate stop on a path between every pair of vertices, and updates its table of best-known shortest distances whenever routing a pair’s path through that intermediate vertex turns out to be shorter than the best distance already known for that pair — after considering every vertex as a potential intermediate stop, the table holds correct shortest distances for all pairs.

Chapter 10: Maximum Flows and Minimum Cuts

Difficulty: Advanced · Late Semester · Graph Algorithms · Key topics: flows, cuts, the maxflow-mincut theorem, Ford-Fulkerson augmenting paths, Edmonds-Karp

This chapter introduces network flow, modeling a graph as a network of pipes with per-edge capacities and asking how much total flow can be pushed from a source to a sink without violating any capacity. It defines cuts (ways of splitting the graph’s vertices into two sides) as a natural upper bound on flow, and states the celebrated maxflow-mincut theorem: the maximum possible flow always exactly equals the minimum-capacity cut. Ford and Fulkerson’s augmenting-path algorithm is developed as the fundamental method for computing a maximum flow, and Edmonds and Karp’s refinement (always augmenting along a shortest available path) is shown to guarantee the algorithm actually terminates efficiently.

Key Points:

• A flow network models each edge as a pipe with a maximum capacity, and asks for the largest total flow that can be pushed from a designated source vertex to a designated sink vertex.
• A cut splits the graph’s vertices into two sides (one containing the source, one containing the sink); its capacity is the total capacity of edges crossing from the source’s side to the sink’s side.
• The maxflow-mincut theorem states that the maximum possible flow in any network is always exactly equal to the minimum-capacity cut separating source from sink — not just an upper bound, but an equality.
• Ford and Fulkerson’s augmenting-path algorithm repeatedly finds a path from source to sink with spare capacity (using residual edges that can also “undo” previously sent flow) and pushes more flow along it, until no such path remains.
• Edmonds and Karp’s refinement — always choosing the shortest available augmenting path (by number of edges) — guarantees the algorithm terminates in polynomial time, avoiding pathological slow cases the plain Ford-Fulkerson method can hit.

Memory Tip: Remember the maxflow-mincut theorem as a duality: you know a flow is maximum the moment you find any cut whose capacity exactly equals that flow’s value, since flow can never exceed any cut’s capacity, and the theorem guarantees such a matching cut always exists at the true maximum.

Common Mistake: Forgetting that augmenting paths must be found in the residual graph, not the original graph — the residual graph includes reverse edges that let the algorithm effectively “undo” flow sent earlier if a better overall routing is found, and skipping this is a common source of incorrect implementations of Ford-Fulkerson.

Important Questions:

• Q1: What does the maxflow-mincut theorem state, and why is it more than just an upper bound? It states that the maximum possible flow from source to sink in a flow network is always exactly equal to the minimum-capacity cut separating them — not merely that flow can never exceed the minimum cut (which is intuitively true as an upper bound), but that this bound is always achievable exactly, giving a guaranteed way to certify that a given flow is truly maximum by exhibiting a matching cut.
• Q2: Why does Edmonds and Karp’s refinement of always choosing the shortest augmenting path matter? Plain Ford-Fulkerson is only guaranteed to terminate (and can be extremely slow) when capacities are arbitrary real or large integer values, because a poor choice of augmenting paths can require an enormous number of augmentations; always choosing the shortest available augmenting path (by number of edges) guarantees the algorithm terminates in a polynomial number of augmentations regardless of the capacity values, avoiding this pathological slowness.

Chapter 11: Applications of Flows and Cuts

Difficulty: Advanced · Late Semester · Graph Algorithms · Key topics: edge-disjoint and vertex-disjoint paths, bipartite matching, disjoint-path covers, baseball elimination, project selection

Rather than introducing new algorithms, this chapter shows off the surprising reach of maximum flow as a modeling tool: many problems that don’t look like flow problems at all turn out to be solvable by cleverly building an appropriate flow network and running the previous chapter’s algorithms on it. Edge-disjoint and vertex-disjoint paths, bipartite matching (pairing two groups according to compatibility), disjoint-path covers, the baseball elimination problem (whether a team can still mathematically finish first), and project selection are all reduced to maximum flow, turning one algorithm into a widely reusable problem-solving hammer.

Key Points:

• Edge-disjoint and vertex-disjoint paths (finding the most paths between two vertices that don’t share edges, or don’t share intermediate vertices, respectively) are both solved by carefully constructing an appropriate flow network.
• Bipartite matching (optimally pairing items from two distinct groups according to compatibility) reduces directly to maximum flow by connecting a source to one side, the other side to a sink, and compatible pairs in between with unit capacities.
• Vertex capacities (limiting how much flow can pass through a vertex, not just an edge) are handled by a standard modeling trick: splitting each capacity-limited vertex into an “in” and “out” copy connected by a capacity-limited edge.
• The baseball elimination problem — determining whether a team can still mathematically finish in first place given remaining games — is answered by checking whether a specific flow network achieves full flow on its source edges.
• Project selection (choosing which interdependent projects to undertake to maximize net profit) is solved via a minimum-cut formulation of an appropriately constructed flow network.

Practice Tip: When a new problem asks for some kind of maximum count, pairing, or feasibility subject to capacity-like constraints, try explicitly asking: what would the source, sink, vertices, edges, and capacities need to be for this to become a maximum flow problem? — this chapter’s pattern of reductions is the main transferable skill to take away from it.

Common Mistake: Treating each application in this chapter as a brand-new algorithm to memorize, rather than recognizing that all of them are the exact same maximum-flow/minimum-cut algorithms from Chapter 10 applied to a cleverly constructed network — the real skill being taught is the modeling/reduction step, not new algorithmic machinery.

Important Questions:

• Q1: How does bipartite matching get reduced to a maximum flow problem? A flow network is built with a source vertex connected to every vertex on one side of the bipartite graph, a sink vertex connected to every vertex on the other side, and unit-capacity edges connecting each pair of compatible vertices between the two sides; the maximum flow in this network then exactly equals the maximum number of compatible pairs that can be matched simultaneously without reusing any vertex.
• Q2: What modeling trick handles a constraint on how much flow can pass through a vertex, rather than just through edges? Each vertex with a capacity constraint is split into two copies — an “in” copy and an “out” copy — connected by a single edge whose capacity equals that vertex’s original capacity limit; all of that vertex’s original incoming edges are redirected to the “in” copy and all outgoing edges from the “out” copy, so the standard edge-capacity machinery from Chapter 10 now also correctly enforces the vertex capacity.

Chapter 12: NP-Hardness

Difficulty: Advanced · Late Semester · Computational Complexity · Key topics: P versus NP, NP-hard/NP-easy/NP-complete, formal reductions, 3-SAT, clique, vertex cover, graph coloring, Hamiltonian cycle

The book’s final chapter turns from designing efficient algorithms to understanding the limits of what efficient algorithms can do. It introduces the P versus NP question, the formal definitions of NP-hard, NP-easy, and NP-complete, and the technique of proving a new problem NP-hard via a reduction from a problem already known to be hard, starting from 3-SAT. It then works through a long, connected chain of classic NP-hard problems — Maximum Independent Set, Clique, Vertex Cover, Graph Coloring, Hamiltonian Cycle, and Subset Sum among them — and closes with practical advice on recognizing and coping with NP-hardness in real problems, rather than searching forever for an efficient algorithm that provably cannot exist (unless P = NP).

Key Points:

• The P versus NP question asks whether every problem whose solution can be quickly verified can also be quickly solved — one of the most famous unsolved problems in all of computer science.
• NP-hard means at least as hard as every problem in NP; NP-complete means both NP-hard and itself in NP; a problem can be NP-hard without even being a yes/no decision problem in NP at all.
• A reduction proves a new problem NP-hard by showing that any instance of an already-known-hard problem (starting from 3-SAT) can be efficiently transformed into an instance of the new problem, so an efficient solver for the new problem would efficiently solve the old one too.
• A long chain of classic problems — Independent Set, Clique, Vertex Cover, Graph Coloring, Hamiltonian Cycle, Subset Sum, and others — are shown to be NP-hard, each building on a reduction from an earlier problem in the chain.
• The chapter closes practically: recognizing that a problem is NP-hard should redirect effort toward approximation, heuristics, special-case algorithms, or reformulating the problem — not toward an endless, likely-futile search for an efficient exact algorithm.

Memory Tip: Keep the direction of a reduction straight: to prove a new problem X is NP-hard, you reduce FROM a known-hard problem TO X (transform instances of the known-hard problem into instances of X) — reducing in the wrong direction proves nothing about X’s hardness.

Common Mistake: Getting the direction of a hardness reduction backwards — showing that X can be reduced to (solved using) an already-easy problem proves X is easy, while proving X is NP-hard requires reducing a known-hard problem TO X, not the other way around; mixing these up is one of the most common student errors when first learning reductions.

Important Questions:

• Q1: What does it mean to prove a problem is NP-hard using a reduction? It means showing that any instance of a problem already known to be NP-hard (ultimately tracing back to 3-SAT) can be efficiently transformed into an instance of the new problem such that solving the new instance would let you solve the original hard instance too; this shows the new problem is at least as hard as the known-hard one, since an efficient algorithm for it would give an efficient algorithm for the known-hard problem as well.
• Q2: According to the chapter’s closing advice, what should be done once a problem is confirmed to be NP-hard? Rather than continuing to search for an efficient algorithm that solves the problem exactly in the worst case (which, unless P = NP, provably cannot exist), effort should shift toward practical alternatives — approximation algorithms, heuristics that work well in practice even without a guarantee, algorithms efficient only for special restricted cases, or reformulating/relaxing the original problem into something tractable.

Read or Download Algorithms for Free

This book is free from its official source — Jeff Erickson, a professor at the University of Illinois at Urbana-Champaign, publishes the complete PDF of Algorithms directly on his own official course site, free for anyone to read or download. A separate paid print edition also exists for readers who want a physical copy, but the legitimate free way to read or download the complete book is the official page below.

How to Study This Book

Chapters 0–3 (Introduction, Recursion, Backtracking, Dynamic Programming) are the conceptual backbone of the entire book — work through them slowly and in order, since almost every later chapter assumes comfort with recursive thinking and with recognizing overlapping subproblems.

Chapter 4 (Greedy Algorithms) is deliberately placed right after Dynamic Programming so its warning lands correctly: read it as “when does the locally-best choice actually work”, not as an easier shortcut around DP.

Chapters 5–9 (graph algorithms through all-pairs shortest paths) build cumulatively — DFS and BFS from Chapters 5–6 are reused as building blocks in Chapters 7–9, so skipping ahead tends to cause confusion rather than save time.

Chapters 10–11 (maximum flow and its applications) reward being read together in one sitting each — Chapter 11 is essentially a worked demonstration of how far one algorithm (max flow) can be stretched by clever problem modeling, and that pattern is easiest to see chapter-length.

Save Chapter 12 (NP-Hardness) for after the rest of the book feels comfortable — understanding why a problem resists an efficient algorithm is much more meaningful once you’ve spent eleven chapters building efficient algorithms for problems that do have them.

Used In These Programs

This book is used as a Design and Analysis of Algorithms core or elective text, and as general reference material, in: BSCS and Programming coursework. Browse all Computer Science category books.

Who Should Read This

Algorithms is written for students taking a formal Design and Analysis of Algorithms course, typically after an introductory data structures course. It assumes comfort with basic programming and discrete math, and builds up from recursion through the standard graph, greedy, dynamic programming, and network flow algorithms every computer science curriculum expects, closing with an introduction to NP-hardness and the limits of efficient computation.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Design and Analysis of Algorithms core or elective course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners who want a free, rigorous, university-level algorithms textbook.

FAQs

Related Books

• Problem Solving with Algorithms and Data Structures using Python (a gentler, implementation-focused companion to this book’s more formal, proof-oriented treatment of algorithms)
• Data Structures in C++ – Aikman Series (foundational data structures background that pairs naturally with this book’s algorithmic content)
• Think OS – Allen B. Downey (systems-level background useful alongside this book’s algorithmic and complexity-focused material)

Algorithms by Jeff Erickson is a free, rigorous, university-level algorithms textbook — covering recursion, backtracking, dynamic programming, greedy algorithms, graph algorithms, network flow, and NP-hardness in 13 chapters, published directly by its author. Browse more Computer Science books for the rest of your semester.

Algorithms, by Jeff Erickson. Free to read online from its official source, published by the author. Licensed under CC BY 4.0. Access for free at https://jeffe.cs.illinois.edu/teaching/algorithms/