Introduction to algorithms / Thomas H. Cormen ... [et al.].

Enhanced descriptions from Syndetics:

A new 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 new exercises and problems have been added for this edition. The international paperback edition is no longer available; the hardcover is available worldwide.

Table of contents provided by Syndetics

• Preface (p. xiii)
• I Foundations
• Introduction (p. 3)
• 1 The Role of Algorithms in Computing (p. 5)
• 1.1 Algorithms (p. 5)
• 1.2 Algorithms as a technology (p. 11)
• 2 Getting Started (p. 16)
• 2.1 Insertion sort (p. 16)
• 2.2 Analyzing algorithms (p. 23)
• 2.3 Designing algorithms (p. 29)
• 3 Growth of Functions (p. 43)
• 3.1 Asymptotic notation (p. 43)
• 3.2 Standard notations and common functions (p. 53)
• 4 Divide-and-Conquer (p. 65)
• 4.1 The maximum-subarray problem (p. 68)
• 4.2 Strassen's algorithm for matrix multiplication (p. 75)
• 4.3 The substitution method for solving recurrences (p. 83)
• 4.4 The recursion-tree method for solving recurrences (p. 88)
• 4.5 The master method for solving recurrences (p. 93)
• 4.6 Proof of the master theorem (p. 97)
• 5 Probabilistic Analysis and Randomized Algorithms (p. 114)
• 5.1 The hiring problem (p. 114)
• 5.2 Indicator random variables (p. 118)
• 5.3 Randomized algorithms (p. 122)
• 5.4 Probabilistic analysis and further uses of indicator random variables (p. 130)
• II Sorting and Order Statistics
• Introduction (p. 147)
• 6 Heapsort (p. 151)
• 6.1 Heaps (p. 151)
• 6.2 Maintaining the heap property (p. 154)
• 6.3 Building a heap (p. 156)
• 6.4 The heapsort algorithm (p. 159)
• 6.5 Priority queues (p. 162)
• 7 Quicksort (p. 170)
• 7.1 Description of quicksort (p. 170)
• 7.2 Performance of quicksort (p. 174)
• 7.3 A randomized version of quicksort (p. 179)
• 7.4 Analysis of quicksort (p. 180)
• 8 Sorting in Linear Time (p. 191)
• 8.1 Lower bounds for sorting (p. 191)
• 8.2 Counting sort (p. 194)
• 8.3 Radix sort (p. 197)
• 8.4 Bucket sort (p. 200)
• 9 Medians and Order Statistics (p. 213)
• 9.1 Minimum and maximum (p. 214)
• 9.2 Selection in expected linear time (p. 215)
• 9.3 Selection in worst-case linear time (p. 220)
• III Data Structures
• Introduction (p. 229)
• 10 Elementary Data Structures (p. 232)
• 10.1 Stacks and queues (p. 232)
• 10.2 Linked lists (p. 236)
• 10.3 Implementing pointers and objects (p. 241)
• 10.4 Representing rooted trees (p. 246)
• 11 Hash Tables (p. 253)
• 11.1 Direct-address tables (p. 254)
• 11.2 Hash tables (p. 256)
• 11.3 Hash functions (p. 262)
• 11.4 Open addressing (p. 269)
• 11.5 Perfect hashing (p. 277)
• 12 Binary Search Trees (p. 286)
• 12.1 What is a binary search tree? (p. 286)
• 12.2 Querying a binary search tree (p. 289)
• 12.3 Insertion and deletion (p. 294)
• 12.4 Randomly built binary search trees (p. 299)
• 13 Red-Black Trees (p. 308)
• 13.1 Properties of red-black trees (p. 308)
• 13.2 Rotations (p. 312)
• 13.3 Insertion (p. 315)
• 13.4 Deletion (p. 323)
• 14 Augmenting Data Structures (p. 339)
• 14.1 Dynamic order statistics (p. 339)
• 14.2 How to augment a data structure (p. 345)
• 14.3 Interval trees (p. 348)
• IV Advanced Design and Analysis Techniques
• Introduction (p. 357)
• 15 Dynamic Programming (p. 359)
• 15.1 Rod cutting (p. 360)
• 15.2 Matrix-chain multiplication (p. 370)
• 15.3 Elements of dynamic programming (p. 378)
• 15.4 Longest common subsequence (p. 390)
• 15.5 Optimal binary search trees (p. 397)
• 16 Greedy Algorithms (p. 414)
• 16.1 An activity-selection problem (p. 415)
• 16.2 Elements of the greedy strategy (p. 423)
• 16.3 Huffman codes (p. 428)
• 16.4 Matroids and greedy methods (p. 437)
• 16.5 A task-scheduling problem as a matroid (p. 443)
• 17 Amortized Analysis (p. 451)
• 17.1 Aggregate analysis (p. 452)
• 17.2 The accounting method (p. 456)
• 17.3 The potential method (p. 459)
• 17.4 Dynamic tables (p. 463)
• V Advanced Data Structures
• Introduction (p. 481)
• 18 B-Trees (p. 484)
• 18.1 Definition of B-trees (p. 488)
• 18.2 Basic operations on B-trees (p. 491)
• 18.3 Deleting a key from a B-tree (p. 499)
• 19 Fibonacci Heaps (p. 505)
• 19.1 Structure of Fibonacci heaps (p. 507)
• 19.2 Mergeable-heap operations (p. 510)
• 19.3 Decreasing a key and deleting a node (p. 518)
• 19.4 Bounding the maximum degree (p. 523)
• 20 van Emde Boas Trees (p. 531)
• 20.1 Preliminary approaches (p. 532)
• 20.2 A recursive structure (p. 536)
• 20.3 The van Emde Boas tree (p. 545)
• 21 Data Structures for Disjoint Sets (p. 561)
• 21.1 Disjoint-set operations (p. 561)
• 21.2 Linked-list representation of disjoint sets (p. 564)
• 21.3 Disjoint-set forests (p. 568)
• 21.4 Analysis of union by rank with path compression (p. 573)
• VI Graph Algorithms
• Introduction (p. 587)
• 22 Elementary Graph Algorithms (p. 589)
• 22.1 Representations of graphs (p. 589)
• 22.2 Breadth-first search (p. 594)
• 22.3 Depth-first search (p. 603)
• 22.4 Topological sort (p. 612)
• 22.5 Strongly connected components (p. 615)
• 23 Minimum Spanning Trees (p. 624)
• 23.1 Growing a minimum spanning tree (p. 625)
• 23.2 The algorithms of Kruskal and Prim (p. 631)
• 24 Single-Source Shortest Paths (p. 643)
• 24.1 The Bellman-Ford algorithm (p. 651)
• 24.2 Single-source shortest paths in directed acyclic graphs (p. 655)
• 24.3 Dijkstra's algorithm (p. 658)
• 24.4 Difference constraints and shortest paths (p. 664)
• 24.5 Proofs of shortest-paths properties (p. 671)
• 25 All-Pairs Shortest Paths (p. 684)
• 25.1 Shortest paths and matrix multiplication (p. 686)
• 25.2 The Floyd-Warshall algorithm (p. 693)
• 25.3 Johnson's algorithm for sparse graphs (p. 700)
• 26 Maximum Flow (p. 708)
• 26.1 Flow networks (p. 709)
• 26.2 The Ford-Fulkerson method (p. 714)
• 26.3 Maximum bipartite matching (p. 732)
• 26.4 Push-relabel algorithms (p. 736)
• 26.5 The relabel-to-front algorithm (p. 748)
• VII Selected Topics
• Introduction (p. 769)
• 27 Multithreaded Algorithms (p. 772)
• 27.1 The basics of dynamic multithreading (p. 774)
• 27.2 Multithreaded matrix multiplication (p. 792)
• 27.3 Multithreaded merge sort (p. 797)
• 28 Matrix Operations (p. 813)
• 28.1 Solving systems of linear equations (p. 813)
• 28.2 Inverting matrices (p. 827)
• 28.3 Symmetric positive-definite matrices and least-squares approximation (p. 832)
• 29 Linear Programming (p. 843)
• 29.1 Standard and slack forms (p. 850)
• 29.2 Formulating problems as linear programs (p. 859)
• 29.3 The simplex algorithm (p. 864)
• 29.4 Duality (p. 879)
• 29.5 The initial basic feasible solution (p. 886)
• 30 Polynomials and the FFT (p. 898)
• 30.1 Representing polynomials (p. 900)
• 30.2 The DFT and FFT (p. 906)
• 30.3 Efficient FFT implementations (p. 915)
• 31 Number-Theoretic Algorithms (p. 926)
• 31.1 Elementary number-theoretic notions (p. 927)
• 31.2 Greatest common divisor (p. 933)
• 31.3 Modular arithmetic (p. 939)
• 31.4 Solving modular linear equations (p. 946)
• 31.5 The Chinese remainder theorem (p. 950)
• 31.6 Powers of an element (p. 954)
• 31.7 The RSA public-key cryptosystem (p. 958)
• 31.8 Primality testing (p. 965)
• 31.9 Integer factorization (p. 975)
• 32 String Matching (p. 985)
• 32.1 The naive string-matching algorithm (p. 988)
• 32.2 The Rabin-Karp algorithm (p. 990)
• 32.3 String matching with finite automata (p. 995)
• 32.4 The Knuth-Morris-Pratt algorithm (p. 1002)
• 33 Computational Geometry (p. 1014)
• 33.1 Line-segment properties (p. 1015)
• 33.2 Determining whether any pair of segments intersects (p. 1021)
• 33.3 Finding the convex hull (p. 1029)
• 33.4 Finding the closest pair of points (p. 1039)
• 34 NP-Completeness (p. 1048)
• 34.1 Polynomial time (p. 1053)
• 34.2 Polynomial-time verification (p. 1061)
• 34.3 NP-completeness and reducibility (p. 1067)
• 34.4 NP-completeness proofs (p. 1078)
• 34.5 NP-complete problems (p. 1086)
• 35 Approximation Algorithms (p. 1106)
• 35.1 The vertex-cover problem (p. 1108)
• 35.2 The traveling-salesman problem (p. 1111)
• 35.3 The set-covering problem (p. 1117)
• 35.4 Randomization and linear programming (p. 1123)
• 35.5 The subset-sum problem (p. 1128)
• VIII Appendix: Mathematical Background
• Introduction (p. 1143)
• A Summations (p. 1145)
• A.1 Summation formulas and properties (p. 1145)
• A.2 Bounding summations (p. 1149)
• B Sets, Etc. (p. 1158)
• B.1 Sets (p. 1158)
• B.2 Relations (p. 1163)
• B.3 Functions (p. 1166)
• B.4 Graphs (p. 1168)
• B.5 Trees (p. 1173)
• C Counting and Probability (p. 1183)
• C.1 Counting (p. 1183)
• C.2 Probability (p. 1189)
• C.3 Discrete random variables (p. 1196)
• C.4 The geometric and binomial distributions (p. 1201)
• C.5 The tails of the binomial distribution (p. 1208)
• D Matrices (p. 1217)
• D.1 Matrices and matrix operations (p. 1217)
• D.2 Basic matrix properties (p. 1222)
• Bibliography (p. 1231)
• Index (p. 1251)

Author notes provided by Syndetics

Cormen is one of the authors of Introduction to Algorithms.

(Bowker Author Biography)