Algorithms (DPV)

BSCS students taking an Algorithms or Design and Analysis of Algorithms course — or anyone who wants a rigorous, proof-oriented algorithms education — can read the complete textbook “Algorithms” by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, free from its official author-hosted source. It’s an 11-chapter, university-level text that builds from number theory and divide-and-conquer through graph algorithms, greedy algorithms, dynamic programming, linear programming, NP-completeness, and finally quantum algorithms.

This edition is published directly by its authors — computer science professors at UC San Diego and UC Berkeley — and grew out of the algorithms courses they have taught for many years, covering algorithms with numbers and divide-and-conquer (Chapters 1–2), graph algorithms and shortest paths (Chapters 3–4), greedy algorithms and dynamic programming (Chapters 5–6), linear programming (Chapter 7), NP-completeness and how to cope with it (Chapters 8–9), and quantum algorithms (Chapter 10) — making it both a complete course textbook and a distinctive reference, notably one of the few standard undergraduate algorithms texts to include a chapter on quantum computing.

Book Overview

Chapter List

Chapter 0: Prologue

Difficulty: Beginner · Early Semester · Algorithms Foundations · Key topics: what is an algorithm, Fibonacci numbers, exponential vs polynomial time, algorithms as a mathematical subject

The prologue frames algorithms as a subject that is simultaneously mathematics and engineering: computing the n-th Fibonacci number is used as a first concrete case study, contrasting a naive exponential-time recursive algorithm with a simple linear-time iterative one and then, more surprisingly, a much faster algorithm based on matrix exponentiation. This single running example is used to make the book’s central point early — that correctness and efficiency are both questions that deserve careful mathematical argument, not guesswork, and that the gap between a naive and a clever algorithm for the same problem can be enormous.

Key Points:

• The naive recursive Fibonacci algorithm takes exponential time because it recomputes the same values over and over as the recursion branches.
• A simple iterative loop that just keeps a running pair of consecutive Fibonacci numbers computes the same answer in linear time.
• An even faster algorithm, based on repeated squaring of a 2×2 matrix, computes the n-th Fibonacci number in logarithmic time.
• The chapter uses this one running example to argue that algorithm design is a genuine mathematical discipline, not just clever programming.
• Big-O style asymptotic thinking (how running time scales with input size) is introduced informally here before being formalized later in the book.

Memory Tip: Keep the three Fibonacci algorithms straight by their running time class: naive recursion is exponential, the iterative loop is linear, and the matrix-power method is logarithmic — the same problem, three very different costs.

Common Mistake: Assuming that because an algorithm is correct and easy to write, it is also efficient — the naive recursive Fibonacci algorithm is completely correct but so slow that it becomes unusable for even moderately large inputs, which is exactly the point the prologue is making.

Important Questions:

• Q1: Why is the naive recursive algorithm for computing Fibonacci numbers so much slower than the iterative version, even though both are correct? The naive recursive algorithm recomputes the same Fibonacci values repeatedly as its recursive calls branch out, so the total number of calls grows exponentially with n; the iterative version instead keeps a running pair of the two most recently computed values and updates them in a single pass, doing a constant amount of work per step for a total of linear time.
• Q2: What point is the prologue making by introducing a third, matrix-based algorithm for the same Fibonacci problem? It shows that even after finding one efficient (linear-time) solution to a problem, a genuinely different algorithmic idea — here, repeated squaring of a 2×2 matrix — can do dramatically better still (logarithmic time), establishing early that algorithm design is an open-ended mathematical search for the best approach, not a search that stops at the first working idea.

Chapter 1: Algorithms with Numbers

Difficulty: Beginner · Early Semester · Algorithms Foundations · Key topics: modular arithmetic, Euclid’s algorithm, modular exponentiation, primality testing, RSA cryptography

This chapter treats basic number-theoretic algorithms as first-class algorithmic problems in their own right, not just arithmetic. It develops modular arithmetic, Euclid’s algorithm for computing the greatest common divisor (and its extended version, which also finds the coefficients of Bézout’s identity), fast modular exponentiation by repeated squaring, and randomized primality testing based on Fermat’s little theorem. These pieces are then assembled into the chapter’s capstone application: the RSA public-key cryptosystem, showing how these number-theoretic algorithms directly underpin real-world secure communication.

Key Points:

