Uni Reading List
Index / 001 EN
Introduction to Algorithms cover

Computer Science

Computer Science

Introduction to Algorithms

Thomas H. Cormen et al.

A comprehensive textbook on algorithm design and analysis, covering fundamental data structures, sorting, graph algorithms, and advanced techniques with rigorous explanations and pseudocode for both theory and practice.

Difficulty Level
Advanced
Academic Level
Undergraduate
algorithm designalgorithm analysisdata structuresgraph algorithmscomputational complexitycomputer algorithms

01 / Reading Guide

Reading Guide

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. 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.
  • 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.
  • 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.

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.

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.
  • 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.

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.

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.