Solutions
by Thomas H. Cormen
to Accompany
Introduction to Algorithms
Fourth Edition
by Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
The MIT Press
Cambridge, Massachusetts London, England
,Instructor’s Manual to Accompany Introduction to Algorithms, Fourth Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Published by the MIT Press. Copyright © 2022 by The Massachusetts Institute of Technology. All rights reserved.
No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database
or retrieval system, without the prior written consent of The MIT Press, including, but not limited to, network or
other electronic storage or transmission, or broadcast for distance learning.
,Contents
Revision History R-1
Preface P-1
Chapter 2: Getting Started
Solutions 2-1
Chapter 3: Characterizing Running Times
Solutions 3-1
Chapter 4: Divide-and-Conquer
Solutions 4-1
Chapter 5: Probabilistic Analysis and Randomized Algorithms
Solutions 5-1
Chapter 6: Heapsort
Solutions 6-1
Chapter 7: Quicksort
Solutions 7-1
Chapter 8: Sorting in Linear Time
Solutions 8-1
Chapter 9: Medians and Order Statistics
Solutions 9-1
Chapter 10: Elementary Data Structures
Solutions 10-1
Chapter 11: Hash Tables
Solutions 11-1
Chapter 12: Binary Search Trees
Solutions 12-1
Chapter 13: Red-Black Trees
Solutions 13-1
Chapter 14: Dynamic Programming
Solutions 14-1
Chapter 15: Greedy Algorithms
Solutions 15-1
Chapter 16: Amortized Analysis
Solutions 16-1
Chapter 17: Augmenting Data Structures
Solutions 17-1
Chapter 19: Data Structures for Disjoint Sets
Solutions 19-1
, iv Contents
Chapter 20: Elementary Graph Algorithms
Solutions 20-1
Chapter 21: Minimum Spanning Trees
Solutions 21-1
Chapter 22: Single-Source Shortest Paths
Solutions 22-1
Chapter 23: All-Pairs Shortest Paths
Solutions 23-1
Chapter 24: Maximum Flow
Solutions 24-1
Chapter 25: Matchings in Bipartite Graphs
Solutions 25-1
Chapter 26: Parallel Algorithms
Solutions 26-1
Chapter 30: Polynomials and the FFT
Solutions 30-1
Chapter 32: String Matching
Solutions 32-1
Chapter 35: Approximation Algorithms
Solutions 35-1
Index I-1
by Thomas H. Cormen
to Accompany
Introduction to Algorithms
Fourth Edition
by Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
The MIT Press
Cambridge, Massachusetts London, England
,Instructor’s Manual to Accompany Introduction to Algorithms, Fourth Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Published by the MIT Press. Copyright © 2022 by The Massachusetts Institute of Technology. All rights reserved.
No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database
or retrieval system, without the prior written consent of The MIT Press, including, but not limited to, network or
other electronic storage or transmission, or broadcast for distance learning.
,Contents
Revision History R-1
Preface P-1
Chapter 2: Getting Started
Solutions 2-1
Chapter 3: Characterizing Running Times
Solutions 3-1
Chapter 4: Divide-and-Conquer
Solutions 4-1
Chapter 5: Probabilistic Analysis and Randomized Algorithms
Solutions 5-1
Chapter 6: Heapsort
Solutions 6-1
Chapter 7: Quicksort
Solutions 7-1
Chapter 8: Sorting in Linear Time
Solutions 8-1
Chapter 9: Medians and Order Statistics
Solutions 9-1
Chapter 10: Elementary Data Structures
Solutions 10-1
Chapter 11: Hash Tables
Solutions 11-1
Chapter 12: Binary Search Trees
Solutions 12-1
Chapter 13: Red-Black Trees
Solutions 13-1
Chapter 14: Dynamic Programming
Solutions 14-1
Chapter 15: Greedy Algorithms
Solutions 15-1
Chapter 16: Amortized Analysis
Solutions 16-1
Chapter 17: Augmenting Data Structures
Solutions 17-1
Chapter 19: Data Structures for Disjoint Sets
Solutions 19-1
, iv Contents
Chapter 20: Elementary Graph Algorithms
Solutions 20-1
Chapter 21: Minimum Spanning Trees
Solutions 21-1
Chapter 22: Single-Source Shortest Paths
Solutions 22-1
Chapter 23: All-Pairs Shortest Paths
Solutions 23-1
Chapter 24: Maximum Flow
Solutions 24-1
Chapter 25: Matchings in Bipartite Graphs
Solutions 25-1
Chapter 26: Parallel Algorithms
Solutions 26-1
Chapter 30: Polynomials and the FFT
Solutions 30-1
Chapter 32: String Matching
Solutions 32-1
Chapter 35: Approximation Algorithms
Solutions 35-1
Index I-1