• Euclid’s algorithm computes the greatest common divisor of two numbers efficiently using repeated remainder-taking, and runs in time logarithmic in the input size.
• The extended Euclidean algorithm additionally finds integer coefficients x and y such that ax + by equals the GCD of a and b, which turns out to be exactly what’s needed to compute modular inverses.
• Modular exponentiation by repeated squaring computes a^b mod n efficiently — in time proportional to the number of bits of the exponent, not the exponent’s actual value.
• Primality testing in this chapter is randomized, based on Fermat’s little theorem: a number that fails a Fermat test is certainly composite, and one that repeatedly passes is very likely prime.
• RSA encryption combines all of these tools — modular exponentiation for encrypting/decrypting, and the extended Euclidean algorithm for generating the key pair — into a working public-key cryptosystem.

Memory Tip: Remember why modular exponentiation is fast: repeated squaring computes a^(2^k) mod n in k squarings, then combines only the squarings whose bit is set in the exponent’s binary representation — logarithmic in the exponent, not linear in it.

Common Mistake: Computing a^b mod n by first computing the full value of a^b and only then reducing mod n — a^b can be astronomically large well before the final mod is applied; the correct approach reduces mod n after every multiplication step during repeated squaring, keeping every intermediate value small.

Important Questions:

• Q1: What does the extended Euclidean algorithm compute beyond the plain GCD, and why does RSA need it? Beyond just computing gcd(a, b), the extended Euclidean algorithm also finds integers x and y satisfying ax + by = gcd(a, b); RSA needs exactly this to compute the modular multiplicative inverse of the public exponent modulo the totient of n, which is required to derive the private decryption exponent during key generation.
• Q2: Why is the primality test in this chapter described as randomized rather than a guaranteed proof of primality? It relies on Fermat’s little theorem: if a number fails the Fermat test for some base, it is certainly composite, but a number that passes the test for one or several randomly chosen bases is only very likely (not certainly) prime, since rare composite numbers can still pass the test for some bases — repeating the test with several random bases drives the probability of error down but never to exactly zero.

Chapter 2: Divide-and-Conquer Algorithms

Difficulty: Beginner · Early Semester · Algorithms Foundations · Key topics: Karatsuba multiplication, recurrence relations, mergesort, median finding, matrix multiplication, fast Fourier transform

This chapter establishes divide-and-conquer as a general algorithm-design strategy and gives the tools to analyze it: recurrence relations and the master theorem for solving them. Karatsuba’s algorithm for multiplying large numbers faster than the grade-school method opens the chapter as a surprising, motivating example, followed by mergesort and a linear-time algorithm for finding the median (and more generally the k-th smallest element) of an unsorted array. The chapter closes with two more advanced applications of the same divide-and-conquer idea: Strassen’s algorithm for faster matrix multiplication, and the fast Fourier transform for efficient polynomial multiplication.

Key Points:

• Divide-and-conquer algorithms split a problem into smaller subproblems of the same type, solve them recursively, and combine their results — the same overall pattern reused across every example in this chapter.
• Karatsuba’s algorithm multiplies two n-digit numbers using roughly n^1.59 single-digit operations instead of the grade-school method’s n^2, by cleverly reducing four recursive multiplications to three.
• The master theorem gives a direct formula for solving common recurrence relations of the form T(n) = aT(n/b) + f(n), which is the standard tool for analyzing divide-and-conquer running times throughout the book.
• A linear-time selection algorithm finds the median (or any k-th smallest element) of an unsorted array without fully sorting it, using a clever “median of medians” pivot-choosing strategy.
• Strassen’s algorithm multiplies two matrices in less than the naive O(n^3) time by reducing eight recursive submatrix multiplications to seven, and the fast Fourier transform multiplies polynomials (and large integers) in O(n log n) time using a divide-and-conquer approach in the frequency domain.

Memory Tip: When you see a recurrence of the form T(n) = aT(n/b) + f(n), reach for the master theorem immediately — comparing f(n) against n^(log_b a) tells you which of the three standard cases applies without having to expand the recursion tree by hand.

Common Mistake: Assuming any algorithm that recursively splits a problem in half is automatically fast — the actual running time depends critically on both how many subproblems are created and how much non-recursive work is done combining them at each level, which is exactly what the master theorem’s three cases distinguish between.

Important Questions:

• Q1: What is the key trick behind Karatsuba’s algorithm that makes it faster than grade-school multiplication? Grade-school multiplication of two n-digit numbers naively requires four recursive multiplications of n/2-digit halves; Karatsuba’s algorithm reformulates the arithmetic so that only three recursive multiplications are needed instead of four (at the cost of a few extra additions and subtractions), which changes the recurrence’s solution from O(n^2) down to roughly O(n^1.59).
• Q2: Why does the linear-time selection algorithm need a careful “median of medians” strategy for choosing its pivot, rather than picking a pivot arbitrarily? Picking a pivot arbitrarily (such as always the first or last element) can lead to very unbalanced splits on some inputs, degrading the algorithm’s running time to quadratic in the worst case; the median-of-medians strategy guarantees the chosen pivot is never too close to the extreme ends of the data, which guarantees a sufficiently balanced split at every level of recursion and keeps the overall running time linear even in the worst case.

