Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest.pdf)

Introduction to Algorithms, Second EditionThomas H. CormenCharles E. LeisersonRonald L. RivestClifford SteinThe MIT PressCambridge , Massachusetts London, EnglandMcGraw-Hill Book CompanyBoston Burr Ridge , IL Dubuque , IA Madison , WI New York San Francisco St. LouisMontréal TorontoThis book is one of a series of texts written by faculty of the Electrical Engineering andComputer Science Department at the Massachusetts Institute of Technology. It was edited andproduced by The MIT Press under a joint production-distribution agreement with theMcGraw-Hill Book Company.Ordering Information:North AmericaText orders should be addressed to the McGraw-Hill Book Company. All other orders shouldbe addressed to The MIT Press.Outside North AmericaAll orders should be addressed to The MIT Press or its local distributor.Copyright © 2001 by The Massachusetts Institute of TechnologyFirst edition 1990All rights reserved.

No part of this book may be reproduced in any form or by any electronicor mechanical means (including photocopying, recording, or information storage andretrieval) 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 DataIntroduction 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, ThomasH.QA76.6 I5858 2001005.1-dc212001031277PrefaceThis book provides a comprehensive introduction to the modern study of computeralgorithms.

It presents many algorithms and covers them in considerable depth, yet makestheir design and analysis accessible to all levels of readers. We have tried to keepexplanations 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 anyonewho has done a little programming. The book contains over 230 figures illustrating how thealgorithms work. Since we emphasize efficiency as a design criterion, we include carefulanalyses of the running times of all our algorithms.The text is intended primarily for use in undergraduate or graduate courses in algorithms ordata structures.

Because it discusses engineering issues in algorithm design, as well asmathematical 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 theaddition of new chapters to the rewriting of individual sentences.To the teacherThis book is designed to be both versatile and complete. You will find it useful for a varietyof courses, from an undergraduate course in data structures up through a graduate course inalgorithms. Because we have provided considerably more material than can fit in a typicalone-term course, you should think of the book as a "buffet" or "smorgasbord" from which youcan 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 havemade chapters relatively self-contained, so that you need not worry about an unexpected andunnecessary dependence of one chapter on another. Each chapter presents the easier materialfirst and the more difficult material later, with section boundaries marking natural stoppingpoints. In an undergraduate course, you might use only the earlier sections from a chapter; ina graduate course, you might cover the entire chapter.We have included over 920 exercises and over 140 problems. Each section ends withexercises, and each chapter ends with problems.

The exercises are generally short questionsthat test basic mastery of the material. Some are simple self-check thought exercises, whereasothers are more substantial and are suitable as assigned homework. The problems are moreelaborate case studies that often introduce new material; they typically consist of severalquestions 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 studentsthan for undergraduates. A starred section is not necessarily more difficult than an unstarredone, but it may require an understanding of more advanced mathematics.

Likewise, starredexercises may require an advanced background or more than average creativity.To the studentWe hope that this textbook provides you with an enjoyable introduction to the field ofalgorithms. We have attempted to make every algorithm accessible and interesting. To helpyou when you encounter unfamiliar or difficult algorithms, we describe each one in a step-bystep manner. We also provide careful explanations of the mathematics needed to understandthe analysis of the algorithms.

If you already have some familiarity with a topic, you will findthe chapters organized so that you can skim introductory sections and proceed quickly to themore advanced material.This is a large book, and your class will probably cover only a portion of its material. Wehave tried, however, to make this a book that will be useful to you now as a course textbookand 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 understandrecursive procedures and simple data structures such as arrays and linked lists.You should have some facility with proofs by mathematical induction. A few portionsof the book rely on some knowledge of elementary calculus. Beyond that, Parts I andVIII of this book teach you all the mathematical techniques you will need.To the professionalThe wide range of topics in this book makes it an excellent handbook on algorithms. Becauseeach 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 addressimplementation concerns and other engineering issues. We often provide practical alternativesto the few algorithms that are primarily of theoretical interest.If you wish to implement any of the algorithms, you will find the translation of ourpseudocode into your favorite programming language a fairly straightforward task. Thepseudocode is designed to present each algorithm clearly and succinctly. Consequently, we donot address error-handling and other software-engineering issues that require specificassumptions about your programming environment. We attempt to present each algorithmsimply and directly without allowing the idiosyncrasies of a particular programming languageto obscure its essence.To our colleaguesWe have supplied an extensive bibliography and pointers to the current literature.

Eachchapter ends with a set of "chapter notes" that give historical details and references. Thechapter 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 couldnot be included due to lack of space.Despite myriad requests from students for solutions to problems and exercises, we havechosen as a matter of policy not to supply references for problems and exercises, to removethe temptation for students to look up a solution rather than to find it themselves.Changes for the second editionWhat has changed between the first and second editions of this book? Depending on how youlook 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 sectionsappear in the second edition.

We removed two chapters and a handful of sections, but we haveadded three new chapters and four new sections apart from these new chapters. If you were tojudge the scope of the changes by the table of contents, you would likely conclude that thechanges were modest.The changes go far beyond what shows up in the table of contents, however. In no particularorder, 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 thefirst 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 onthe following topics:o perfect hashing (Section 11.5),o two applications of dynamic programming (Sections 15.1 and 15.5), ando 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 onmathematical background have been moved from Part I to the Appendix, which is PartVIII.There are over 40 new problems and over 185 new exercises.We have made explicit the use of loop invariants for proving correctness.

Our firstloop invariant appears in Chapter 2, and we use them a couple of dozen timesthroughout the book.Many of the probabilistic analyses have been rewritten. In particular, we use in adozen places the technique of "indicator random variables," which simplifyprobabilistic analyses, especially when random variables are dependent.We have expanded and updated the chapter notes and bibliography. The bibliographyhas grown by over 50%, and we have mentioned many new algorithmic results thathave 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, inSection 4.2, we have "promoted" recursion trees to constitute a method in their ownright.