CLRS Solutions
19.1 Structure of Fibonacci heaps
Initializing search
walkccc/CLRS
CLRS Solutions
walkccc/CLRS
Preface
I Foundations
I Foundations
1 The Role of Algorithms in Computing
1 The Role of Algorithms in Computing
1.1 Algorithms
1.2 Algorithms as a technology
Chap 1 Problems
Chap 1 Problems
Problem 1-1
2 Getting Started
2 Getting Started
2.1 Insertion sort
2.2 Analyzing algorithms
2.3 Designing algorithms
Chap 2 Problems
Chap 2 Problems
2-1 Insertion sort on small arrays in merge sort
2-2 Correctness of bubblesort
2-3 Correctness of Horner's rule
2-4 Inversions
3 Growth of Functions
3 Growth of Functions
3.1 Asymptotic notation
3.2 Standard notations and common functions
Chap 3 Problems
Chap 3 Problems
3-1 Asymptotic behavior of polynomials
3-2 Relative asymptotic growths
3-3 Ordering by asymptotic growth rates
3-4 Asymptotic notation properties
3-5 Variations on $O$ and $\Omega$
3-6 Iterated functions
4 Divide-and-Conquer
4 Divide-and-Conquer
4.1 The maximum-subarray problem
4.2 Strassen's algorithm for matrix multiplication
4.3 The substitution method for solving recurrences
4.4 The recursion-tree method for solving recurrences
4.5 The master method for solving recurrences
4.6 Proof of the master theorem
Chap 4 Problems
Chap 4 Problems
4-1 Recurrence examples
4-2 Parameter-passing costs
4-3 More recurrence examples
4-4 Fibonacci numbers
4-5 Chip testing
4-6 Monge arrays
5 Probabilistic Analysis and Randomized Algorithms
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
Chap 5 Problems
Chap 5 Problems
5-1 Probabilstic counting
5-2 Searching an unsorted array
II Sorting and Order Statistics
II Sorting and Order Statistics
6 Heapsort
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
Chap 6 Problems
Chap 6 Problems
6-1 Building a heap using insertion
6-2 Analysis of $d$-ary heaps
6-3 Young tableaus
7 Quicksort
7 Quicksort
7.1 Description of quicksort
7.2 Performance of quicksort
7.3 A randomized version of quicksort
7.4 Analysis of quicksort
Chap 7 Problems
Chap 7 Problems
7-1 Hoare partition correctness
7-2 Quicksort with equal element values
7-3 Alternative quicksort analysis
7-4 Stack depth for quicksort
7-5 Median-of-3 partition
7-6 Fuzzy sorting of intervals
8 Sorting in Linear Time
8 Sorting in Linear Time
8.1 Lower bounds for sorting
8.2 Counting sort
8.3 Radix sort
8.4 Bucket sort
Chap 8 Problems
Chap 8 Problems
8-1 Probabilistic lower bounds on comparison sorting
8-2 Sorting in place in linear time
8-3 Sorting variable-length items
8-4 Water jugs
8-5 Average sorting
8-6 Lower bound on merging sorted lists
8-7 The $0$-$1$ sorting lemma and columnsort
9 Medians and Order Statistics
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
Chap 9 Problems
Chap 9 Problems
9-1 Largest $i$ numbers in sorted order
9-2 Weighted median
9-3 Small order statistics
9-4 Alternative analysis of randomized selection
III Data Structures
III Data Structures
10 Elementary 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
Chap 10 Problems
Chap 10 Problems
10-1 Comparisons among lists
10-2 Mergeable heaps using linked lists
10-3 Searching a sorted compact list
11 Hash Tables
11 Hash Tables
11.1 Direct-address tables
11.2 Hash tables
11.3 Hash functions
11.4 Open addressing
11.5 Perfect hashing
Chap 11 Problems
Chap 11 Problems
11-1 Longest-probe bound for hashing
11-2 Slot-size bound for chaining
11-3 Quadratic probing
11-4 Hashing and authentication
12 Binary Search Trees
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
Chap 12 Problems
Chap 12 Problems
12-1 Binary search trees with equal keys
12-2 Radix trees
12-3 Average node depth in a randomly built binary search tree
12-4 Number of different binary trees
13 Red-Black Trees
13 Red-Black Trees
13.1 Properties of red-black trees
13.2 Rotations
13.3 Insertion
13.4 Deletion
Chap 13 Problems
Chap 13 Problems
13-1 Persistent dynamic sets
13-2 Join operation on red-black trees
13-3 AVL trees
13-4 Treaps
14 Augmenting Data Structures
14 Augmenting Data Structures
14.1 Dynamic order statistics
14.2 How to augment a data structure
14.3 Interval trees
Chap 14 Problems
Chap 14 Problems
14-1 Point of maximum overlap
14-2 Josephus permutation
IV Advanced Design and Analysis Techniques
IV Advanced Design and Analysis Techniques
15 Dynamic Programming
15 Dynamic Programming
15.1 Rod cutting
15.2 Matrix-chain multiplication
15.3 Elements of dynamic programming
15.4 Longest common subsequence
15.5 Optimal binary search trees
Chap 15 Problems
Chap 15 Problems
15-1 Longest simple path in a directed acyclic graph
15-2 Longest palindrome subsequence
15-3 Bitonic euclidean
15-4 Printing neatly
15-5 Edit distance
15-6 Planning a company party
15-7 Viterbi algorithm
15-8 Image compression by seam carving
15-9 Breaking a string
15-10 Planning an investment strategy
15-11 Inventory planning
15-12 Signing free-agent baseball players
16 Greedy Algorithms
16 Greedy Algorithms
16.1 An activity-selection problem
16.2 Elements of the greedy strategy
16.3 Huffman codes
16.4 Matroids and greedy methods
16.5 A task-scheduling problem as a matroid
Chap 16 Problems
Chap 16 Problems
16-1 Coin changing
16-2 Scheduling to minimize average completion time
16-3 Acyclic subgraphs
16-4 Scheduling variations
16-5 Off-line caching
17 Amortized Analysis
17 Amortized Analysis
17.1 Aggregate analysis
17.2 The accounting method
17.3 The potential method
17.4 Dynamic tables
Chap 17 Problems
Chap 17 Problems
17-1 Bit-reversed binary counter
17-2 Making binary search dynamic
17-3 Amortized weight-balanced trees
17-4 The cost of restructuring red-black trees
17-5 Competitive analysis of self-organizing lists with move-to-front
V Advanced Data Structures
V Advanced Data Structures
18 B-Trees
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
Chap 18 Problems
Chap 18 Problems
18-1 Stacks on secondary storage
18-2 Joining and splitting 2-3-4 trees
19 Fibonacci Heaps
19 Fibonacci Heaps
19.1 Structure of Fibonacci heaps
19.2 Mergeable-heap operations
19.3 Decreasing a key and deleting a node
19.4 Bounding the maximum degree
Chap 19 Problems
Chap 19 Problems
19-1 Alternative implementation of deletion
19-2 Binomial trees and binomial heaps
19-3 More Fibonacci-heap operations
19-4 2-3-4 heaps
20 van Emde Boas Trees
20 van Emde Boas Trees
20.1 Preliminary approaches
20.2 A recursive structure
20.3 The van Emde Boas tree
Chap 20 Problems
Chap 20 Problems
20-1 Space requirements for van Emde Boas trees
20-2 $y$-fast tries
21 Data Structures for Disjoint Sets
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
Chap 21 Problems
Chap 21 Problems
21-1 Off-line minimum
21-2 Depth determination
21-3 Tarjan's off-line least-common-ancestors algorithm
VI Graph Algorithms
VI Graph Algorithms
22 Elementary 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
Chap 22 Problems
Chap 22 Problems
22-1 Classifying edges by breadth-first search
22-2 Articulation points, bridges, and biconnected components
22-3 Euler tour
22-4 Reachability
23 Minimum Spanning Trees
23 Minimum Spanning Trees
23.1 Growing a minimum spanning tree
23.2 The algorithms of Kruskal and Prim
Chap 23 Problems
Chap 23 Problems
23-1 Second-best minimum spanning tree
23-2 Minimum spanning tree in sparse graphs
23-3 Bottleneck spanning tree
23-4 Alternative minimum-spanning-tree algorithms
24 Single-Source Shortest Paths
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
Chap 24 Problems
Chap 24 Problems
24-1 Yen's improvement to Bellman-Ford
24-2 Nesting boxes
24-3 Arbitrage
24-4 Gabow's scaling algorithm for single-source shortest paths
24-5 Karp's minimum mean-weight cycle algorithm
24-6 Bitonic shortest paths
25 All-Pairs Shortest Paths
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
Chap 25 Problems
Chap 25 Problems
25-1 Transitive closure of a dynamic graph
25-2 Shortest paths in epsilon-dense graphs
26 Maximum Flow
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
Chap 26 Problems
Chap 26 Problems
26-1 Escape problem
26-2 Minimum path cover
26-3 Algorithmic consulting
26-4 Updating maximum flow
26-5 Maximum flow by scaling
26-6 The Hopcroft-Karp bipartite matching algorithm
VII Selected Topics
VII Selected Topics
27 Multithreaded Algorithms
27 Multithreaded Algorithms
27.1 The basics of dynamic multithreading
27.2 Multithreaded matrix multiplication
27.3 Multithreaded merge sort
Chap 27 Problems
Chap 27 Problems
27-1 Implementing parallel loops using nested parallelism
27-2 Saving temporary space in matrix multiplication
27-3 Multithreaded matrix algorithms
27-4 Multithreading reductions and prefix computations
27-5 Multithreading a simple stencil calculation
27-6 Randomized multithreaded algorithms
28 Matrix Operations
28 Matrix Operations
28.1 Solving systems of linear equations
28.2 Inverting matrices
28.3 Symmetric positive-definite matrices and least-squares approximation
Chap 28 Problems
Chap 28 Problems
28-1 Tridiagonal systems of linear equations
28-2 Splines
29 Linear Programming
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
Chap 29 Problems
Chap 29 Problems
29-1 Linear-inequality feasibility
29-2 Complementary slackness
29-3 Integer linear programming
29-4 Farkas'ss lemma
29-5 Minimum-cost circulation
30 Polynomials and the FFT
30 Polynomials and the FFT
30.1 Representing polynomials
30.2 The DFT and FFT
30.3 Efficient FFT implementations
Chap 30 Problems
Chap 30 Problems
30-1 Divide-and-conquer multiplication
30-2 Toeplitz matrices
30-3 Multidimensional fast Fourier transform
30-4 Evaluating all derivatives of a polynomial at a point
30-5 Polynomial evaluation at multiple points
30-6 FFT using modular arithmetic
31 Number-Theoretic Algorithms
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
Chap 31 Problems
Chap 31 Problems
31-1 Binary gcd algorithm
31-2 Analysis of bit operations in Euclid's algorithm
31-3 Three algorithms for Fibonacci numbers
31-4 Quadratic residues
32 String Matching
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
Chap 32 Problems
Chap 32 Problems
32-1 String matching based on repetition factors
33 Computational Geometry
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
Chap 33 Problems
Chap 33 Problems
33-1 Convex layers
33-2 Maximal layers
33-3 Ghostbusters and ghosts
33-4 Picking up sticks
33-5 Sparse-hulled distributions
34 NP-Completeness
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
Chap 34 Problems
Chap 34 Problems
34-1 Independent set
34-2 Bonnie and Clyde
34-3 Graph coloring
34-4 Scheduling with profits and deadlines
35 Approximation Algorithms
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.5 The subset-sum problem
Chap 35 Problems
Chap 35 Problems
35-1 Bin packing
35-2 Approximating the size of a maximum clique
35-3 Weighted set-covering problem
35-4 Maximum matching
35-5 Parallel machine scheduling
35-6 Approximating a maximum spanning tree
35-7 An approximation algorithm for the 0-1 knapsack problem
19.1 Structure of Fibonacci heaps
There is no exercise in this section.