Introduction to Algorithms

Citation

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). The MIT Press.

Chapter Summary

The fourth edition has 35 chapters in seven parts, followed by a mathematical-background appendix, and runs to about 1,300 pages (MIT Press lists the hardcover, published in 2022, at 1,312 pages). Each part opens with a short introduction.

Part I, Chapters 1–5: Foundations

Chapter 1, The Role of Algorithms in Computing, and Chapter 2, Getting Started, introduce algorithms and their analysis. Chapter 3, Characterizing Running Times, covers asymptotic notation; Chapter 4, Divide-and-Conquer, is one of the longest in the part; and Chapter 5, Probabilistic Analysis and Randomized Algorithms, prepares the ground for randomized methods used later.

Part II, Chapters 6–9: Sorting and Order Statistics

Heapsort, Quicksort, Sorting in Linear Time, and Medians and Order Statistics. Together they cover comparison sorting, non-comparison sorting and selection.

Part III, Chapters 10–13: Data Structures

Elementary Data Structures, Hash Tables, Binary Search Trees and Red-Black Trees. Hash tables get a chapter of roughly forty pages, and the edition lists new material on hash tables among its changes.

Part IV, Chapters 14–16: Advanced Design and Analysis Techniques

Dynamic Programming, Greedy Algorithms and Amortized Analysis. Dynamic programming is one of the longer chapters in the book (about 55 pages). The part introduces two main design strategies for optimization problems and the main tool for analyzing sequences of operations.

Part V, Chapters 17–19: Advanced Data Structures

Augmenting Data Structures, B-Trees and Data Structures for Disjoint Sets.

Part VI, Chapters 20–25: Graph Algorithms

Elementary Graph Algorithms, Minimum Spanning Trees, Single-Source Shortest Paths, All-Pairs Shortest Paths, Maximum Flow, and Matchings in Bipartite Graphs. The last chapter is new in this edition.

Part VII, Chapters 26–35: Selected Topics

Parallel Algorithms, Online Algorithms, Matrix Operations, Linear Programming, Polynomials and the FFT, Number-Theoretic Algorithms, String Matching, Machine-Learning Algorithms, NP-Completeness and Approximation Algorithms. Online algorithms and machine-learning algorithms are new chapters in this edition. NP-Completeness and Approximation Algorithms close the part.

Appendix: Mathematical Background

Summations, Sets, Etc., Counting and Probability, and Matrices (Appendices A–D), followed by the bibliography and index.

Key Concepts

Chapters 1–5

• Asymptotic notation and running times: a vocabulary for comparing algorithms independent of machines, developed in Chapter 3.
• Divide-and-conquer and recurrences: Chapter 4 treats recursive design together with ways of solving the resulting recurrence equations. MIT Press lists new material on recurrence equations among the fourth edition's changes.
• Randomized algorithms: Chapter 5 introduces probabilistic analysis of algorithms.

Chapters 6–19

• Sorting bounds and selection: Chapters 6–9 distinguish comparison sorts from linear-time sorting and cover order statistics.
• Dynamic programming, greedy algorithms, amortized analysis: the three techniques of Part IV. New material on potential functions is among the edition's listed changes.
• Balanced and augmented search structures: red-black trees, B-trees and augmentation (Chapters 13, 17, 18).

Chapters 20–35

• Shortest paths, spanning trees, flow and matching: the graph chapters of Part VI.
• NP-completeness and approximation: Chapters 34 and 35 on problems believed to have no efficient exact algorithms and on approximating them.
• Selected topics: parallel and online algorithms, linear programming, the FFT, number theory, string matching and machine learning as short, self-contained chapters. The edition also lists new material on suffix arrays among its changes.

Critical Analysis

Strengths

• Rigor with breadth. The publisher describes the book as combining rigor and comprehensiveness, with self-contained chapters and algorithms written in pseudocode, so a reader can enter at many points.
• Mathematical background included. Appendices A–D cover summations, sets, counting and probability, and matrices, so most prerequisites can be reviewed in the book itself.
• Exercises and problems. The fourth edition adds 140 new exercises and 22 new problems and improves earlier problems in response to reader feedback.
• Currency. The edition adds chapters on matchings in bipartite graphs, online algorithms and machine learning, and new material on recurrences, hash tables, potential functions and suffix arrays.
• Revised presentation. According to MIT Press, the fourth edition adds color and revises the writing to be clearer, more personal and gender neutral.
• A long teaching track record. Courses across decades keep assigning it, from the Fall 2024 Johns Hopkins course and the fourth-edition UC Denver course to archived MIT, Stanford and Berkeley syllabi (see Common course assignments below). Most use the book modularly, assigning selected chapters rather than the whole book. Watch editions: the second edition appeared in 2001, the third in 2009, and the fourth in 2022, so a 2005 course used the second edition, not the third.

Limitations