Chapter 3: Decompositions of Graphs

Difficulty: Beginner · Mid Semester · Graph Algorithms · Key topics: graph representations, depth-first search, connected components, directed graphs, topological sort, strongly connected components

This chapter introduces graphs as a data structure and depth-first search (DFS) as the fundamental algorithm for exploring them, then shows how the same basic traversal reveals very different structural information depending on whether the graph is undirected or directed. In undirected graphs, DFS finds connected components directly. In directed graphs, DFS is extended to detect cycles and produce a topological ordering of a directed acyclic graph, and finally to decompose any directed graph into its strongly connected components — maximal groups of vertices that can all reach each other.

Key Points:

• Depth-first search explores a graph by going as deep as possible along each branch before backtracking, and can be implemented either recursively or with an explicit stack.
• In an undirected graph, running DFS from unvisited vertices one at a time directly partitions the graph into its connected components.
• In a directed graph, DFS can detect cycles by checking for back edges (edges to a vertex still on the current recursion path), and produces a topological ordering of a directed acyclic graph via reverse postorder.
• Every directed graph can be decomposed into strongly connected components — maximal sets of vertices where every vertex can reach every other vertex in the same set — computable in linear time using two passes of DFS.
• The “metagraph” formed by contracting each strongly connected component into a single vertex is always a directed acyclic graph, giving a clean higher-level structural summary of any directed graph.

Memory Tip: Remember DFS’s dual role by graph type: on an undirected graph it finds connected components; on a directed graph the same traversal, with attention to edge types, finds cycles, topological order, and (with a second pass) strongly connected components.

Common Mistake: Confusing an undirected graph’s connected components with a directed graph’s strongly connected components — the undirected notion only requires some path between two vertices in either direction, while the directed notion requires each vertex to be able to reach the other and be reached by it, which is a strictly stronger condition that can split what looks like one connected piece into several strongly connected components.

Important Questions:

• Q1: How does depth-first search determine the connected components of an undirected graph? By repeatedly starting a new DFS from any vertex that hasn’t been visited yet, and marking every vertex reached during that particular DFS run as belonging to the same connected component; once a DFS run finishes, the next unvisited vertex (if any) starts a new component, so each full pass through the graph’s vertices assigns every vertex to exactly one connected component.
• Q2: Why does contracting each strongly connected component of a directed graph into a single vertex always produce a directed acyclic graph? If the resulting “metagraph” contained a cycle among the contracted components, then every component on that cycle could reach every other component on it by following the cycle, which would mean all of those vertices could actually reach each other and should have been merged into one single, larger strongly connected component in the first place — so by the very definition of strongly connected components being maximal, no such cycle can remain in the metagraph.

Chapter 4: Paths in Graphs

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: breadth-first search, shortest paths in DAGs, Dijkstra’s algorithm, priority queues, Bellman-Ford algorithm

Having covered graph traversal and structure in the previous chapter, this chapter tackles the shortest-path problem across a sequence of progressively more general settings. It starts with breadth-first search for unweighted graphs, then shortest paths in directed acyclic graphs via a single linear-time pass in topological order. Dijkstra’s algorithm is then developed in depth for general graphs with non-negative edge weights, including a careful discussion of priority-queue implementations and their effect on running time, before the chapter closes with the Bellman-Ford algorithm for graphs that may contain negative edge weights.

Key Points:

• Breadth-first search computes shortest paths correctly in unweighted graphs by exploring vertices in order of increasing distance from the source, using a queue.
• Shortest paths in a directed acyclic graph can be computed in linear time with a single pass in topological order, without needing Dijkstra’s or Bellman-Ford’s extra machinery.
• Dijkstra’s algorithm greedily finalizes the closest not-yet-finalized vertex at each step and is correct only when all edge weights are non-negative; its running time depends heavily on the priority-queue implementation used to find that closest vertex efficiently.
• A binary-heap-based priority queue is the standard practical choice for implementing Dijkstra’s algorithm, giving an overall running time of O((|V| + |E|) log |V|).
• The Bellman-Ford algorithm handles negative edge weights correctly (and can detect negative cycles) by repeatedly relaxing all edges up to |V| – 1 times, trading Dijkstra’s greedy speed for broader correctness.

