Introduction to Algorithms

Description

The latest edition of the essential text and professional reference, with substantial new material on such topics as vEB trees, multithreaded algorithms, dynamic programming, and edge-based flow. Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor. The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming. The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, substantial additions to the chapter on recurrence (now called “Divide-and-Conquer”), and an appendix on matrices. It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many exercises and problems have been added for this edition. The international paperback edition is no longer available; the hardcover is available worldwide. Contents......Page 6 Preface......Page 14 I Foundations......Page 23 1.1 Algorithms......Page 26 1.2 Algorithms as a technology......Page 32 Problems......Page 35 Notes......Page 36 2.1 Insertion sort......Page 37 2.2 Analyzing algorithms......Page 44 2.3 Designing algorithms......Page 50 Problems......Page 60 Notes......Page 63 3.1 Asymptotic notation......Page 64 3.2 Standard notations and common functions......Page 74 Problems......Page 82 Notes......Page 85 4 Divide-and-Conquer......Page 86 4.1 The maximum-subarray problem......Page 89 4.2 Strassen's algorithm for matrix multiplication......Page 96 4.3 The substitution method for solving recurrences......Page 104 4.4 The recursion-tree method for solving recurrences......Page 109 4.5 The master method for solving recurrences......Page 114 * 4.6 Proof of the master theorem......Page 118 Problems......Page 128 Notes......Page 132 5.1 The hiring problem......Page 135 5.2 Indicator random variables......Page 139 5.3 Randomized algorithms......Page 143 (*) 5.4 Probabilistic analysis and further uses of indicator random variables......Page 151 Problems......Page 164 Notes......Page 166 II Sorting and Order Statistics......Page 167 6.1 Heaps......Page 172 6.2 Maintaining the heap property......Page 175 6.3 Building a heap......Page 177 6.4 The heapsort algorithm......Page 180 6.5 Priority queues......Page 183 Problems......Page 187 Notes......Page 189 7.1 Description of quicksort......Page 191 7.2 Performance of quicksort......Page 195 7.3 A randomized version of quicksort......Page 200 7.4 Analysis of quicksort......Page 201 Problems......Page 206 Notes......Page 211 8.1 Lower bounds for sorting......Page 212 8.2 Counting sort......Page 215 8.3 Radix sort......Page 218 8.4 Bucket sort......Page 221 Problems......Page 226 Notes......Page 232 9 Medians and Order Statistics......Page 234 9.1 Minimum and maximum......Page 235 9.2 Selection in expected linear time......Page 236 9.3 Selection in worst-case linear time......Page 241 Problems......Page 245 Notes......Page 248 III Data Structures......Page 249 10.1 Stacks and queues......Page 253 10.2 Linked lists......Page 257 10.3 Implementing pointers and objects......Page 262 10.4 Representing rooted trees......Page 267 Problems......Page 270 Notes......Page 273 11 Hash Tables......Page 274 11.1 Direct-address tables......Page 275 11.2 Hash tables......Page 277 11.3 Hash functions......Page 283 11.4 Open addressing......Page 290 (*) 11.5 Perfect hashing......Page 298 Problems......Page 303 Notes......Page 306 12.1 What is a binary search tree?......Page 307 12.2 Querying a binary search tree......Page 310 12.3 Insertion and deletion......Page 315 (*) 12.4 Randomly built search trees......Page 320 Problems......Page 324 Notes......Page 328 13.1 Properties of red-black trees......Page 329 13.2 Rotations......Page 333 13.3 Insertion......Page 336 13.4 Deletion......Page 344 Problems......Page 352 Notes......Page 358 14.1 Dynamic order statistics......Page 360 14.2 How to augment a data structure......Page 366 14.3 Interval Trees......Page 369 Problems......Page 375 Notes......Page 376 IV Advanced Design and Analysis Techniques......Page 377 15 Dynamic Programming......Page 380 15.1 Rod cutting......Page 381 15.2 Matrix-chain multiplication......Page 391 15.3 Elements of dynamic programming......Page 399 15.4 Longest common subsequence......Page 411 15.5 Optimal binary search trees......Page 418 Problems......Page 425 Notes......Page 433 16 Greedy Algorithms......Page 435 16.1 An activity-selection problem......Page 436 16.2 Elements of the greedy strategy......Page 444 16.3 Huffman codes......Page 449 (*) 16.4 Matroids and greedy methods......Page 458 (*) 16.5 A task-scheduling problem as a matroid......Page 464 Problems......Page 467 Notes......Page 471 17 Amortized Analysis......Page 472 17.1 Aggregate analysis......Page 473 17.2 The accounting method......Page 477 17.3 The potential method......Page 480 17.4 Dynamic tables......Page 484 Problems......Page 493 Notes......Page 499 V Advanced Data Structures......Page 501 18 B-Trees......Page 505 18.1 Definition of B-trees......Page 509 18.2 Basic operations on B-trees......Page 512 18.3 Deleting a key from a B-tree......Page 520 Problems......Page 523 Notes......Page 525 19 Fibonacci Heaps......Page 526 19.1 Structure of Fibonacci heaps......Page 528 19.2 Mergeable-heap operations......Page 531 19.3 Decreasing a key and deleting a node......Page 539 19.4 Bounding the maximum degree......Page 544 Problems......Page 547 Notes......Page 551 20 van Emde Boas Trees......Page 552 20.1 Preliminary approaches......Page 553 20.2 A recursive structure......Page 557 20.3 The van Emde Boas tree......Page 566 Problems......Page 578 Notes......Page 580 21.1 Disjoint-set operations......Page 582 21.2 Linked-list representation of disjoint sets......Page 585 21.3 Disjoint-set forests......Page 589 (*) 21.4 Analysis of union by rank with path compression......Page 594 Problems......Page 603 Notes......Page 606 VI Graph Algorithms......Page 607 22.1 Representations of graphs......Page 610 22.2 Breadth-first search......Page 615 22.3 Depth-first search......Page 624 22.4 Topological sort......Page 633 22.5 Strongly connected components......Page 636 Problems......Page 642 Notes......Page 644 23 Minimum Spanning Trees......Page 645 23.1 Growing a minimum spanning tree......Page 646 23.2 The algorithms of Kruskal and Prim......Page 652 Problems......Page 659 Notes......Page 662 24 Single-Source Shortest Paths......Page 664 24.1 The Bellman-Ford algorithm......Page 672 24.2 Single-source shortest paths in directed acyclic graphs......Page 676 24.3 Dijkstra's algorithm......Page 679 24.4 Difference constraints and shortest paths......Page 685 24.5 Proofs of shortest-paths properties......Page 692 Problems......Page 699 Notes......Page 703 25 All-Pairs Shortest Paths......Page 705 25.1 Shortest paths and matrix multiplication......Page 707 25.2 The Floyd-Warshall algorithm......Page 714 25.3 Johnson's algorithm for sparse graphs......Page 721 Problems......Page 726 Notes......Page 727 26 Maximum Flow......Page 729 26.1 Flow networks......Page 730 26.2 The Ford-Fulkerson method......Page 735 26.3 Maximum bipartite matching......Page 753 * 26.4 Push-relabel algorithms......Page 757 * 26.5 The relabel-to-front algorithm......Page 769 Problems......Page 781 Notes......Page 786 VII Selected Topics......Page 789 27 Multithreaded Algorithms......Page 793 27.1 The basics of dynamic multithreading......Page 795 27.2 Multithreaded matrix multiplication......Page 813 27.3 Multithreaded merge sort......Page 818 Problems......Page 826 Notes......Page 832 28.1 Solving systems of linear equations......Page 834 28.2 Inverting matrices......Page 848 28.3 Symmetric positive definite matrices and least-squares approximation......Page 853 Problems......Page 861 Notes......Page 863 29 Linear Programming......Page 864 29.1 Standard and slack forms......Page 871 29.2 Formulating problems as lienar programs......Page 880 29.3 The simplex algorithm......Page 885 29.4 Duality......Page 900 29.5 The initial basic feasible solution......Page 907 Problems......Page 915 Notes......Page 917 30 Polynomials and the FFT......Page 919 30.1 Representing polynomials......Page 921 30.2 The DFT and the FFT......Page 927 30.3 Efficient FFT implementations......Page 936 Problems......Page 941 Notes......Page 945 31 Number-Theoretic Algorithms......Page 947 31.1 Elementary number-theoretic notions......Page 948 31.2 Greatest common divisor......Page 954 31.3 Modular arithmetic......Page 960 31.4 Solving modular linear equations......Page 967 31.5 The Chinese remainder theorem......Page 971 31.6 Powers of an element......Page 975 31.7 The RSA public-key cryptosystem......Page 979 * 31.8 Primality testing......Page 986 * 31.9 Integer factorization......Page 996 Problems......Page 1002 Notes......Page 1003 32 String Matching......Page 1006 32.1 The naive string-matching algorithm......Page 1009 32.2 The Rabin-Karp algorithm......Page 1011 32.3 String matching with finite automata......Page 1016 * 32.4 The Knuth-Morris-Pratt algorithm......Page 1023 Problems......Page 1033 Notes......Page 1034 33 Computational Geometry......Page 1035 33.1 Line-segment properties......Page 1036 33.2 Determing whether any pair of segments intersects......Page 1042 33.3 Finding the convex hull......Page 1050 33.4 Finding the closest pair of points......Page 1060 Problems......Page 1065 Notes......Page 1068 34 NP-Completeness......Page 1069 34.1 Polynomial time......Page 1074 34.2 Polynomial-time verification......Page 1082 34.3 NP-completeness and reducibility......Page 1088 34.4 NP-completeness proofs......Page 1099 34.5 NP-complete problems......Page 1107 Problems......Page 1122 Notes......Page 1125 35 Approximation Algorithms......Page 1127 35.1 The vertex-cover problem......Page 1129 35.2 The traveling-salesman problem......Page 1132 35.3 The set-covering problem......Page 1138 35.4 Randomization and linear programming......Page 1144 35.5 The subset-sum problem......Page 1149 Problems......Page 1155 Notes......Page 1159 VIII Appendix: Mathematical Background......Page 1163 A.1 Summation formulas and properties......Page 1166 A.2 Bounding summations......Page 1170 B.1 Sets......Page 1179 B.2 Relations......Page 1184 B.3 Functions......Page 1187 B.4 Graphs......Page 1189 B.5 Trees......Page 1194 C.1 Counting......Page 1204 C.2 Probability......Page 1210 C.3 Discrete random variables......Page 1217 C.4 The geometric and binomial distributions......Page 1222 * C.5 The tails of the binomial distribution......Page 1229 D.1 Matrices and matrix operations......Page 1238 D.2 Basic matrix properties......Page 1243 Bibliography......Page 1252 Symbols......Page 1272 A......Page 1273 B......Page 1275 C......Page 1277 D......Page 1280 E......Page 1283 F......Page 1285 G......Page 1286 H......Page 1287 I......Page 1289 J......Page 1290 L......Page 1291 M......Page 1293 N......Page 1297 O......Page 1298 P......Page 1299 R......Page 1303 S......Page 1305 T......Page 1310 U......Page 1311 V......Page 1312 0-9......Page 1313