Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
Purchase Benefits
What is included with this book?
Preface | p. xiii |
Foundations | |
Introduction | p. 3 |
The Role of Algorithms in Computing | p. 5 |
Algorithms | p. 5 |
Algorithms as a technology | p. 11 |
Getting Started | p. 16 |
Insertion sort | p. 16 |
Analyzing algorithms | p. 23 |
Designing algorithms | p. 29 |
Growth of Functions | p. 43 |
Asymptotic notation | p. 43 |
Standard notations and common functions | p. 53 |
Divide-and-Conquer | p. 65 |
The maximum-subarray problem | p. 68 |
Strassen's algorithm for matrix multiplication | p. 75 |
The substitution method for solving recurrences | p. 83 |
The recursion-tree method for solving recurrences | p. 88 |
The master method for solving recurrences | p. 93 |
Proof of the master theorem | p. 97 |
Probabilistic Analysis and Randomized Algorithms | p. 114 |
The hiring problem | p. 114 |
Indicator random variables | p. 118 |
Randomized algorithms | p. 122 |
Probabilistic analysis and further uses of indicator random variables | p. 130 |
Sorting and Order Statistics | |
Introduction | p. 147 |
Heapsort | p. 151 |
Heaps | p. 151 |
Maintaining the heap property | p. 154 |
Building a heap | p. 156 |
The heapsort algorithm | p. 159 |
Priority queues | p. 162 |
Quicksort | p. 170 |
Description of quicksort | p. 170 |
Performance of quicksort | p. 174 |
A randomized version of quicksort | p. 179 |
Analysis of quicksort | p. 180 |
Sorting in Linear Time | p. 191 |
Lower bounds for sorting | p. 191 |
Counting sort | p. 194 |
Radix sort | p. 197 |
Bucket sort | p. 200 |
Medians and Order Statistics | p. 213 |
Minimum and maximum | p. 214 |
Selection in expected linear time | p. 215 |
Selection in worst-case linear time | p. 220 |
Data Structures | |
Introduction | p. 229 |
Elementary Data Structures | p. 232 |
Stacks and queues | p. 232 |
Linked lists | p. 236 |
Implementing pointers and objects | p. 241 |
Representing rooted trees | p. 246 |
Hash Tables | p. 253 |
Direct-address tables | p. 254 |
Hash tables | p. 256 |
Hash functions | p. 262 |
Open addressing | p. 269 |
Perfect hashing | p. 277 |
Binary Search Trees | p. 286 |
What is a binary search tree? | p. 286 |
Querying a binary search tree | p. 289 |
Insertion and deletion | p. 294 |
Randomly built binary search trees | p. 299 |
Red-Black Trees | p. 308 |
Properties of red-black trees | p. 308 |
Rotations | p. 312 |
Insertion | p. 315 |
Deletion | p. 323 |
Augmenting Data Structures | p. 339 |
Dynamic order statistics | p. 339 |
How to augment a data structure | p. 345 |
Interval trees | p. 348 |
Advanced Design and Analysis Techniques | |
Introduction | p. 357 |
Dynamic Programming | p. 359 |
Rod cutting | p. 360 |
Matrix-chain multiplication | p. 370 |
Elements of dynamic programming | p. 378 |
Longest common subsequence | p. 390 |
Optimal binary search trees | p. 397 |
Greedy Algorithms | p. 414 |
An activity-selection problem | p. 415 |
Elements of the greedy strategy | p. 423 |
Huffman codes | p. 428 |
Matroids and greedy methods | p. 437 |
A task-scheduling problem as a matroid | p. 443 |
Amortized Analysis | p. 451 |
Aggregate analysis | p. 452 |
The accounting method | p. 456 |
The potential method | p. 459 |
Dynamic tables | p. 463 |
Advanced Data Structures | |
Introduction | p. 481 |
B-Trees | p. 484 |
Definition of B-trees | p. 488 |
Basic operations on B-trees | p. 491 |
Deleting a key from a B-tree | p. 499 |
Fibonacci Heaps | p. 505 |
Structure of Fibonacci heaps | p. 507 |
Mergeable-heap operations | p. 510 |
Decreasing a key and deleting a node | p. 518 |
Bounding the maximum degree | p. 523 |
van Emde Boas Trees | p. 531 |
Preliminary approaches | p. 532 |
A recursive structure | p. 536 |
The van Emde Boas tree | p. 545 |
Data Structures for Disjoint Sets | p. 561 |
Disjoint-set operations | p. 561 |
Linked-list representation of disjoint sets | p. 564 |
Disjoint-set forests | p. 568 |
Analysis of union by rank with path compression | p. 573 |
Graph Algorithms | |
Introduction | p. 587 |
Elementary Graph Algorithms | p. 589 |
Representations of graphs | p. 589 |
Breadth-first search | p. 594 |
Depth-first search | p. 603 |
Topological sort | p. 612 |
Strongly connected components | p. 615 |
Minimum Spanning Trees | p. 624 |
Growing a minimum spanning tree | p. 625 |
The algorithms of Kruskal and Prim | p. 631 |
Single-Source Shortest Paths | p. 643 |
The Bellman-Ford algorithm | p. 651 |
Single-source shortest paths in directed acyclic graphs | p. 655 |
Dijkstra's algorithm | p. 658 |
Difference constraints and shortest paths | p. 664 |
Proofs of shortest-paths properties | p. 671 |
All-Pairs Shortest Paths | p. 684 |
Shortest paths and matrix multiplication | p. 686 |
The Floyd-Warshall algorithm | p. 693 |
Johnson's algorithm for sparse graphs | p. 700 |
Maximum Flow | p. 708 |
Flow networks | p. 709 |
The Ford-Fulkerson method | p. 714 |
Maximum bipartite matching | p. 732 |
Push-relabel algorithms | p. 736 |
The relabel-to-front algorithm | p. 748 |
Selected Topics | |
Introduction | p. 769 |
Multithreaded Algorithms | p. 772 |
The basics of dynamic multithreading | p. 774 |
Multithreaded matrix multiplication | p. 792 |
Multithreaded merge sort | p. 797 |
Matrix Operations | p. 813 |
Solving systems of linear equations | p. 813 |
Inverting matrices | p. 827 |
Symmetric positive-definite matrices and least-squares approximation | p. 832 |
Linear Programming | p. 843 |
Standard and slack forms | p. 850 |
Formulating problems as linear programs | p. 859 |
The simplex algorithm | p. 864 |
Duality | p. 879 |
The initial basic feasible solution | p. 886 |
Polynomials and the FFT | p. 898 |
Representing polynomials | p. 900 |
The DFT and FFT | p. 906 |
Efficient FFT implementations | p. 915 |
Number-Theoretic Algorithms | p. 926 |
Elementary number-theoretic notions | p. 927 |
Greatest common divisor | p. 933 |
Modular arithmetic | p. 939 |
Solving modular linear equations | p. 946 |
The Chinese remainder theorem | p. 950 |
Powers of an element | p. 954 |
The RSA public-key cryptosystem | p. 958 |
Primality testing | p. 965 |
Integer factorization | p. 975 |
String Matching | p. 985 |
The naive string-matching algorithm | p. 988 |
The Rabin-Karp algorithm | p. 990 |
String matching with finite automata | p. 995 |
The Knuth-Morris-Pratt algorithm | p. 1002 |
Computational Geometry | p. 1014 |
Line-segment properties | p. 1015 |
Determining whether any pair of segments intersects | p. 1021 |
Finding the convex hull | p. 1029 |
Finding the closest pair of points | p. 1039 |
NP-Completeness | p. 1048 |
Polynomial time | p. 1053 |
Polynomial-time verification | p. 1061 |
NP-completeness and reducibility | p. 1067 |
NP-completeness proofs | p. 1078 |
NP-complete problems | p. 1086 |
Approximation Algorithms | p. 1106 |
The vertex-cover problem | p. 1108 |
The traveling-salesman problem | p. 1111 |
The set-covering problem | p. 1117 |
Randomization and linear programming | p. 1123 |
The subset-sum problem | p. 1128 |
Appendix: Mathematical Background | |
Introduction | p. 1143 |
Summations | p. 1145 |
Summation formulas and properties | p. 1145 |
Bounding summations | p. 1149 |
Sets, Etc. | p. 1158 |
Sets | p. 1158 |
Relations | p. 1163 |
Functions | p. 1166 |
Graphs | p. 1168 |
Trees | p. 1173 |
Counting and Probability | p. 1183 |
Counting | p. 1183 |
Probability | p. 1189 |
Discrete random variables | p. 1196 |
The geometric and binomial distributions | p. 1201 |
The tails of the binomial distribution | p. 1208 |
Matrices | p. 1217 |
Matrices and matrix operations | p. 1217 |
Basic matrix properties | p. 1222 |
Bibliography | p. 1231 |
Index | p. 1251 |
Table of Contents provided by Publisher. All Rights Reserved. |