## Capítulos | ||

CLR | CLRS | CHAPTER |

1 | The Role of Algorithms in Computing | |

1 | 2 | Introduction || Getting Started |

2 | 3 | Growths of functions |

3 | A | Summations |

6 | C | Counting and Probability |

4 | 4 | Recurrences [& master method] |

5 | B | Sets & Graphs |

6.6 | 5 | Probabilistic Analysis and Randomized Algorithms |

7 | 6 | Heapsort |

8 | 7 | Quicksort |

9 | 8 | Sorting in linear time |

10 | 9 | Medians and order statistics |

13 | 12 | Binary Search Trees |

16 | 15 | Dynamic programming |

17 | 16 | Greedy algorithms |

18 | 17 | Amortized analysis |

19 | 18 | B-trees |

20 | 19 | Binomial heaps |

21 | 20 | Fibonacci heaps |

22 | 21 | Data Structures for Disjoint Sets |

23 | 22 | Elementary gragh algorithms [BFS & DFS] |

24 | 23 | Minimum spanning trees |

25 | 24 | Single-source shortest paths [Dijkstra] |

31 | 28 | Matrix operations |

36 | 34 | NP-completeness |

## Seções | ||

CLR | CLRS | OBS |

2.2 | 3.2 | Standard notations and common functions |

3.1 | A.1 | Summation formulas and properties [arithmetic progressions] |

6.1 | C.1 | Counting |

6.2 | C.2 | Probability |

6.3 | C.3 | Discrete Random Variables |

- | 5.1 | Hiring problem |

- | 5.2 | Indicator random variables |

- | 5.3 | Randomized algorithms |

6.6 | 5.4 | Probabilistic Analysis |

1.1 | 2.1 | |

1.2 | 2.2 | |

1.3 | 2.3 | |

2.1 | 3.1 | Asymptotic notation |

2.2 | 3.3 | Standard notations and common functions |

4.1 | 4.1 | |

4.2 | 4.2 | |

22.1 | 21.1 | Disjoint-set operations |

22.2 | 21.2 | Linked-list representation of disjoint sets |

22.3 | 21.3 | Disjoint-set forests |

22.4 | 21.4 | Analysis of union by rank with path compression |

## Exercícios | |

CLR | CLRS |

1.1-3 | 2.1-3 |

1.2-1 | 2.2-1 |

1.3-2 | 2.3.1 |

1.3-3 | |

1.3-4 | 2.3-4 |

1.3-5 | 2.3-5 |

1.3-6 | |

1.3-7 | |

1.4-1 | |

2.2-7 | |

3.2-2 | |

2.1-2 | |

2.1-3 | 3.1-3 |

2.1-4 | |

3.2-6 | |

2-3 | |

2-4 | |

4.2-1 | |

4-5 | |

4.1-1 | |

4.1-2 | |

4.3-1 | |

5.2-2 | |

5.2-3 | |

5.3-4 | |

6-2 | |

6.3-2 | C.3-2 |

7.1-1 | |

7.1-2 | 6.1-2 |

7.1-4 | 6.1-4 |

6.1-7 | |

7.2-4 | 6.2-4 |

7.2-5 | |

7.3-3 | 6.3-3 |

6.5-5 | |

7.5-5 | 6.5-7 |

7.5-6 | |

7-1 | |

6-3 | |

7.1-3 | |

8.2-1 | 7.2-2 |

8.2-2 | 7.2-3 |

8.4-2 | 7.4-3 |

8.4-2 | 7.4-1 |

8-4 | 7-4 |

8.4.2 | 7-2 |

8-3 | 7-3 |

9.1-1 | 8.1-1 |

9.1-2 | 8.1-2 |

9.1-3 | |

9.1-4 | |

9.1-5 | 8.?-? |

10.1-2 | 9.1-1 |

9.2-2 | |

10.1-1 | |

10.2-1 | 9.2-3 |

10.3-3 | |

10.3-8 | 9.3-8 |

13.1-3 | 12.1-3 |

13.1-4 | 12.1-4 |

