算法导论第2版课后习题答案解析.pdf-资料库

on_theway10-10877060-4744302543291047810.pdf-第1页.png

第1页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第2页.png

第2页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第3页.png

第3页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第4页.png

第4页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第5页.png

第5页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第6页.png

第6页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第7页.png

第7页 / 共429页

on_theway10-10877060-4744302543291047810.pdf-第8页.png

第8页 / 共429页

Instructorís Manual by Thomas H. Cormen Clara Lee Erica Lin to Accompany Introduction to Algorithms Second Edition by Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein The MIT Press Cambridge, Massachusetts London, England McGraw-Hill Book Company Boston New York Burr Ridge, IL San Francisco Dubuque, IA St. Louis Montr¥eal Madison, WI Toronto

Instructorís Manual by Thomas H. Cormen, Clara Lee, and Erica Lin to Accompany Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Published by The MIT Press and McGraw-Hill Higher Education, an imprint of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York, NY 10020. Copyright c⃝ 2002 by The Massachusetts Institute of Technology and The McGraw-Hill Companies, Inc. 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., in- cluding, but not limited to, network or other electronic storage or transmission, or broadcast for distance learning.

Contents R-1 Revision History Preface P-1 Chapter 2: Getting Started Lecture Notes Solutions 2-16 2-1 Chapter 3: Growth of Functions Lecture Notes Solutions 3-7 3-1 Chapter 4: Recurrences Lecture Notes Solutions 4-8 4-1 Chapter 5: Probabilistic Analysis and Randomized Algorithms Lecture Notes Solutions 5-8 5-1 Chapter 6: Heapsort 6-1 Lecture Notes Solutions 6-10 Chapter 7: Quicksort 7-1 Lecture Notes Solutions 7-9 Chapter 8: Sorting in Linear Time Lecture Notes Solutions 8-9 8-1 Chapter 9: Medians and Order Statistics Lecture Notes Solutions 9-9 9-1 Chapter 11: Hash Tables Lecture Notes Solutions 11-16 11-1 Chapter 12: Binary Search Trees Lecture Notes Solutions 12-12 12-1 Chapter 13: Red-Black Trees Lecture Notes Solutions 13-13 13-1 Chapter 14: Augmenting Data Structures Lecture Notes Solutions 14-9 14-1

iv Contents Chapter 15: Dynamic Programming Lecture Notes Solutions 15-19 15-1 Chapter 16: Greedy Algorithms Lecture Notes Solutions 16-9 16-1 Chapter 17: Amortized Analysis Lecture Notes Solutions 17-14 17-1 Chapter 21: Data Structures for Disjoint Sets Lecture Notes Solutions 21-6 21-1 Chapter 22: Elementary Graph Algorithms Lecture Notes Solutions 22-12 22-1 Chapter 23: Minimum Spanning Trees Lecture Notes Solutions 23-8 23-1 Chapter 24: Single-Source Shortest Paths Lecture Notes Solutions 24-13 24-1 Chapter 25: All-Pairs Shortest Paths Lecture Notes Solutions 25-8 25-1 Chapter 26: Maximum Flow Lecture Notes Solutions 26-15 26-1 Chapter 27: Sorting Networks 27-1 Lecture Notes Solutions I-1 27-8 Index

