Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 2
Текст из файла (страница 2)
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 togenerate guesses that are then verified via the substitution method.The partitioning method used for quicksort (Section 7.1) and the expected linear-timeorder-statistic algorithm (Section 9.2) is different. We now use the method developedby Lomuto, which, along with indicator random variables, allows for a somewhatsimpler analysis. The method from the first edition, due to Hoare, appears as aproblem in Chapter 7.We have modified the discussion of universal hashing in Section 11.3.3 so that itintegrates into the presentation of perfect hashing.There is a much simpler analysis of the height of a randomly built binary search tree inSection 12.4.The discussions on the elements of dynamic programming (Section 15.3) and theelements of greedy algorithms (Section 16.2) are significantly expanded.
Theexploration of the activity-selection problem, which starts off the greedy-algorithmschapter, helps to clarify the relationship between dynamic programming and greedyalgorithms.We have replaced the proof of the running time of the disjoint-set-union data structurein 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 inSection 22.5 is simpler, clearer, and more direct.Chapter 24, on single-source shortest paths, has been reorganized to move proofs ofthe essential properties to their own section.
The new organization allows us to focusearlier on algorithms.Section 34.5 contains an expanded overview of NP-completeness as well as new NPcompleteness proofs for the hamiltonian-cycle and subset-sum problems.Finally, virtually every section has been edited to correct, simplify, and clarify explanationsand proofs.Web siteAnother 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 ofknown errors, or make suggestions; we would like to hear from you.
We particularly welcomeideas for new exercises and problems, but please include solutions.We regret that we cannot personally respond to all comments.Acknowledgments for the first editionMany friends and colleagues have contributed greatly to the quality of this book. We thank allof you for your help and constructive criticisms.MIT's Laboratory for Computer Science has provided an ideal working environment. Ourcolleagues in the laboratory's Theory of Computation Group have been particularly supportiveand tolerant of our incessant requests for critical appraisal of chapters.
We specifically thankBaruch Awerbuch, Shafi Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, DavidShmoys, and Éva Tardos. Thanks to William Ang, Sally Bemus, Ray Hirschfeld, and MarkReinhold for keeping our machines (DEC Microvaxes, Apple Macintoshes, and SunSparcstations) running and for recompiling whenever we exceeded a compile-time limit.Thinking Machines Corporation provided partial support for Charles Leiserson to work onthis book during a leave of absence from MIT.Many colleagues have used drafts of this text in courses at other schools. They have suggestednumerous corrections and revisions. We particularly wish to thank Richard Beigel, AndrewGoldberg, Joan Lucas, Mark Overmars, Alan Sherman, and Diane Souvaine.Many teaching assistants in our courses have made significant contributions to thedevelopment of this material.
We especially thank Alan Baratz, Bonnie Berger, Aditi Dhagat,Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou, Cindy Phillips, MarkReinhold, Phil Rogaway, Flavio Rose, Arie Rudich, Alan Sherman, Cliff Stein, Susmita Sur,Gregory Troxel, and Margaret Tuttle.Additional valuable technical assistance was provided by many individuals. Denise Sergentspent many hours in the MIT libraries researching bibliographic references. Maria Sensale,the librarian of our reading room, was always cheerful and helpful. Access to Albert Meyer'spersonal library saved many hours of library time in preparing the chapter notes. ShlomoKipnis, Bill Niehaus, and David Wilson proofread old exercises, developed new ones, andwrote notes on their solutions.
Marios Papaefthymiou and Gregory Troxel contributed to theindexing. Over the years, our secretaries Inna Radzihovsky, Denise Sergent, Gayle Sherman,and especially Be Blackburn provided endless support in this project, for which we thankthem.Many errors in the early drafts were reported by students. We particularly thank BobbyBlumofe, Bonnie Eisenberg, Raymond Johnson, John Keen, Richard Lethin, Mark Lillibridge,John Pezaris, Steve Ponzio, and Margaret Tuttle for their careful readings.Colleagues have also provided critical reviews of specific chapters, or information on specificalgorithms, for which we are grateful.
We especially thank Bill Aiello, Alok Aggarwal, EricBach, Vašek Chvátal, Richard Cole, Johan Hastad, Alex Ishii, David Johnson, Joe Kilian,Dina Kravets, Bruce Maggs, Jim Orlin, James Park, Thane Plambeck, Hershel Safer, JeffShallit, Cliff Stein, Gil Strang, Bob Tarjan, and Paul Wang. Several of our colleagues alsograciously supplied us with problems; we particularly thank Andrew Goldberg, DannySleator, and Umesh Vazirani.It has been a pleasure working with The MIT Press and McGraw-Hill in the development ofthis text. We especially thank Frank Satlow, Terry Ehling, Larry Cohen, and Lorrie Lejeuneof The MIT Press and David Shapiro of McGraw-Hill for their encouragement, support, andpatience. We are particularly grateful to Larry Cohen for his outstanding copyediting.Acknowledgments for the second editionWhen we asked Julie Sussman, P.P.A., to serve as a technical copyeditor for the secondedition, we did not know what a good deal we were getting.
In addition to copyediting thetechnical content, Julie enthusiastically edited our prose. It is humbling to think of how manyerrors Julie found in our earlier drafts, though considering how many errors she found in thefirst edition (after it was printed, unfortunately), it is not surprising. Moreover, Julie sacrificedher own schedule to accommodate ours-she even brought chapters with her on a trip to theVirgin Islands! Julie, we cannot thank you enough for the amazing job you did.The work for the second edition was done while the authors were members of the Departmentof Computer Science at Dartmouth College and the Laboratory for Computer Science at MIT.Both were stimulating environments in which to work, and we thank our colleagues for theirsupport.Friends and colleagues all over the world have provided suggestions and opinions that guidedour writing. Many thanks to Sanjeev Arora, Javed Aslam, Guy Blelloch, Avrim Blum, ScotDrysdale, Hany Farid, Hal Gabow, Andrew Goldberg, David Johnson, Yanlin Liu, NicolasSchabanel, Alexander Schrijver, Sasha Shen, David Shmoys, Dan Spielman, Gerald JaySussman, Bob Tarjan, Mikkel Thorup, and Vijay Vazirani.Many teachers and colleagues have taught us a great deal about algorithms.
We particularlyacknowledge our teachers Jon L. Bentley, Bob Floyd, Don Knuth, Harold Kuhn, H. T. Kung,Richard Lipton, Arnold Ross, Larry Snyder, Michael I. Shamos, David Shmoys, KenSteiglitz, Tom Szymanski, Éva Tardos, Bob Tarjan, and Jeffrey Ullman.We acknowledge the work of the many teaching assistants for the algorithms courses at MITand Dartmouth, including Joseph Adler, Craig Barrack, Bobby Blumofe, Roberto De Prisco,Matteo Frigo, Igal Galperin, David Gupta, Raj D.
Iyer, Nabil Kahale, Sarfraz Khurshid,Stavros Kolliopoulos, Alain Leblanc, Yuan Ma, Maria Minkoff, Dimitris Mitsouras, AlinPopescu, Harald Prokop, Sudipta Sengupta, Donna Slonim, Joshua A. Tauber, Sivan Toledo,Elisheva Werner-Reiss, Lea Wittie, Qiang Wu, and Michael Zhang.Computer support was provided by William Ang, Scott Blomquist, and Greg Shomo at MITand by Wayne Cripps, John Konkle, and Tim Tregubov at Dartmouth. Thanks also to BeBlackburn, Don Dailey, Leigh Deacon, Irene Sebeda, and Cheryl Patton Wu at MIT and toPhyllis Bellmore, Kelly Clark, Delia Mauceli, Sammie Travis, Deb Whiting, and Beth Youngat Dartmouth for administrative support. Michael Fromberger, Brian Campbell, AmandaEubanks, Sung Hoon Kim, and Neha Narula also provided timely support at Dartmouth.Many people were kind enough to report errors in the first edition.
We thank the followingpeople, each of whom was the first to report an error from the first edition: Len Adleman,Selim Akl, Richard Anderson, Juan Andrade-Cetto, Gregory Bachelis, David Barrington, PaulBeame, Richard Beigel, Margrit Betke, Alex Blakemore, Bobby Blumofe, Alexander Brown,Xavier Cazin, Jack Chan, Richard Chang, Chienhua Chen, Ien Cheng, Hoon Choi, DrueColes, Christian Collberg, George Collins, Eric Conrad, Peter Csaszar, Paul Dietz, MartinDietzfelbinger, Scot Drysdale, Patricia Ealy, Yaakov Eisenberg, Michael Ernst, MichaelFormann, Nedim Fresko, Hal Gabow, Marek Galecki, Igal Galperin, Luisa Gargano, JohnGately, Rosario Genario, Mihaly Gereb, Ronald Greenberg, Jerry Grossman, StephenGuattery, Alexander Hartemik, Anthony Hill, Thomas Hofmeister, Mathew Hostetter, YihChun Hu, Dick Johnsonbaugh, Marcin Jurdzinki, Nabil Kahale, Fumiaki Kamiya, AnandKanagala, Mark Kantrowitz, Scott Karlin, Dean Kelley, Sanjay Khanna, Haluk Konuk, DinaKravets, Jon Kroger, Bradley Kuszmaul, Tim Lambert, Hang Lau, Thomas Lengauer, GeorgeMadrid, Bruce Maggs, Victor Miller, Joseph Muskat, Tung Nguyen, Michael Orlov, JamesPark, Seongbin Park, Ioannis Paschalidis, Boaz Patt-Shamir, Leonid Peshkin, PatricioPoblete, Ira Pohl, Stephen Ponzio, Kjell Post, Todd Poynor, Colin Prepscius, Sholom Rosen,Dale Russell, Hershel Safer, Karen Seidel, Joel Seiferas, Erik Seligman, Stanley Selkow,Jeffrey Shallit, Greg Shannon, Micha Sharir, Sasha Shen, Norman Shulman, Andrew Singer,Daniel Sleator, Bob Sloan, Michael Sofka, Volker Strumpen, Lon Sunshine, Julie Sussman,Asterio Tanaka, Clark Thomborson, Nils Thommesen, Homer Tilton, Martin Tompa, AndreiToom, Felzer Torsten, Hirendu Vaishnav, M.
Veldhorst, Luca Venuti, Jian Wang, MichaelWellman, Gerry Wiener, Ronald Williams, David Wolfe, Jeff Wong, Richard Woundy, NealYoung, Huaiyuan Yu, Tian Yuxing, Joe Zachary, Steve Zhang, Florian Zschoke, and UriZwick.Many of our colleagues provided thoughtful reviews or filled out a long survey. We thankreviewers Nancy Amato, Jim Aspnes, Kevin Compton, William Evans, Peter Gacs, MichaelGoldwasser, Andrzej Proskurowski, Vijaya Ramachandran, and John Reif.
We also thank thefollowing people for sending back the survey: James Abello, Josh Benaloh, Bryan BeresfordSmith, Kenneth Blaha, Hans Bodlaender, Richard Borie, Ted Brown, Domenico Cantone, M.Chen, Robert Cimikowski, William Clocksin, Paul Cull, Rick Decker, Matthew Dickerson,Robert Douglas, Margaret Fleck, Michael Goodrich, Susanne Hambrusch, Dean Hendrix,Richard Johnsonbaugh, Kyriakos Kalorkoti, Srinivas Kankanahalli, Hikyoo Koh, StevenLindell, Errol Lloyd, Andy Lopez, Dian Rae Lopez, George Lucker, David Maier, CharlesMartel, Xiannong Meng, David Mount, Alberto Policriti, Andrzej Proskurowski, Kirk Pruhs,Yves Robert, Guna Seetharaman, Stanley Selkow, Robert Sloan, Charles Steele, Gerard Tel,Murali Varanasi, Bernd Walter, and Alden Wright.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