Common Mistake: Running Dijkstra’s algorithm on a graph with negative edge weights is a classic mistake — its correctness proof depends entirely on the assumption that a finalized vertex’s shortest distance can never later improve, and a negative edge encountered later can violate exactly that assumption.

Common Mistake: Choosing an inefficient priority-queue implementation (such as a plain unsorted array) for Dijkstra’s algorithm without considering the trade-off — the choice of priority-queue data structure directly determines the algorithm’s overall running time, and a binary heap or more advanced structure is usually necessary to get the efficient running time the algorithm is known for.

Important Questions:

• Q1: Why is a single linear-time pass sufficient to compute shortest paths in a directed acyclic graph, without needing Dijkstra’s algorithm? Because a DAG’s topological order guarantees that, by the time any vertex is processed, all of its predecessors (and therefore the shortest distances to reach it) have already been finalized; processing vertices in topological order and relaxing each vertex’s outgoing edges exactly once is therefore already sufficient to compute correct shortest distances, without any need for Dijkstra’s repeated “find the closest remaining vertex” step.
• Q2: How does the choice of priority-queue implementation affect Dijkstra’s algorithm’s running time? Dijkstra’s algorithm repeatedly needs to find and remove the not-yet-finalized vertex with the smallest tentative distance, which is exactly what a priority queue provides; using a simple unsorted array for this gives O(|V|) time per extraction and an overall O(|V|^2) running time, while using a binary heap reduces extraction (and the needed decrease-key updates) to O(log |V|) time each, giving the much better overall O((|V| + |E|) log |V|) running time typically quoted for Dijkstra’s algorithm.

Chapter 5: Greedy Algorithms

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: minimum spanning trees, Kruskal’s and Prim’s algorithms, Huffman encoding, Horn formulas, set cover

This chapter develops greedy algorithms through two of the field’s cleanest worked examples: minimum spanning trees and Huffman encoding. Kruskal’s and Prim’s algorithms are both presented as correct greedy strategies for the minimum spanning tree problem, backed by a shared cut-property argument, with the union-find data structure introduced as the efficient way to implement Kruskal’s algorithm’s cycle checks. Huffman encoding is then developed as a second, structurally different greedy algorithm for building optimal prefix-free codes. The chapter closes with two further greedy applications: solving Horn formulas and approximating set cover.

Key Points:

• Both Kruskal’s algorithm (globally cheapest edge first, skipping ones that create a cycle) and Prim’s algorithm (growing a single tree by its cheapest available edge) are correct greedy strategies for finding a minimum spanning tree, both justified by the same underlying cut property.
• The union-find (disjoint-set) data structure lets Kruskal’s algorithm efficiently check whether adding an edge would create a cycle, which is essential to the algorithm’s practical efficiency.
• Huffman encoding builds an optimal prefix-free binary code by repeatedly and greedily merging the two least-frequent symbols or subtrees, guaranteeing frequent symbols end up with shorter codes.
• Horn formulas (a restricted, practically important class of boolean formulas) can be satisfied, when possible, by a greedy algorithm that sets variables to false by default and only to true when forced by an implication.
• The set cover problem is NP-hard in general, but a simple greedy algorithm that always picks the set covering the most currently-uncovered elements gives a provably good (logarithmic-factor) approximation.

Memory Tip: Keep Kruskal’s and Prim’s algorithms straight by what they’re greedy about: Kruskal considers all edges globally, cheapest first, using union-find to avoid cycles; Prim grows one tree outward, always adding that tree’s single cheapest available edge next.

Common Mistake: Assuming greedy algorithms are always correct simply because they “make sense” intuitively — this chapter’s own examples (MST and Huffman encoding) are correct greedy algorithms with real proofs behind them, but the book is equally clear elsewhere that many superficially similar greedy strategies on other problems are provably wrong, so correctness always requires an actual proof, not just intuition.

Important Questions:

• Q1: What data structure makes Kruskal’s algorithm efficient, and what problem does it solve for the algorithm? The union-find (disjoint-set) data structure is used to efficiently track which vertices currently belong to the same growing tree component; before adding each candidate edge, Kruskal’s algorithm uses union-find to check in nearly constant time whether the edge’s two endpoints are already in the same component (which would create a cycle) and, if not, merges their components after adding the edge.
• Q2: How does the greedy algorithm for set cover work, and in what sense is it only an approximation rather than an exact solution? The greedy set cover algorithm repeatedly selects whichever available set covers the largest number of elements not yet covered by any previously selected set, continuing until every element is covered; because set cover is NP-hard in general, this greedy approach is not guaranteed to find the fewest possible sets, but it is provably guaranteed to use no more than a logarithmic factor more sets than the true optimal solution, which is a strong and useful approximation guarantee even though it is not exact.

