Introducción al algoritmo
Páginas: 541 (135203 palabras)
Publicado: 17 de noviembre de 2011
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 Dubuque, IA St. Louis Montr´ al e Madison, WI Toronto
McGraw-Hill Book Company Boston Burr Ridge, IL New York San Francisco 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 ofTechnology 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., including, but not limited to, network or other electronic storage or transmission, or broadcast for distancelearning.
Contents
Revision History Preface P-1
R-1
Chapter 2: Getting Started Lecture Notes 2-1 Solutions 2-16 Chapter 3: Growth of Functions Lecture Notes 3-1 Solutions 3-7 Chapter 4: Recurrences Lecture Notes 4-1 Solutions 4-8 Chapter 5: Probabilistic Analysis and Randomized Algorithms Lecture Notes 5-1 Solutions 5-8 Chapter 6: Heapsort Lecture Notes 6-1 Solutions 6-10 Chapter 7:Quicksort Lecture Notes 7-1 Solutions 7-9 Chapter 8: Sorting in Linear Time Lecture Notes 8-1 Solutions 8-9 Chapter 9: Medians and Order Statistics Lecture Notes 9-1 Solutions 9-9 Chapter 11: Hash Tables Lecture Notes 11-1 Solutions 11-16 Chapter 12: Binary Search Trees Lecture Notes 12-1 Solutions 12-12 Chapter 13: Red-Black Trees Lecture Notes 13-1 Solutions 13-13 Chapter 14: Augmenting DataStructures Lecture Notes 14-1 Solutions 14-9
iv
Contents
Chapter 15: Dynamic Programming Lecture Notes 15-1 Solutions 15-19 Chapter 16: Greedy Algorithms Lecture Notes 16-1 Solutions 16-9 Chapter 17: Amortized Analysis Lecture Notes 17-1 Solutions 17-14 Chapter 21: Data Structures for Disjoint Sets Lecture Notes 21-1 Solutions 21-6 Chapter 22: Elementary Graph Algorithms Lecture Notes 22-1Solutions 22-12 Chapter 23: Minimum Spanning Trees Lecture Notes 23-1 Solutions 23-8 Chapter 24: Single-Source Shortest Paths Lecture Notes 24-1 Solutions 24-13 Chapter 25: All-Pairs Shortest Paths Lecture Notes 25-1 Solutions 25-8 Chapter 26: Maximum Flow Lecture Notes 26-1 Solutions 26-15 Chapter 27: Sorting Networks Lecture Notes 27-1 Solutions 27-8 Index I-1
Revision History
Revisions arelisted 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 Exercises5.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 chapters: Chapter12. 23 July 2003. Updated the solution to Exercise 22.3-4(b) to adjust for a correction 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 Exercise 23.2-7 and Problem 26-4. Affected chapters: Chapters 23, 24, and 26; index. 20 May 2003....
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 Dubuque, IA St. Louis Montr´ al e Madison, WI Toronto
McGraw-Hill Book Company Boston Burr Ridge, IL New York San Francisco 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 ofTechnology 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., including, but not limited to, network or other electronic storage or transmission, or broadcast for distancelearning.
Contents
Revision History Preface P-1
R-1
Chapter 2: Getting Started Lecture Notes 2-1 Solutions 2-16 Chapter 3: Growth of Functions Lecture Notes 3-1 Solutions 3-7 Chapter 4: Recurrences Lecture Notes 4-1 Solutions 4-8 Chapter 5: Probabilistic Analysis and Randomized Algorithms Lecture Notes 5-1 Solutions 5-8 Chapter 6: Heapsort Lecture Notes 6-1 Solutions 6-10 Chapter 7:Quicksort Lecture Notes 7-1 Solutions 7-9 Chapter 8: Sorting in Linear Time Lecture Notes 8-1 Solutions 8-9 Chapter 9: Medians and Order Statistics Lecture Notes 9-1 Solutions 9-9 Chapter 11: Hash Tables Lecture Notes 11-1 Solutions 11-16 Chapter 12: Binary Search Trees Lecture Notes 12-1 Solutions 12-12 Chapter 13: Red-Black Trees Lecture Notes 13-1 Solutions 13-13 Chapter 14: Augmenting DataStructures Lecture Notes 14-1 Solutions 14-9
iv
Contents
Chapter 15: Dynamic Programming Lecture Notes 15-1 Solutions 15-19 Chapter 16: Greedy Algorithms Lecture Notes 16-1 Solutions 16-9 Chapter 17: Amortized Analysis Lecture Notes 17-1 Solutions 17-14 Chapter 21: Data Structures for Disjoint Sets Lecture Notes 21-1 Solutions 21-6 Chapter 22: Elementary Graph Algorithms Lecture Notes 22-1Solutions 22-12 Chapter 23: Minimum Spanning Trees Lecture Notes 23-1 Solutions 23-8 Chapter 24: Single-Source Shortest Paths Lecture Notes 24-1 Solutions 24-13 Chapter 25: All-Pairs Shortest Paths Lecture Notes 25-1 Solutions 25-8 Chapter 26: Maximum Flow Lecture Notes 26-1 Solutions 26-15 Chapter 27: Sorting Networks Lecture Notes 27-1 Solutions 27-8 Index I-1
Revision History
Revisions arelisted 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 Exercises5.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 chapters: Chapter12. 23 July 2003. Updated the solution to Exercise 22.3-4(b) to adjust for a correction 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 Exercise 23.2-7 and Problem 26-4. Affected chapters: Chapters 23, 24, and 26; index. 20 May 2003....
Leer documento completo
Regístrate para leer el documento completo.