Revision History 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. • • • • • • • • • • • • 18 January 2005. Corrected an error in the transpose-symmetry properties. Affected chapters: Chapter 3. 2 April 2004. Added solutions to Exercises 5.4-6, 11.3-5, 12.4-1, 16.4-2, 16.4-3, 21.3-4, 26.4-2, 26.4-3, and 26.4-6 and to Problems 12-3 and 17-4. Made minor changes in the solutions to Problems 11-2 and 17-2. Affected chapters: Chapters 5, 11, 12, 16, 17, 21, and 26; index. 7 January 2004. Corrected two minor typographical errors in the lecture notes for the expected height of a randomly built binary search tree. Affected chap- ters: Chapter 12. 23 July 2003. Updated the solution to Exercise 22.3-4(b) to adjust for a correc- tion in the text. Affected chapters: Chapter 22; index. 23 June 2003. Added the link to the website for the clrscode package to the preface. 2 June 2003. Added the solution to Problem 24-6. Corrected solutions to Ex- ercise 23.2-7 and Problem 26-4. Affected chapters: Chapters 23, 24, and 26; index. 20 May 2003. Added solutions to Exercises 24.4-10 and 26.1-7. Affected chapters: Chapters 24 and 26; index. 2 May 2003. Added solutions to Exercises 21.4-4, 21.4-5, 21.4-6, 22.1-6, and 22.3-4. Corrected a minor typographical error in the Chapter 22 notes on page 22-6. Affected chapters: Chapters 21 and 22; index. 28 April 2003. Added the solution to Exercise 16.1-2, corrected an error in the ﬁrst adjacency matrix example in the Chapter 22 notes, and made a minor change to the accounting method analysis for dynamic tables in the Chapter 17 notes. Affected chapters: Chapters 16, 17, and 22; index. 10 April 2003. Corrected an error in the solution to Exercise 11.3-3. Affected chapters: Chapter 11. 3 April 2003. Reversed the order of Exercises 14.2-3 and 14.3-3. Affected chapters: Chapter 13, index. 2 April 2003. Corrected an error in the substitution method for recurrences on page 4-4. Affected chapters: Chapter 4.

R-2 Revision History • • • • • 31 March 2003. Corrected a minor typographical error in the Chapter 8 notes on page 8-3. Affected chapters: Chapter 8. 14 January 2003. Changed the exposition of indicator random variables in the Chapter 5 notes to correct for an error in the text. Affected pages: 5-4 through 5-6. (The only content changes are on page 5-4; in pages 5-5 and 5-6 only pagination changes.) Affected chapters: Chapter 5. 14 January 2003. Corrected an error in the pseudocode for the solution to Ex- ercise 2.2-2 on page 2-16. Affected chapters: Chapter 2. 7 October 2002. Corrected a typographical error in EUCLIDEAN-TSP on page 15-23. Affected chapters: Chapter 15. 1 August 2002. Initial release.

Preface This document is an instructorís manual to accompany Introduction to Algorithms, Second Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is intended for use in a course on algorithms. You might also ﬁnd some of the material herein to be useful for a CS 2-style course in data structures. Unlike the instructorís manual for the ﬁrst edition of the textówhich was organized around the undergraduate algorithms course taught by Charles Leiserson at MIT in Spring 1991ówe have chosen to organize the manual for the second edition according to chapters of the text. 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 Chap- ter 10 consists of background material that often falls outside algorithms and data- structures 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 have numbered the pages in this manual using the format CC-PP, where CC is a chapter number of the text and PP is the page number within that chapterís lecture notes and solutions. The PP numbers restart from 1 at the beginning of each chapterís lecture notes. 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:

P-2 Preface • Some are from the ﬁrst-edition manual, and so they correspond to Charles Leis- ersonís lectures in MITís undergraduate algorithms course, 6.046. • Some are from Tom Cormenís lectures in Dartmouth Collegeís undergraduate algorithms course, CS 25. • Some are written just for this manual. You will ﬁnd that the lecture notes are more informal than the text, as is appro- priate for a lecture situation. In some places, we have simpliﬁed the material for lecture presentation or even omitted certain considerations. Some sections of the textóusually starredóare omitted from the lecture notes. (We have included lec- ture notes for one starred section: 12.4, on randomly built binary search trees, which we cover in an optional CS 25 lecture.) In several places in the lecture notes, we have included ìasidesî to the instruc- tor. The asides are typeset in a slanted font and are enclosed in square brack- ets. [Hereisanaside.] Some of the asides suggest leaving certain material on the board, since you will be coming back to it later. If you are projecting a presenta- tion 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 nec- essary to cover a topic depends on the instructor, the students, the class schedule, and other variables. There are two differences in how we write pseudocode in the lecture notes and the text: • Lines are not numbered in the lecture notes. We ﬁnd them inconvenient to number when writing pseudocode on the board. • 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. We have also minimized the use of shading in ﬁgures within lecture notes, since drawing a ﬁgure with shading on a blackboard or whiteboard is difﬁcult. 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 solu- tions, along with the number of the page on which each solution starts. Asides appear in a handful of places throughout the solutions. Also, we are less reluctant to use shading in ﬁgures within solutions, since these ﬁgures are more likely to be reproduced than to be drawn on a board.

资料库

算法导论第2版课后习题答案解析.pdf

相关推荐

课程资源

热门标签

最新资料