Chapter 6: Dynamic Programming

Difficulty: Intermediate · Mid Semester · Algorithms Foundations · Key topics: shortest paths as DP, longest increasing subsequence, edit distance, knapsack, chain matrix multiplication, independent sets in trees

This chapter develops dynamic programming as a general technique for problems built from overlapping subproblems, opening by re-deriving shortest-path algorithms as dynamic programs to connect back to earlier chapters. It then works through several of the field’s classic DP problems in sequence: longest increasing subsequence, edit distance between two strings, the knapsack problem (in both its 0/1 and unbounded forms), chain matrix multiplication (finding the cheapest order to multiply a chain of matrices), and independent sets in trees, each illustrating how to identify the right subproblems and the recurrence connecting them.

Key Points:

• Dynamic programming solves a problem by breaking it into overlapping subproblems, solving each distinct subproblem exactly once, and storing (memoizing or tabulating) its answer for reuse.
• Longest increasing subsequence and edit distance are developed as classic single- and two-dimensional dynamic programming examples, each building a table indexed by subproblem parameters.
• The knapsack problem is presented in both its 0/1 form (each item taken entirely or not at all) and unbounded form (unlimited copies of each item allowed), showing how a small change in problem statement changes the DP table’s structure.
• Chain matrix multiplication finds the cheapest way to parenthesize a chain of matrix multiplications, illustrating dynamic programming over subranges of a sequence rather than just prefixes.
• Independent sets in trees extends dynamic programming to tree-structured inputs, computing subproblem answers bottom-up from the leaves toward the root.

Memory Tip: When starting a new dynamic programming problem, explicitly write down three things first: what a subproblem is (in words, not just an index), what the recurrence relating a subproblem to smaller ones is, and what order to fill the table in so every needed smaller subproblem is already known.

Common Mistake: Writing a recursive solution and adding memoization without first correctly identifying what the subproblems actually are — a table indexed by the wrong parameters, or one that doesn’t capture enough state to distinguish genuinely different subproblems, will silently produce wrong answers even though the code runs without errors.

Important Questions:

• Q1: What is the key structural difference between the 0/1 knapsack problem and the unbounded knapsack problem, and how does it change the dynamic program? In the 0/1 knapsack problem each item can be taken at most once, so the DP table must track, for each item, whether it has already been used in the current subproblem, typically requiring a table indexed by both item index and remaining capacity; in the unbounded knapsack problem any item can be reused an unlimited number of times, which actually simplifies the table to be indexed only by remaining capacity, since there’s no need to track which specific items have already been used.
• Q2: How does dynamic programming for chain matrix multiplication differ from the earlier dynamic programming examples in this chapter that work over prefixes of a sequence? Chain matrix multiplication requires considering the cost of multiplying every possible contiguous subrange of matrices in the chain, not just prefixes, so its subproblems are indexed by a pair (i, j) representing a subrange from matrix i to matrix j rather than by a single index; the table is filled in order of increasing subrange length, combining the best way to split each subrange at every possible point, rather than filling in order of a single growing prefix.

Chapter 7: Linear Programming and Reductions

Difficulty: Advanced · Mid-Late Semester · Optimization · Key topics: linear programming formulation, the simplex algorithm, duality, reductions to shortest paths and max-flow, zero-sum games

This chapter introduces linear programming as a remarkably general framework that many of the book’s earlier problems — shortest paths, maximum flow, bipartite matching — turn out to be special cases of. It covers how to formulate a problem as a linear program (an objective function to optimize subject to linear constraints), the geometric intuition and mechanics of the simplex algorithm for solving one, and the theory of duality, which pairs every linear program with a related “dual” program whose optimal value always matches the original. The chapter closes by showing how reductions connect linear programming to earlier graph problems and to zero-sum game theory.

Key Points:

• A linear program consists of a linear objective function to maximize or minimize, subject to a system of linear inequality and equality constraints — a surprisingly general modeling framework.
• The simplex algorithm solves linear programs by moving from vertex to vertex along the boundary of the feasible region defined by the constraints, always improving the objective, until no further improvement is possible.
• Duality theory pairs every linear program (the “primal”) with a related “dual” linear program, and the strong duality theorem guarantees their optimal objective values are always exactly equal.
• Several earlier problems in the book — shortest paths, maximum flow, and bipartite matching among them — can be formulated as special cases of linear programming, showing the framework’s unifying reach.
• Zero-sum games can be solved using linear programming, connecting the chapter’s optimization machinery to game theory and giving a concrete, non-graph-theoretic application of duality.

