Introduction to algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest.

CONTENIDO
Chapter 1
Introduction 1
Algorithms 1
Analyzing algorithms 6
Designing algorithms 11
Summary 16
Part I: Mathematical Foundations
Introduction 21
Chapter 2
Growth of Functions 23
Asymptotic notation 23
Standard notations and common functions 32
Chapter 3
Summations 42
Summation formulas and properties 42
Bounding summations 46
Chapter 4
Recurrences 53
The substitution method 54
The iteration method 58
The master method 61
Proof of the master theorem 64
Chapter 5
Sets, Etc. 77
Sets 77
Relations 81
Functions 84
Graphs 86
Trees 91
Chapter 6
Counting and Probability 99
Counting 99
Probability 104
Discrete random variables 111
The geometric and binomial distributions 115
The tails of the binomial distribution 121
Probabilistic analysis 126
Part II: Sorting and Order Statistics
Introduction 137
Chapter 7
Heapsort 140
Heaps 140
Maintaining the heap property 142
Building a heap 145
The heapsort algorithm 147
Priority queues 149
Chapter 8
Quicksort 153
Description of quicksort 153
Performance of quicksort 156
Randomized versions of quicksort 161
Analysis of quicksort 163
Chapter 9
Sorting in Linear Time 172
Lower bounds for sorting 172
Counting sort 175
Radix sort 178
Bucket sort 180
Chapter 10
Medians and Order Statistics 185
Minimum and maximum 185
Selection in expected linear time 187
Selection in worst-case linear time 189
Part III: Data Structures
Introduction 197
Chapter 11
Elementary Data Structures 200
Stacks and queues 200
Linked lists 204
Implementing pointers and objects 209
Representing rooted trees 213
Chapter 12
Hash Tables 219
Direct-address tables 219
Hash tables 221
Hash functions 226
Open addressing 232
Chapter 13
Binary Search Trees 244
What is a binary search tree? 244
Querying a binary search tree 246
Insertion and deletion 250
Randomly built binary search trees 254
Chapter 14
Red-Black Trees 263
Properties of red-black trees 263
Rotations 265
Insertion 268
Deletion 272
Chapter 15
Augmenting Data Structures 281
Dynamic order statistics 281
How to augment a data structure 287
Interval trees 290
Part IV: Advanced Design and Analysis Techniques Introduction
Chapter 16
Dynamic Programming 301
Matrix-chain multiplication 302
Elements of dynamic programming 309
Longest common subsequence 314
Optimal polygon triangulation 320
Chapter 17
Greedy Algorithms 329
An activity-selection problem 329
Elements of the greedy strategy 333
Huffman codes 337
Theoretical foundations for greedy methods 345
A task-scheduling problem 350
Chapter 18
Amortized Analysis 356
The aggregate method 357
The accounting method 360
The potential method 363
Dynamic tables 367
Part V Advanced Data Structures
Introduction 379
Chapter 19
B-Trees 381
Definition of B-trees 384
Basic operations on B-trees 387
Deleting a key from a B-tree 395
Chapter 20
Binomial Heaps 400
Binomial trees and binomial heaps 401
Operations on binomial heaps 406
Chapter 21
Fibonacci Heaps 420
Structure of Fibonacci heaps 421
Mergeable-heap operations 423
Decreasing a key and deleting a node 431
Bounding the maximum degree 435
Chapter 22
Data Structures for Disjoint Sets 440
Disjoint-set operations 440
Linked-list representation of disjoint sets 443
Disjoint-set forests 446
Analysis of union by rank with path compression 450
Part VI: Graph Algorithms
Introduction 463
Chapter 23
Elementary Graph Algorithms 465
Representations of graphs 465
Breadth-first search 469
Depth-first search 477
Topological sort 485
Strongly connected components 488
Chapter 24
Minimum Spanning Trees 498
Growing a minimum spanning tree 499
The algorithms of Kruskal and Prim 504
Chapter 25
Single-Source Shortest Paths 514
Shortest paths and relaxation 518
Dijkstra's algorithm 527
The Bellman-Ford algorithm 532
Single-source shortest paths in directed acyclic graphs 536
Difference constraints and shortest paths 539
Chapter 26
All-Pairs Shortest Paths 550
Shortest paths and matrix multiplication 552
The Floyd-Warshall algorithm 558
Johnson's algorithm for sparse graphs 565
A general framework for solving path problems in directedgraphs 570
Chapter 27
Maximum Flow 579
Flow networks 580
The Ford-Fulkerson method 587
Maximum bipartite matching 600
Preflow-push algorithms 605
The lift-to-front algorithm 615
Part VII: Selected Topics
Introduction 631
Chapter 28
Sorting Networks 634
Comparison networks 634
The zero-one principle 639
A bitonic sorting network 642
A merging network 646
A sorting network 648
Chapter 29
Arithmetic Circuits 654
Combinational circuits 655
Addition circuits 660
Multiplication circuits 671
Clocked circuits 678
Chapter 30
Algorithms for Parallel Computers 688
Pointer jumping 692
CRCW algorithms versus EREW algorithms 701
Brent's theorem and work efficiency 709
Work-efficient parallel prefix computation 714
Deterministic symmetry breaking 720
Chapter 31
Matrix Operations 730
Properties of matrices 730
Strassen's algorithm for matrix multiplication 739
Algebraic number systems and boolean matrix multiplication 745
Solving systems of linear equations 749
Inverting matrices 762
Symmetric positive-definite matrices and least-squares approximation 766
Chapter 32
Polynomials and the FFT 776
Representation of polynomials 778
The DFT and FFT 783
Efficient FFT implementations 791
Chapter 33
Number-Theoretic Algorithms 801
Elementary number-theoretic notions 802
Greatest common divisor 808
Modular arithmetic 814
Solving modular linear equations 820
The Chinese remainder theorem 823
Powers of an element 827
The RSA public-key cryptosystem 831
Primality testing 837
Integer factorization 844
Chapter 34
String Matching 853
The naive string-matching algorithm 855
The Rabin-Karp algorithm 857
String matching with finite automata 862
The Knuth-Morris-Pratt algorithm 869
The Boyer-Moore algorithm 876
Chapter 35
Computational Geometry 886
Line-segment properties 887
Determining whether any pair of segments intersects 892
Finding the convex hull 898
Finding the closest pair of points 908
Chapter 36
NP-Completeness 916
Polynomial time 917
Polynomial-time verification 924
NP-completeness and reducibility 929
NP-completeness proofs 939
NP-complete problems 946
Chapter 37
Approximation Algorithms 964
The vertex-cover problem 966
The traveling-salesman problem 969
The set-covering problem 974
The subset-sum problem 978
Bibliography 987
Index 997