• Sheer size. At 35 chapters and more than a thousand pages, it is a reference as much as a course text; no single course covers all of it, and the reader has to choose. None of the syllabi listed below assigns the whole book; the Stanford CS 161 list, for example, assigns individual sections rather than entire parts.
• Pseudocode only. Since the algorithms are given as pseudocode, readers who want working programs must write their own implementations.
• Selected topics are brief. Subjects such as linear programming (about 27 pages) and machine learning (about 39 pages) each receive a single chapter and work as introductions, not full treatments.
• Demanding for beginners. The mathematical style and length make it a demanding first exposure to algorithms; it works better alongside lectures or as a second pass.
• Edition mismatches in course materials. Several freely available syllabi, including the Stanford and MIT lists below, are keyed to the third or second edition. The fourth edition renumbers some chapters, notably in the graph part, and adds new ones, so reading lists do not transfer directly.

Where It Fits in the Course

In the algorithms course, this is the comprehensive reference. Cormen's own Algorithms Unlocked is a short introduction to how algorithms work, written for readers who are not yet ready for this book, and Roughgarden's Algorithms Illuminated presents the standard paradigms in a conversational style with video lectures. Either is a good first pass. Skiena's The Algorithm Design Manual is a practical guide to recognizing problems and choosing designs, with a catalogue of problems, and pairs well with this book when the aim is implementation.

Kleinberg and Tardos's Algorithm Design is listed as an alternative text on the Stanford CS 161 syllabus below.

For specialist follow-ups, Chapter 35 of this book is a short introduction to approximation, which Vazirani's Approximation Algorithms and Williamson and Shmoys's The Design of Approximation Algorithms develop in full. Probability and Computing by Mitzenmacher et al. extends the randomized material that begins in Chapter 5.

How to Use This Book

The book suits upper-level undergraduates and graduate students, and it also serves as a long-term reference. Comfort with proofs, summations and basic probability is helpful, and Appendices A–D can be used to refresh them.

A typical first course reads Parts I and II, then selected chapters from Parts III and IV (hash tables, binary search trees, dynamic programming, greedy algorithms), then the elementary graph algorithms, spanning trees and shortest paths of Part VI. Amortized analysis, B-trees, maximum flow and NP-completeness are natural second-semester topics. The chapters of Part VII are mostly independent and can be read in any order as interests require.

Read each chapter with the exercises and problems. Pseudocode is best understood by tracing it by hand and then writing it in a language of choice.

Common course assignments

Published reading lists show how courses use the book selectively. Chapter numbers follow each syllabus's stated edition—they do not all match the fourth edition. The fourth edition renumbers much of the graph material (for example, elementary graph algorithms appear as Chapter 20 in fourth-edition syllabi versus Chapter 22 in third-edition ones) and adds new chapters, so map topics with MIT Press's third-to-fourth Transition Guide before copying an older list.

Recent (within about eight years):

• Johns Hopkins 601.433/633, Fall 2024 (3rd ed. required; 4th acceptable): Schedule readings span Chs. 1–9, 11–13, 15–18, 21–26, 29 and 34–35, with later lectures on online algorithms and algorithmic learning. A full undergraduate/graduate sweep from asymptotics and sorting through graphs, flow, LP, NP-completeness and approximation. (schedule)
• MIT OCW 6.006, Spring 2020 (3rd ed. as optional reference): Written materials are lecture and recitation notes; CLRS third edition is listed as a useful but not required reference. (syllabus)

Fourth-edition syllabus (term year unspecified on the page):

• UC Denver CSCI 5451 (4th ed., 2022 textbook): Chs. 1, 3–4, 6–7, 9, 12–15, 19–24, 28–29, 32, 34–35. Explicit fourth-edition numbering (elementary graphs as Ch. 20, MSTs as Ch. 21, max-flow as Ch. 24). (course page)

Older archived lists:

• Stanford CS 161, Spring 2016 (3rd ed.): Ch. 1; 2.3, 3.1; 4.3–4.5; Ch. 9; Chs. 7 and 5; 8.1–8.2; Ch. 12; Ch. 11; Ch. 22; Chs. 24 and 6; 24.3; 24.1 and 24.3; 25.2 and 15.4; Chs. 16 and 23; 26.1–26.3.
• MIT OCW 6.006, Fall 2011 (3rd ed.): Chs. 1 and 3; 2.1–2.3, 4.3–4.6; 6.1–6.4; 12.1–12.3; 8.1–8.3; 11.1–11.4; 17; 22.1–22.4; 24.; 15.; 34.1–34.3.
• MIT OCW 6.046J, Fall 2005 (2nd ed., 2001): Chs. 1–9, 11–17, 22–25. Predates the 2009 third edition; treat chapter numbers as second-edition.
• UC Berkeley CS 170, Fall 2005 (2nd ed.): Chs. 1–5, 11, 15, 16.3, 21–24, 26, 29–30, 34–35. Same caveat: second edition, not third.

Across these lists, foundations, sorting, hashing, basic graph algorithms and dynamic programming form the common core. Later "selected topics" chapters appear only in some courses.

Edition notes

MIT Press's 2022 fourth-edition hardcover is ISBN 9780262046305 (electronic editions use other identifiers). Match section titles and pseudocode to the edition you hold before following any syllabus. Use the Transition Guide above to map third-edition readings onto fourth-edition chapter numbers rather than guessing from titles.