16.3-4 | 15.4-4 |

16.3-5 | 15.4-5 |

16.3-6 | |

16-2 | 15-2 |

16-3 | 15-3a |

16-5 | |

17.1-1 | 16.1-1 |

17.1-3 | 16.1-4 |

17.1-2 | 16.1-3 |

17.2-1 | |

17.2-2 | |

17.2-5 | |

17.2-2 | 16.2-2 |

17-2 | |

17-3 | 16-4 |

16.1-2 | |

17.1-2 | 16.1-3 |

17-3 | 16-4 |

18.1-3 | 17.1-3 |

18.2-2 | 17.2-2 |

18.2-3 | |

18.3-2 | 17.3-2 |

18.3-3 | 17.3-3 |

18.3-6 | 17.3-6 |

18-2 | 17-2 |

22.3-1 | 21.3-1 |

22.3-2 | 21.3-2 |

Corol 22.5 | 21.4-2 |

22.4-3 | 21.4-4 |

23.4-5 | 22.4-5 |

23.5-1 | 22.5-1 |

22.5-2 | |

23.5-3 | 22.5-3 |

24.1-3 | 23.1-3 |

24.1-9 | 23.1-9 |

24.2-2 | 23.2-2 |

24.2 | |

25.?-? | 24.3-2 |

36.2-3 |

