CLRS Solutions
7 3
Initializing search
icefox-saber/CLRS
CLRS Solutions
icefox-saber/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
1-1 Comparison of running times
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 Characterizing Running Times
3 Characterizing Running Times
3.1 O-notation, $\Omega$-notation, and $\Theta$-notation
3.2Asymptotic notation formal definitions
3.3 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 Manipulating asymptotic notation
3-6 Variations on $O$ and $\Omega$
3-7 Iterated functions
4 Divide-and-Conquer
4 Divide-and-Conquer
4.1 Multiplying square matrices
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
$\star$ 4.6 Proof of the continuous master theorem
$\star$ 4.7 Akra-Bazzi recurrences
Chap 4 Problems
Chap 4 Problems
4-1 Recurrence examples
4-2 Parameter-passing costs
4-3 Solving recurrences with a change of variables
4-4 More recurrence examples
4-5 Fibonacci numbers
4-6 Chip testing
4-7 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 Probabilistic 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
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
7 4
7 5
7 6
7 7
7 3