Instructor’s Manual
by Thomas H. Cormen
to Accompany
Introduction to Algorithms
Third 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,ThirdEdition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Published by the MIT Press. Copyright
c
! 2009 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 TheMITPress,including,butnotlimitedto,networkor
other electronic storage or transmission, or broadcast for distance learning.
Contents
Revision History R-1
Preface P-1
Chapter 2: Getting Started
Lecture Notes 2-1
Solutions 2-17
Chapter 3: Growth of Functions
Lecture Notes 3-1
Solutions 3-7
Chapter 4: Divide-and-Conquer
Lecture Notes 4-1
Solutions 4-17
Chapter 5: Probabilistic Analysis and Randomized Algorithms
Lecture Notes 5-1
Solutions 5-9
Chapter 6: Heapsort
Lecture Notes 6-1
Solutions 6-10
Chapter 7: Quicksort
Lecture Notes 7-1
Solutions 7-9
Chapter 8: Sorting in Linear Time
Lecture Notes 8-1
Solutions 8-10
Chapter 9: Medians and Order Statistics
Lecture Notes 9-1
Solutions 9-10
Chapter 11: Hash Tables
Lecture Notes 11-1
Solutions 11-16
Chapter 12: Binary Search Trees
Lecture Notes 12-1
Solutions 12-15
Chapter 13: Red-Black Trees
Lecture Notes 13-1
Solutions 13-13
Chapter 14: Augmenting Data Structures
Lecture Notes 14-1
Solutions 14-9
iv Contents
Chapter 15: Dynamic Programming
Lecture Notes 15-1
Solutions 15-21
Chapter 16: Greedy Algorithms
Lecture Notes 16-1
Solutions 16-9
Chapter 17: Amortized Analysis
Lecture Notes 17-1
Solutions 17-14
Chapter 21: Data Structures for Disjoint Sets
Lecture Notes 21-1
Solutions 21-6
Chapter 22: Elementary Graph Algorithms
Lecture Notes 22-1
Solutions 22-13
Chapter 23: Minimum Spanning Trees
Lecture Notes 23-1
Solutions 23-8
Chapter 24: Single-Source Shortest Paths
Lecture Notes 24-1
Solutions 24-13
Chapter 25: All-Pairs Shortest Paths
Lecture Notes 25-1
Solutions 25-9
Chapter 26: Maximum Flow
Lecture Notes 26-1
Solutions 26-12
Chapter 27: Multithreaded Algorithms
Solutions 27-1
Index I-1
Revision History
Revisions are listed by date rather than being numbered.
!
3January2012. AddedsolutionstoChapter27.Addedanalternative solution
to Exercise 2.3-7, courtesy of Viktor Korsun and Crystal Peng. Corrected a
minor error in the Chapter 15 notes in the recurrence for T.n/for the recursive
CUT-ROD procedure. Updated the solution to Problem 24-3. Corrected an
error in the proof about the Edmonds-Karp algorithm performing O.VE / flow
augmentations. The bodies of all pseudocode procedures are indented slightly.
!
28 January 2011. Corrected an error in the solution to Problem2-4(c),and
removed unnecessary code in the solution to Problem 2-4(d). Added a missing
parameter to recursive calls of REC-MAT-MULT on page 4-7. Changed the
pseudocode for HEAP-EXTRACT-MAX on page 6-8 and MAX-HEAP-INSERT
on page 6-9 to assume that the parameter n is passed by reference.
!
7May2010. ChangedthesolutionstoExercises22.2-3and22.3-4 because
these exercises changed.
!
17 February 2010. Corrected a minor error in the solution to Exercise 4.3-7.
!
16 December 2009. Added an alternative solution to Exercise 6.3-3, courtesy
of Eyal Mashiach.
!
7December2009.AddedsolutionstoExercises16.3-1,26.1-1, 26.1-3, 26.1-7,
26.2-1, 26.2-8, 26.2-9, 26.2-12, 26.2-13, and 26.4-1 and to Problem 26-3. Cor-
rected spelling in the solution to Exercise 16.2-4. Several corrections to the
solution to Exercise 16.4-3, courtesy of Zhixiang Zhu. Minorchangestothe
solutions to Exercises 24.3-3 and 24.4-7 and Problem 24-1.
!
7August2009.Initialrelease.