Practice Tip: When trying to recognize whether a new problem can be formulated as a linear program, check whether its objective and every constraint can be written using only linear combinations of the decision variables — no products of variables, no absolute values, and no either/or conditions without further reformulation.

Common Mistake: Assuming the simplex algorithm’s practical speed on typical inputs means it has polynomial worst-case running time — the chapter is explicit that simplex can take exponential time in the worst case on adversarially constructed inputs, even though it performs efficiently on essentially all inputs encountered in practice, which is why other polynomial-time algorithms for linear programming (interior-point methods) also matter theoretically.

Important Questions:

• Q1: What does the strong duality theorem guarantee about a linear program and its dual? It guarantees that if a linear program (the primal) has an optimal solution, its corresponding dual linear program also has an optimal solution, and the two optimal objective values are always exactly equal — not merely that one bounds the other, giving a powerful way to certify that a candidate solution to the primal is truly optimal by exhibiting a dual solution with a matching objective value.
• Q2: In what sense are shortest paths and maximum flow shown to be special cases of linear programming in this chapter? Both problems can be formulated directly as linear programs: shortest paths as minimizing a path-length objective subject to constraints capturing valid distances along edges, and maximum flow as maximizing total flow out of the source subject to capacity and flow-conservation constraints at every vertex; this shows that the specialized graph algorithms developed in earlier chapters are, in a precise sense, solving particular structured instances of the same general linear programming problem.

Chapter 8: NP-Complete Problems

Difficulty: Advanced · Late Semester · Computational Complexity · Key topics: P versus NP, satisfiability, reductions, NP-completeness proofs, graph problems, the Cook-Levin theorem

This chapter turns from designing algorithms to understanding computational hardness, introducing the classes P and NP and the central open question of whether they are equal. It develops the technique of polynomial-time reductions as the tool for comparing problems’ difficulty, starting from the boolean satisfiability problem (SAT) and its restricted form 3-SAT, whose NP-hardness traces back to the Cook-Levin theorem. From this starting point, the chapter builds a chain of reductions establishing the NP-completeness of a range of classic graph and combinatorial problems, including independent set, vertex cover, and clique.

Key Points:

• The class P contains problems solvable in polynomial time; the class NP contains problems whose proposed solutions can be verified in polynomial time — whether P equals NP is one of the most famous open questions in computer science.
• A polynomial-time reduction from problem A to problem B shows that A is no harder than B, since an efficient algorithm for B could be used, together with the reduction, to efficiently solve A.
• The Cook-Levin theorem establishes that satisfiability (SAT) is NP-complete, giving the very first problem known to be NP-complete and the starting point for proving other problems NP-complete via reduction.
• 3-SAT, a restricted version of SAT where every clause has exactly three literals, is shown to remain NP-complete, and serves as the practical starting point for most later reductions in the chapter.
• A chain of reductions from 3-SAT establishes NP-completeness for independent set, then from independent set for vertex cover and clique, illustrating how NP-completeness results build on each other rather than needing to be proven from scratch each time.

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

Common Mistake: Treating “NP” as meaning “not solvable in polynomial time” — NP actually means solutions can be verified in polynomial time, and every problem in P is also in NP, since anything solvable quickly can certainly also be checked quickly; confusing NP with problems known to be hard is one of the most common misunderstandings when first learning this material.

Important Questions:

• Q1: What does the Cook-Levin theorem establish, and why is it historically significant? The Cook-Levin theorem establishes that the boolean satisfiability problem (SAT) is NP-complete — that is, every problem in NP can be reduced to it in polynomial time; it is historically significant because it provided the very first known NP-complete problem, which then made it possible to prove other problems NP-complete simply by reducing SAT (or a problem already shown NP-complete) to them, rather than having to argue NP-hardness from first principles for every new problem.
• Q2: How does proving vertex cover is NP-complete typically build on the earlier NP-completeness result for independent set in this chapter’s chain of reductions? Independent set and vertex cover are shown to be complementary on the same graph — a set of vertices is an independent set if and only if the remaining vertices form a vertex cover — so a polynomial-time reduction from independent set to vertex cover follows almost immediately from this relationship, letting the chapter reuse the hardness already established for independent set (itself reduced from 3-SAT) rather than proving vertex cover’s hardness independently from scratch.

