Introduction to Algorithms, Second Edition
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
The MIT Press
Cambridge , Massachusetts London, England
McGraw-Hill Book Company
Boston Burr Ridge , IL Dubuque , IA Madison , WI New York San Francisco St. Louis
Montréal Toronto
This book is one of a series of texts written by faculty of the Electrical Engineering and
Computer Science Department at the Massachusetts Institute of Technology. It was edited and
produced by The MIT Press under a joint production-distribution agreement with the
McGraw-Hill Book Company.
Ordering Information:
North America
Text orders should be addressed to the McGraw-Hill Book Company. All other orders should
be addressed to The MIT Press.
Outside North America
All orders should be addressed to The MIT Press or its local distributor.
Copyright © 2001 by The Massachusetts Institute of Technology
First edition 1990
All rights reserved. No part of this book may be reproduced in any form or by any electronic
or mechanical means (including photocopying, recording, or information storage and
retrieval) without permission in writing from the publisher.
This book was printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Introduction to algorithms / Thomas H. Cormen ... [et al.].-2nd ed.
p. cm.
Includes bibliographical references and index.
ISBN 0-262-03293-7 (hc.: alk. paper, MIT Press).-ISBN 0-07-013151-1 (McGraw-Hill)
1. Computer programming. 2. Computer algorithms. I. Title: Algorithms. II. Cormen, Thomas
H.
QA76.6 I5858 2001
005.1-dc21
2001031277
Preface
This book provides a comprehensive introduction to the modern study of computer
algorithms. It presents many algorithms and covers them in considerable depth, yet makes
their design and analysis accessible to all levels of readers. We have tried to keep
explanations elementary without sacrificing depth of coverage or mathematical rigor.
Each chapter presents an algorithm, a design technique, an application area, or a related topic.
Algorithms are described in English and in a "pseudocode" designed to be readable by anyone
who has done a little programming. The book contains over 230 figures illustrating how the
algorithms work. Since we emphasize efficiency as a design criterion, we include careful
analyses of the running times of all our algorithms.
The text is intended primarily for use in undergraduate or graduate courses in algorithms or
data structures. Because it discusses engineering issues in algorithm design, as well as
mathematical aspects, it is equally well suited for self-study by technical professionals.
In this, the second edition, we have updated the entire book. The changes range from the
addition of new chapters to the rewriting of individual sentences.
To the teacher
This book is designed to be both versatile and complete. You will find it useful for a variety
of courses, from an undergraduate course in data structures up through a graduate course in
algorithms. Because we have provided considerably more material than can fit in a typical
one-term course, you should think of the book as a "buffet" or "smorgasbord" from which you
can pick and choose the material that best supports the course you wish to teach.
You should find it easy to organize your course around just the chapters you need. We have
made chapters relatively self-contained, so that you need not worry about an unexpected and
unnecessary dependence of one chapter on another. Each chapter presents the easier material
first and the more difficult material later, with section boundaries marking natural stopping
points. In an undergraduate course, you might use only the earlier sections from a chapter; in
a graduate course, you might cover the entire chapter.
We have included over 920 exercises and over 140 problems. Each section ends with
exercises, and each chapter ends with problems. The exercises are generally short questions
that test basic mastery of the material. Some are simple self-check thought exercises, whereas
others are more substantial and are suitable as assigned homework. The problems are more
elaborate case studies that often introduce new material; they typically consist of several
questions that lead the student through the steps required to arrive at a solution.
We have starred (⋆) the sections and exercises that are more suitable for graduate students
than for undergraduates. A starred section is not necessarily more difficult than an unstarred
one, but it may require an understanding of more advanced mathematics. Likewise, starred
exercises may require an advanced background or more than average creativity.
To the student
We hope that this textbook provides you with an enjoyable introduction to the field of
algorithms. We have attempted to make every algorithm accessible and interesting. To help
you when you encounter unfamiliar or difficult algorithms, we describe each one in a step-by-
step manner. We also provide careful explanations of the mathematics needed to understand
the analysis of the algorithms. If you already have some familiarity with a topic, you will find
the chapters organized so that you can skim introductory sections and proceed quickly to the
more advanced material.
This is a large book, and your class will probably cover only a portion of its material. We
have tried, however, to make this a book that will be useful to you now as a course textbook
and also later in your career as a mathematical desk reference or an engineering handbook.
What are the prerequisites for reading this book?
• You should have some programming experience. In particular, you should understand
recursive procedures and simple data structures such as arrays and linked lists.
• You should have some facility with proofs by mathematical induction. A few portions
of the book rely on some knowledge of elementary calculus. Beyond that, Parts I and
VIII of this book teach you all the mathematical techniques you will need.
To the professional
The wide range of topics in this book makes it an excellent handbook on algorithms. Because
each chapter is relatively self-contained, you can focus in on the topics that most interest you.
Most of the algorithms we discuss have great practical utility. We therefore address
implementation concerns and other engineering issues. We often provide practical alternatives
to the few algorithms that are primarily of theoretical interest.
If you wish to implement any of the algorithms, you will find the translation of our
pseudocode into your favorite programming language a fairly straightforward task. The
pseudocode is designed to present each algorithm clearly and succinctly. Consequently, we do
not address error-handling and other software-engineering issues that require specific
assumptions about your programming environment. We attempt to present each algorithm
simply and directly without allowing the idiosyncrasies of a particular programming language
to obscure its essence.
To our colleagues
We have supplied an extensive bibliography and pointers to the current literature. Each
chapter ends with a set of "chapter notes" that give historical details and references. The
chapter notes do not provide a complete reference to the whole field of algorithms, however.
Though it may be hard to believe for a book of this size, many interesting algorithms could
not be included due to lack of space.
Despite myriad requests from students for solutions to problems and exercises, we have
chosen as a matter of policy not to supply references for problems and exercises, to remove
the temptation for students to look up a solution rather than to find it themselves.
Changes for the second edition
What has changed between the first and second editions of this book? Depending on how you
look at it, either not much or quite a bit.
A quick look at the table of contents shows that most of the first-edition chapters and sections
appear in the second edition. We removed two chapters and a handful of sections, but we have
added three new chapters and four new sections apart from these new chapters. If you were to
judge the scope of the changes by the table of contents, you would likely conclude that the
changes were modest.
The changes go far beyond what shows up in the table of contents, however. In no particular
order, here is a summary of the most significant changes for the second edition:
• Cliff Stein was added as a coauthor.
• Errors have been corrected. How many errors? Let's just say several.
• There are three new chapters:
o Chapter 1 discusses the role of algorithms in computing.
o Chapter 5 covers probabilistic analysis and randomized algorithms. As in the
first edition, these topics appear throughout the book.
o Chapter 29 is devoted to linear programming.
• Within chapters that were carried over from the first edition, there are new sections on
the following topics:
o perfect hashing (Section 11.5),
o two applications of dynamic programming (Sections 15.1 and 15.5), and
o approximation algorithms that use randomization and linear programming
(Section 35.4
).
• To allow more algorithms to appear earlier in the book, three of the chapters on
mathematical background have been moved from Part I
to the Appendix, which is Part
VIII.
• There are over 40 new problems and over 185 new exercises.
• We have made explicit the use of loop invariants for proving correctness. Our first
loop invariant appears in Chapter 2
, and we use them a couple of dozen times
throughout the book.
• Many of the probabilistic analyses have been rewritten. In particular, we use in a
dozen places the technique of "indicator random variables," which simplify
probabilistic analyses, especially when random variables are dependent.
• We have expanded and updated the chapter notes and bibliography. The bibliography
has grown by over 50%, and we have mentioned many new algorithmic results that
have appeared subsequent to the printing of the first edition.
We have also made the following changes:
• The chapter on solving recurrences no longer contains the iteration method. Instead, in
Section 4.2, we have "promoted" recursion trees to constitute a method in their own
right. We have found that drawing out recursion trees is less error-prone than iterating
recurrences. We do point out, however, that recursion trees are best used as a way to
generate guesses that are then verified via the substitution method.
• The partitioning method used for quicksort (Section 7.1) and the expected linear-time
order-statistic algorithm (Section 9.2) is different. We now use the method developed
by Lomuto, which, along with indicator random variables, allows for a somewhat
simpler analysis. The method from the first edition, due to Hoare, appears as a
problem in Chapter 7.
• We have modified the discussion of universal hashing in Section 11.3.3 so that it
integrates into the presentation of perfect hashing.
• There is a much simpler analysis of the height of a randomly built binary search tree in
Section 12.4.
• The discussions on the elements of dynamic programming (Section 15.3) and the
elements of greedy algorithms (Section 16.2
) are significantly expanded. The
exploration of the activity-selection problem, which starts off the greedy-algorithms
chapter, helps to clarify the relationship between dynamic programming and greedy
algorithms.
• We have replaced the proof of the running time of the disjoint-set-union data structure
in Section 21.4 with a proof that uses the potential method to derive a tight bound.
• The proof of correctness of the algorithm for strongly connected components in
Section 22.5 is simpler, clearer, and more direct.
• Chapter 24, on single-source shortest paths, has been reorganized to move proofs of
the essential properties to their own section. The new organization allows us to focus
earlier on algorithms.
• Section 34.5 contains an expanded overview of NP-completeness as well as new NP-
completeness proofs for the hamiltonian-cycle and subset-sum problems.
Finally, virtually every section has been edited to correct, simplify, and clarify explanations
and proofs.
Web site
Another change from the first edition is that this book now has its own web site:
http://mitpress.mit.edu/algorithms/. You can use the web site to report errors, obtain a list of
known errors, or make suggestions; we would like to hear from you. We particularly welcome
ideas for new exercises and problems, but please include solutions.
We regret that we cannot personally respond to all comments.
Acknowledgments for the first edition
Many friends and colleagues have contributed greatly to the quality of this book. We thank all
of you for your help and constructive criticisms.
MIT's Laboratory for Computer Science has provided an ideal working environment. Our
colleagues in the laboratory's Theory of Computation Group have been particularly supportive
and tolerant of our incessant requests for critical appraisal of chapters. We specifically thank
Baruch Awerbuch, Shafi Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, David
Shmoys, and Éva Tardos. Thanks to William Ang, Sally Bemus, Ray Hirschfeld, and Mark
Reinhold for keeping our machines (DEC Microvaxes, Apple Macintoshes, and Sun
