|Published (Last):||19 March 2011|
|PDF File Size:||19.58 Mb|
|ePub File Size:||9.90 Mb|
|Price:||Free* [*Free Regsitration Required]|
Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein. Cormen, Charles E. Leiserson, Ronald L. 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 or The McGraw-Hill Companies, Inc. Revisions are listed by date rather than being numbered. Because this revision history is part of each revision, the affected chapters always include the front matter in addition to those listed below.
Corrected an error in the transpose-symmetry properties. Affected chapters: Chapter 3. Added solutions to Exercises 5.
Made minor changes in the solutions to Problems and Affected chapters: Chapters 5, 11, 12, 16, 17, 21, and 26; index. Corrected two minor typographical errors in the lecture notes for the expected height of a randomly built binary search tree. Affected chapters: Chapter Updated the solution to Exercise Affected chapters: Chapter 22; index.
Added the link to the website for the clrscode package to the preface. Added the solution to Problem Corrected solutions to Exercise Affected chapters: Chapters 23, 24, and 26; index. Added solutions to Exercises Affected chapters: Chapters 24 and 26; index. Corrected a minor typographical error in the Chapter 22 notes on page Affected chapters: Chapters 21 and 22; index.
Added the solution to Exercise Affected chapters: Chapters 16, 17, and 22; index. Corrected an error in the solution to Exercise Reversed the order of Exercises Affected chapters: Chapter 13, index. Corrected an error in the substitution method for recurrences on page Affected chapters: Chapter 4. Corrected a minor typographical error in the Chapter 8 notes on page Affected chapters: Chapter 8.
Changed the exposition of indicator random variables in the Chapter 5 notes to correct for an error in the text. Affected pages: through The only content changes are on page ; in pages and only pagination changes.
Affected chapters: Chapter 5. Corrected an error in the pseudocode for the solution to Exercise 2. Affected chapters: Chapter 2. Initial release. Rivest, and Clifford Stein. It is intended for use in a course on algorithms. That is, for most chapters we have provided a set of lecture notes and a set of exercise and problem solutions pertaining to the chapter.
This organization allows you to decide how to best use the material in the manual in your own course. We have not included lecture notes and solutions for every chapter, nor have we included solutions for every exercise and problem within the chapters that we have selected. We felt that Chapter 1 is too nontechnical to include here, and Chapter 10 consists of background material that often falls outside algorithms and datastructures courses.
We have also omitted the chapters that are not covered in the courses that we teach: Chapters 18—20 and 28—35, as well as Appendices A—C; future editions of this manual may include some of these chapters. There are two reasons that we have not included solutions to all exercises and problems in the selected chapters. First, writing up all these solutions would take a long time, and we felt it more important to release this manual in as timely a fashion as possible.
Second, if we were to include all solutions, this manual would be longer than the text itself! We chose this form of page numbering so that if we add or change solutions to exercises and problems, the only pages whose numbering is affected are those for the solutions for that chapter. Moreover, if we add material for currently uncovered chapters, the numbers of the existing pages will remain unchanged.
The lecture notes The lecture notes are based on three sources:. Some are written just for this manual. Some sections of the text—usually starred—are omitted from the lecture notes. We have included lecture notes for one starred section: The asides are typeset in a slanted font and are enclosed in square brackets.
If you are projecting a presentation rather than writing on a blackboard or whiteboard, you might want to mark slides containing this material so that you can easily come back to them later in the lecture. We have chosen not to indicate how long it takes to cover material, as the time necessary to cover a topic depends on the instructor, the students, the class schedule, and other variables. Lines are not numbered in the lecture notes. We avoid using the length attribute of an array. Instead, we pass the array length as a parameter to the procedure.
This change makes the pseudocode more concise, as well as matching better with the description of what it does. The solutions The solutions are based on the same sources as the lecture notes. They are written a bit more formally than the lecture notes, though a bit less formally than the text.
We do not number lines of pseudocode, but we do use the length attribute on the assumption that you will want your students to write pseudocode as it appears in the text. The index lists all the exercises and problems for which this manual provides solutions, along with the number of the page on which each solution starts. Asides appear in a handful of places throughout the solutions.
We apologize for this inconvenience. It enables you to typeset pseudocode in the same way that we do. That site also includes documentation. Please report errors by sending email to clrs-manual-bugs mhhe. We thank you in advance for your assistance in correcting errors in both this manual and the text. The other three Introduction to Algorithms authors—Charles Leiserson, Ron Rivest, and Cliff Stein—provided helpful comments and suggestions for solutions to exercises and problems.
At this point, we do not know which TAs wrote which solutions, and so we simply thank them collectively. Phillip Meek of McGrawHill helped us hook this manual into their web site. Start using frameworks for describing and analyzing algorithms. Examine two algorithms for sorting: insertion sort and merge sort. See how to describe algorithms in pseudocode. Begin using asymptotic notation to express running-time analysis. The sequences are typically stored in arrays. We also refer to the numbers as keys.
Along with each key may be additional information, known as satellite data. Expressing algorithms We express algorithms in whatever way is the clearest and most concise. English is sometimes the best way. When issues of control need to be made perfectly clear, we often use pseudocode. If you know any of these languages, you should be able to understand pseudocode.
Pseudocode is designed for expressing algorithms to humans. Software engineering issues of data abstraction, modularity, and error handling are often ignored. We sometimes embed English statements into pseudocode. Insertion sort A good algorithm for sorting a small number of elements. Start with an empty left hand and the cards face down on the table. Then remove one card at a time from the table, and insert it into the correct position in the left hand.
At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table. Takes as parameters an array A[1. There are a few places in later chapters where we use 0-origin indexing instead. An easier option is, when using an array A[1.
SOLUTIONS MANUAL Introduction to Algorithms 2nd edition by T. Cormen