Introduction to Algorithms (2nd Edition).pdf

所需积分/C币:36 2011-10-25 11:20:49 7.4MB PDF
收藏 收藏 1
举报

Introduction to Algorithms (2nd Edition).pdf 算法导论 第二版 英文原版 非扫描版
This page intentionally left blank Thomas h. cormen Charles e leiserson Ronald L. Rivest Clifford Stein Introduction to Algorithms Second edition The Mit Press Cambridge, Massachusetts London, england McGraw-Hill Book Company Boston Burr ridge IL Dubuque. IA Madison Wi New York San francisco St Louis Montreal Toronto This book is one of a series of texts written by faculty of the electrical Engineering and Computer Science joint production-distribution agreement with the M cGraw-Hill Book Compa oduced by the m it press under a Department at the M assachusetts Institute of Technology. It was edited and pi Ordering Information North ameri Text orders should be addressed to the m cgraw-Hill Book Company. all other orders should be addressed to the MIT Press Outside north america all orders should be addressed to the m it press or its local distributor Third printing, 2002 C 2001 by the m assachusetts Institute of Technology First edition 1990 All rights reserved No part of this book may be reproduced in any form or by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval)without permission in writing from the bisher This book was printed and bound in the U nited States of a merica Library of Congress Cataloging-in-Publication Data Introduction to algorithms /Thomas H Cormen.. [et al. ] -2nd ed Includes biblioqtor2-7(hC: alk. paper, M IT Press). -ISBN 0-07-013151-1(M cGraw-Hill) hi cal references and index ISBN0-262-0329 1. Computer programming. 2. Computer algorithms. I Title Algorithms. II. Cormen, Thomas H QA76.6158582001 0051-dc21 2001031277 Contents Preface xiii I Foundations Introduction 1 the role of a lgorithms in C omputing 5 1. 1 algorithms 5 1.2 Algorithms as a technology 10 2 Getting Started 15 2.1 Insertion sort 15 2. 2 A nalyzing al gorithms 21 2.3 Designing algorithms 27 3 G rowth of functions 41 3.1 a symptotic notation 41 3.2 Standard notations and common functions 51 4 Recurrences 62 4. 1 the substitution method 63 4.2 The recursion- tree method 67 4,3 the master method 73 * 4.4 Proof of the master theorem 76 5 Probabilistic A nalysis and randomized algorithms 91 5. 1 the hiring problem 91 5.2 Indicator random variables 94 5.3 Randomized algorithms 99 5.4 probabilistic anal ysis and further uses of indicator random variables 106 Contents II Sorting and Order Statistics Introduction 123 6 Heapsort 127 6. 1 H eaps 127 6. 2 M aintaining the heap property 130 6. 3 Building a heap 132 6.4 the heapsort al gorithm 135 6.5 Priority queues 138 7 Quicksort 145 7.1 Description of quicksort 145 7. 2 Performance of quicksort 149 7.3 A randomized version of quicksort 153 7.4 A nalysis of quicksort 155 8 Sorting in Linear time 165 8. 1 Lower bounds for sorting 165 8.2 Counting sort 168 8.3 Radix sort 170 8. 4 Bucket sort 174 9 Medians and order statistics 183 9. 1 M inimum and maximum 184 9.2 Selection in expected linear time 185 9.3 Selection in worst-case linear time 189 Data structure Introduction 197 10 Elementary Data Structures 200 10. 1 Stacks and queues 200 10.2 Linked lists 204 10.3 Implementing pointers and objects 209 10.4 Representing rooted trees 214 1 Hash tables 221 11. 1 Direct-address tables 222 11.2 H ash tables 224 11,3 Hash functions 229 11.4 Open addressing 237 11.5 Perfect hashing 245 Contents 12 Binary Search Trees 253 12. 1 What is a binary search tree? 253 12.2 Querying a binary search tree 256 12.3 Insertion and deletion 261 12.4 Randomly built binary search trees 265 13 Red-Black Trees 273 13. 1 Properties of red-black trees 273 13.2 Rotations 277 13. 3 Insertion 280 13 4 Deletion 288 14 Augmenting Data Structures 302 14. 1 D ynamic order statistics 302 14.2 How to augment a data structure 308 14.3 Interval trees 311 Iv Advanced Design and analysis Techniques Introduction 321 15 Dynamic Programming 323 15. 1 A ssembly-line scheduling 324 15.2 M atrix-chain multiplication 331 15.3 Elements of dynamic programming 339 15. 4 L ongest common subsequence 350 15.5 Optimal binary search trees 356 16 G reedy algorithms 370 16. 1 A n activity-selection problem 371 16.2 Elements of the greedy strategy 379 16.3 Huffman codes 385 16.4 theoretical foundations for greedy methods 393 16.5 a task-scheduling problem 399 17 Amortized analysis 405 17. 1 a ggregate anal ysis 406 17. 2 The accounting method 410 17. 3 The potenti al method 412 17.4 D ynamic tables 416 Contents v Advanced data structures Introduction 431 18 B-Trees 434 18. 1 Definition of b-trees 438 18.2 B asic operations on B-trees 441 18.3 Deleting a key from a B-tree 449 19 Binomial Heaps 455 19.2 O perations on binomial heaps 46/ 457 19. 1 Binomial trees and binomial heaps 20 Fibonacci Heaps 476 20.1 Structure of Fibonacci heaps 477 20.2 M ergeable-heap operations 479 20.3 Decreasing a key and deleting a node 489 20. 4 bounding the maximum degree 493 21 Data Structures for Disjoint Sets 498 21.1 Disjoint-set operations 498 21.2 Linked-list representation of disjoint sets 501 21.3 Disjoint-set forests 505 21 4 a nal ysis of union by rank with path compression 509 Vi Graph algorithms Introduction 525 22 Elementary Graph algorithms 527 22.1 Representations of graphs 527 22.2 B readth -first search 531 22.3 Depth-first search 540 22. 4 Topological sort 549 22.5 Strongly connected components 552 23 Minimum Spanning Trees 561 23. 1 Growing a minimum spanning tree 562 23.2 the algorithms of k ruskal and prim 567 24 Single-Source Shortest Paths 580 24.1 The bell man- Ford al gorithm 588 24.2 Single-source shortest paths in directed acyclic graphs 592 24.3 Dijkstra's algorithm 595 24.4 Difference constraints and shortest paths 601 24.5 Proofs of shortest-paths properties 607 Contents 25 All-Pairs shortest paths 620 25.1 Shortest paths and matrix multiplication 622 25.2 The Floyd-Warshall al gorithm 629 25.3 Johnson's algorithm for sparse graphs 636 26 Maximum flow 643 26. 1 Flow networks 644 26.2 the ford- Ful kerson method 651 26.3 M aximum biparti te matching 664 26.4 Push-rel abel algorithms 669 26.5 the relabel-to-front algorithm 681 VII Selected Topics Introduction 701 27 Sorting networks 704 27. 1 Comparison networks 704 27.2 The zero-one principle 709 27.3 a bitonic sorting network 712 27. 4 A merging network 716 27.5 A sorting network 719 28 M atrix o perations 725 28. 1 Properties of matrices 725 28.2 Strassen 's al gorithm for matrix multiplication 735 28.3 Solving systems of linear equations 742 28.4 Inverting matrices 755 28.5 Symmetric positive-definite matrices and least-squares approximation 760 29 Linear programming 770 29. 1 Standard and slack forms 777 29.2 Formulating problems as linear programs 785 29. 3 The simplex al gorithm 790 29.4 Duality 804 29.5 the initial basic feasi ble solution 811 30 Polynomials and the FFt 822 30. 1 Representation of polynomials 824 30.2 the d ft and fft 830 30.3 Efficient FFT implementations 839

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    一个资源只可评论一次,评论内容不能少于5个字
    jiangyunwei2012 好书!准备好好学习一下!
    2017-09-08
    回复
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