Chapter 9: Coping with NP-Completeness

Difficulty: Advanced · Late Semester · Computational Complexity · Key topics: approximation algorithms, vertex cover and TSP approximations, local search, backtracking, branch-and-bound

Rather than continuing to prove more problems NP-hard, this chapter turns practical: given that a problem is confirmed NP-hard, what can actually be done about it? It covers approximation algorithms with provable guarantees, worked through concretely on vertex cover and the traveling salesman problem, local search heuristics that improve a candidate solution step by step without worst-case guarantees, and exact but exponential-time techniques — backtracking and branch-and-bound — that remain useful in practice by pruning large parts of the search space long before it is fully explored.

Key Points:

• Approximation algorithms trade exactness for guaranteed efficiency, providing a solution provably within some bounded factor of optimal, even though the problem itself is NP-hard.
• A simple 2-approximation algorithm for vertex cover repeatedly picks an uncovered edge and adds both its endpoints to the cover, guaranteeing a cover at most twice the size of the true minimum.
• For metric instances of the traveling salesman problem (where edge weights satisfy the triangle inequality), a minimum-spanning-tree-based approximation algorithm guarantees a tour no worse than twice the optimal length.
• Local search heuristics start from some candidate solution and repeatedly make small improving changes, offering no worst-case guarantee but often performing very well in practice on real instances.
• Backtracking and branch-and-bound remain exact, exponential-time-in-the-worst-case techniques, but aggressively prune large parts of the search space using bounds and partial-solution checks, often making them practical on real NP-hard instances of moderate size.

Practice Tip: When faced with a confirmed NP-hard problem in practice, ask three questions in order: is a provable approximation algorithm known for it, would a local search heuristic likely perform well on realistic inputs, and is the actual instance size small enough for pruned exact search (backtracking/branch-and-bound) to finish in reasonable time?

Common Mistake: Giving up on an NP-hard problem entirely, or conversely insisting on an exact exponential-time algorithm regardless of instance size — this chapter’s whole point is that NP-hardness rules out a guaranteed efficient exact algorithm, not practical progress altogether; approximation algorithms, local search, and pruned exact search are all genuinely useful responses depending on the problem and the required guarantee.

Important Questions:

• Q1: How does the simple approximation algorithm for vertex cover work, and what guarantee does it provide? The algorithm repeatedly picks any edge that is not yet covered by the vertices selected so far, adds both of that edge’s endpoints to the cover (even though only one might technically be needed), and removes all edges now covered by those two vertices, repeating until no uncovered edges remain; this guarantees the resulting cover is at most twice the size of the true minimum vertex cover, because every selected pair of vertices corresponds to a distinct edge, and any valid vertex cover must include at least one endpoint from each of those distinct edges.
• Q2: What is the key structural difference between an approximation algorithm and a local search heuristic, as presented in this chapter? An approximation algorithm comes with a proven mathematical guarantee bounding how far its output can be from the true optimal solution in the worst case, even though it runs in polynomial time on an NP-hard problem; a local search heuristic instead starts from some initial candidate solution and repeatedly applies small improving changes until no improvement is found, and while it often performs very well in practice, it provides no such worst-case guarantee and can get stuck in a solution that is only locally, not globally, good.

Chapter 10: Quantum Algorithms

Difficulty: Advanced · Late Semester · Computational Complexity · Key topics: qubits and superposition, quantum circuits, Simon’s algorithm, Shor’s factoring algorithm

The book’s final chapter steps outside classical computation entirely, introducing the basic mathematical model of quantum computation — qubits, superposition, and quantum gates arranged into circuits — as a genuinely different computational model rather than just a faster classical computer. Simon’s algorithm is developed as an accessible first example of a problem where a quantum algorithm provably outperforms any classical algorithm, building the intuition needed for the chapter’s centerpiece: Shor’s algorithm, which factors large integers in polynomial time on a quantum computer, a task with no known polynomial-time classical algorithm and one whose presumed hardness underlies cryptosystems like RSA from Chapter 1.

Key Points:

• A qubit generalizes a classical bit by existing in a superposition of the states 0 and 1 simultaneously, with quantum measurement collapsing that superposition probabilistically into a definite classical outcome.
• Quantum circuits are built from quantum gates acting on qubits, and are the standard model used to describe quantum algorithms precisely, analogous to classical logic circuits.
• Simon’s algorithm solves a specific structured problem exponentially faster on a quantum computer than any known classical algorithm can, giving an early, relatively simple proof-of-concept for genuine quantum speedup.
• Shor’s algorithm factors large integers in polynomial time on a quantum computer by reducing factoring to finding the period of a certain function, which a quantum computer can do efficiently using the quantum Fourier transform.
• Because RSA’s security (Chapter 1) depends on factoring being hard for classical computers, Shor’s algorithm directly threatens RSA’s security if a sufficiently large quantum computer is ever built, tying the book’s opening and closing chapters together.