CLRS INTRODUCTION TO ALGORITHMS, Second Edition Table of Contents Preface I Foundations 1 The Role of Algorithms in Computing 1.1 Algorithms 1.2 Algorithms as a technology 2 Getting Started 2.1 Insertion sort 2.2 Analyzing algorithms 2.3 Designing Algorithms 3 Growth of Functions 3.1 Asymptotic notation 3.2 Standard notations and common functions 4 Recurrences 4.1 The substitution method 4.2 The recursion-tree method 4.3 The master method 4.4 Proof of the master theorem 5 Probabilistic Analysis and Randomized Algorithms 5.1 The hiring problem 5.2 Indicator random variables 5.3 Randomized algorithms 5.4 Probabilistic analysis and further uses of indicator random variables II Sorting and Order Statistics 6 Heapsort 6.1 Heaps 6.2 Maintaining the heap property 6.3 Building a heap 6.4 The heapsort algorithm 6.5 Priority queues 7 Quicksort 7.1 Description of quicksort 7.2 Performance of quicksort 7.3 Randomized versions of quicksort 7.4 Analysis of quicksort 8 Sorting in Linear Time 8.1 Lower bounds for sorting 8.2 Counting sort 8.3 Radix sort 8.4 Bucket sort 9 Medians and Order Statistics 9.1 Minimum and maximum 9.2 Selection in expected linear time 9.3 Selection in worst-case linear time III Data Structures 10 Elementary Data Structures 10.1 Stacks and queues 10.2 Linked lists 10.3 Implementing pointers and objects 10.4 Representing rooted trees 11 Hash Tables 11.1 Direct-address tables 11.2 Hash tables 11.3 Hash functions 11.4 Open addressing 11.5 Perfect hashing 12 Binary Search Trees 12.1 What is a binary search tree? 12.2 Querying a binary search tree 12.3 Insertion and deletion 12.4 Randomly built binary search trees 13 Red-Black Trees 13.1 Properties of red-black trees 13.2 Rotations 13.3 Insertion 13.4 Deletion 14 Augmenting Data Structures 14.1 Dynamic order statistics 14.2 How to augment a data structure 14.3 Interval trees IV Advanced Design and Analysis Techniques 15 Dynamic Programming 15.1 Assembly-line scheduling 15.2 Matrix-chain multiplication 15.3 Elements of dynamic programming 15.4 Longest common subsequence 15.5 Optimal binary search trees 16 Greedy Algorithms 16.1 An activity-selection problem 16.2 Elements of the greedy strategy 16.3 Huffman codes 16.4 Theoretical foundations for greedy methods 16.5 A task-scheduling problem 17 Amortized Analysis 17.1 Aggregate analysis 17.2 The accounting method 17.3 The potential method 17.4 Dynamic tables V Advanced Data Structures 18 B-Trees 18.1 Definition of B-trees 18.2 Basic operations on B-trees 18.3 Deleting a key from a B-tree 19 Binomial Heaps 19.1 Binomial trees and binomial heaps 19.2 Operations on binomial heaps 20 Fibonacci Heaps 20.1 Structure of Fibonacci heaps 20.2 Mergeable-heap operations 20.3 Decreasing a key and deleting a node 20.4 Bounding the maximum degree 21 Data Structures for Disjoint Sets 21.1 Disjoint-set operations 21.2 Linked-list representation of disjoint sets 21.3 Disjoint-set forests 21.4 Analysis of union by rank with path compression VI Graph Algorithms 22 Elementary Graph Algorithms 22.1 Representations of graphs 22.2 Breadth-first search 22.3 Depth-first search 22.4 Topological sort 22.5 Strongly connected components 23 Minimum Spanning Trees 23.1 Growing a minimum spanning tree 23.2 The algorithms of Kruskal and Prim 24 Single-Source Shortest Paths 24.1 The Bellman-Ford algorithm 24.2 Single-source shortest paths in directed acyclic graphs 24.3 Dijkstra's algorithm 24.4 Difference constraints and shortest paths 24.5 Proofs of shortest-paths properties 25 All-Pairs Shortest Paths 25.1 Shortest paths and matrix multiplication 25.2 The Floyd-Warshall algorithm 25.3 Johnson's algorithm for sparse graphs 26 Maximum Flow 26.1 Flow networks 26.2 The Ford-Fulkerson method 26.3 Maximum bipartite matching 26.4 Push-relabel algorithms 26.5 The relabel-to-front algorithm VII Selected Topics 27 Sorting Networks 27.1 Comparison networks 27.2 The zero-one principle 27.3 A bitonic sorting network 27.4 A merging network 27.5 A sorting network 28 Matrix Operations 28.1 Properties of matrices 28.2 Strassen's algorithm for matrix multiplication 28.3 Solving systems of linear equations 28.4 Inverting matrices 28.5 Symmetric positive-definite matrices and least-squares approximation 29 Linear Programming 29.1 Standard and slack forms 29.2 Formulating problems as linear programs 29.3 The simplex algorithm 29.4 Duality 29.5 The initial basic feasible solution 30 Polynomials and the FFT 30.1 Representation of polynomials 30.2 The DFT and FFT 30.3 Efficient FFT implementations 31 Number-Theoretic Algorithms 31.1 Elementary number-theoretic notions 31.2 Greatest common divisor 31.3 Modular arithmetic 31.4 Solving modular linear equations 31.5 The Chinese remainder theorem 31.6 Powers of an element 31.7 The RSA public-key cryptosystem 31.8 Primality testing 31.9 Integer factorization 32 String Matching 32.1 The naive string-matching algorithm 32.2 The Rabin-Karp algorithm 32.3 String matching with finite automata 32.4 The Knuth-Morris-Pratt algorithm 33 Computational Geometry 33.1 Line-segment properties 33.2 Determining whether any pair of segments intersects 33.3 Finding the convex hull 33.4 Finding the closest pair of points 34 NP-Completeness 34.1 Polynomial time 34.2 Polynomial-time verification 34.3 NP-completeness and reducibility 34.4 NP-completeness proofs 34.5 NP-complete problems 35 Approximation Algorithms 35.1 The vertex-cover problem 35.2 The traveling-salesman problem 35.3 The set-covering problem 35.4 Randomization and linear programming 35.4 The subset-sum problem VIII Appendix: Mathematical Background A Summations A.1 Summation formulas and properties A.2 Bounding summations B Sets, Etc. B.1 Sets B.2 Relations B.3 Functions B.4 Graphs B.5 Trees C Counting and Probability C.1 Counting C.2 Probability C.3 Discrete random variables C.4 The geometric and binomial distributions C.5 The tails of the binomial distribution Bibliography Index (created by the authors)