Memory Tip: Connect this chapter back to Chapter 1 explicitly: RSA’s security rests on the assumption that factoring large integers is hard for classical computers, and Shor’s algorithm in this chapter is precisely what threatens that assumption on a quantum computer.

Common Mistake: Thinking of a quantum computer as simply a faster classical computer that tries every possibility “in parallel” — superposition alone does not give useful speedup; a quantum algorithm’s power comes from carefully engineered interference between amplitudes that cancels out wrong answers and reinforces correct ones, which is exactly the structure Simon’s and Shor’s algorithms are built around.

Important Questions:

• Q1: What does Simon’s algorithm demonstrate that makes it an important first example in this chapter? It demonstrates a concrete computational problem, with a specific hidden structural property, that a quantum algorithm can solve exponentially faster than any known classical algorithm; this makes it valuable as a relatively accessible, rigorously provable early example of genuine quantum speedup, building the intuition (about superposition and interference) needed before tackling the more consequential but more involved Shor’s algorithm later in the chapter.
• Q2: Why does Shor’s algorithm matter beyond being a fast factoring algorithm, in the specific context of this book? Because Chapter 1’s RSA cryptosystem relies entirely on the assumption that factoring large integers is computationally hard for classical computers, and Shor’s algorithm shows that a sufficiently powerful quantum computer could factor those same integers in polynomial time; this means Shor’s algorithm is not just a mathematical curiosity but a direct, concrete threat to the practical security of RSA and related cryptosystems if large-scale quantum computers become available.

Read or Download Algorithms (DPV) for Free

This book is free from its official source — Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the three authors, publish the complete book as chapter-by-chapter PDFs directly on their own university pages, free for anyone to read or download. A separate commercial print edition (published by McGraw-Hill) also exists for readers who want a physical copy, but the legitimate free way to read or download the book is the official author page below.

How to Study This Book

Chapters 0–2 (Prologue, Algorithms with Numbers, Divide-and-Conquer) set the mathematical tone for the whole book — work through the Fibonacci and RSA examples by hand at least once, since the habit of reasoning carefully about correctness and running time carries through every later chapter.

Chapters 3–4 (Decompositions of Graphs, Paths in Graphs) build the graph-traversal and shortest-path foundation that Chapter 5’s minimum spanning tree material and later chapters assume — make sure DFS, BFS, and Dijkstra’s algorithm feel comfortable before moving on.

Chapters 5–6 (Greedy Algorithms, Dynamic Programming) are deliberately placed back to back — for every problem, ask explicitly why a greedy approach does or doesn’t work, and what changes when the same-looking problem instead needs a full dynamic-programming recurrence.

Chapter 7 (Linear Programming and Reductions) rewards being read after Chapters 4–6, since it explicitly reframes shortest paths, max-flow, and other earlier problems as special cases of one unifying optimization framework — the reductions make much more sense once the original problems are familiar.

Save Chapters 8–10 (NP-Complete Problems, Coping with NP-Completeness, Quantum Algorithms) for after the rest of the book feels solid — understanding computational hardness, and what quantum computing changes about it, is far more meaningful once you’ve spent nine chapters building efficient algorithms for problems that do have them.

Used In These Programs

This book is used as an Algorithms / 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 by Dasgupta, Papadimitriou, and Vazirani is written for students taking a formal Algorithms or Design and Analysis of Algorithms course, typically after an introductory data structures course. It assumes comfort with basic programming, discrete math, and mathematical proof, and builds up from number-theoretic and divide-and-conquer algorithms through the standard graph, greedy, dynamic programming, and linear programming algorithms every computer science curriculum expects, closing with NP-completeness and an introduction to quantum algorithms.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with an Algorithms or 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 Dasgupta, Papadimitriou, and Vazirani is a free, rigorous, university-level algorithms textbook — covering number-theoretic algorithms, divide-and-conquer, graph algorithms, greedy algorithms, dynamic programming, linear programming, NP-completeness, and quantum algorithms in 11 chapters, published directly by its authors. Browse more Computer Science books for the rest of your semester.

Algorithms, by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Free to read online from its official author-hosted source. Access for free at https://people.eecs.berkeley.edu/~vazirani/algorithms.html