DSA

CLRS

1. 1.1 Algorithms 5
2. 1.2 Algorithms as a technology 12
3. 2.1 Insertion sort 17
4. 2.2 Analyzing algorithms 25
5. 2.3 Designing algorithms 34
6. 3.1 O-notation, Ω-notation, and ‚θ-notation 50
7. 3.2 Asymptotic notation: formal deûnitions 53
8. 3.3 Standard notations and common functions 63
9. 4.1 Multiplying square matrices 80
10. 4.2 Strassen’s algorithm for matrix multiplication 85
11. 4.3 The substitution method for solving recurrences 90
12. 4.4 The recursion-tree method for solving recurrences 95
13. 4.5 The master method for solving recurrences 101
14. 4.6 Proof of the continuous master theorem 107
15. 4.7 Akra-Bazzi recurrences 115
16. 5.1 The hiring problem 126
17. 5.2 Indicator random variables 130
18. 5.3 Randomized algorithms 134
19. 5.4 Probabilistic analysis and further uses of indicator random variables 140
20. 6.1 Heaps 161
21. 6.2 Maintaining the heap property 164
22. 6.3 Building a heap 167
23. 6.4 The heapsort algorithm 170
24. 6.5 Priority queues 172
25. 7.1 Description of quicksort 183
26. 7.2 Performance of quicksort 187
27. 7.3 A randomized version of quicksort 191
28. 7.4 Analysis of quicksort 193
29. 8.1 Lower bounds for sorting 205
30. 8.2 Counting sort 208
31. 8.3 Radix sort 211
32. 8.4 Bucket sort 215
33. 9.1 Minimum and maximum 228
34. 9.2 Selection in expected linear time 230
35. 9.3 Selection in worst-case linear time 236
36. 10.1 Simple array-based data structures: arrays, matrices, stacks, queues 252
37. 10.2 Linked lists 258
38. 10.3 Representing rooted trees 265
39. 11.1 Direct-address tables 273
40. 11.2 Hash tables 275
41. 11.3 Hash functions 282
42. 11.4 Open addressing 293
43. 11.5 Practical considerations 301
44. 12.1 What is a binary search tree? 312
45. 12.2 Querying a binary search tree 316
46. 12.3 Insertion and deletion 321
47. 13.1 Properties of red-black trees 331
48. 13.2 Rotations 335
49. 13.3 Insertion 338
50. 13.4 Deletion 346
51. 14.1 Rod cutting 363
52. 14.2 Matrix-chain multiplication 373
53. 14.3 Elements of dynamic programming 382
54. 14.4 Longest common subsequence 393
55. 14.5 Optimal binary search trees 400
56. 15.1 An activity-selection problem 418
57. 15.2 Elements of the greedy strategy 426
58. 15.3 Huffman codes 431
59. 15.4 Ofüine caching 440
60. 16.1 Aggregate analysis 449
61. 16.2 The accounting method 453
62. 16.3 The potential method 456
63. 16.4 Dynamic tables 460
64. 17.1 Dynamic order statistics 480
65. 17.2 How to augment a data structure 486
66. 17.3 Interval trees 489
67. 18.1 Deûnition of B-trees 501
68. 18.2 Basic operations on B-trees 504
69. 18.3 Deleting a key from a B-tree 513
70. 19.1 Disjoint-set operations 520
71. 19.2 Linked-list representation of disjoint sets 523
72. 19.3 Disjoint-set forests 527
73. 19.4 Analysis of union by rank with path compression 531
74. 20.1 Representations of graphs 549
75. 20.2 Breadth-ûrst search 554
76. 20.3 Depth-ûrst search 563
77. 20.4 Topological sort 573
78. 20.5 Strongly connected components 576
79. 21.1 Growing a minimum spanning tree 586
80. 21.2 The algorithms of Kruskal and Prim 591
81. 22.1 The Bellman-Ford algorithm 612
82. 22.2 Single-source shortest paths in directed acyclic graphs 616
83. 22.3 Dijkstra’s algorithm 620
84. 22.4 Difference constraints and shortest paths 626
85. 22.5 Proofs of shortest-paths properties 633
86. 23.1 Shortest paths and matrix multiplication 648
87. 23.2 The Floyd-Warshall algorithm 655
88. 23.3 Johnson’s algorithm for sparse graphs 662
89. 24.1 Flow networks 671
90. 24.2 The Ford-Fulkerson method 676
91. 24.3 Maximum bipartite matching 693
92. 25.1 Maximum bipartite matching (revisited) 705
93. 25.2 The stable-marriage problem 716
94. 25.3 The Hungarian algorithm for the assignment problem 723
95. 26.1 The basics of fork-join parallelism 750
96. 26.2 Parallel matrix multiplication 770
97. 26.3 Parallel merge sort 775
98. 27.1 Waiting for an elevator 792
99. 27.2 Maintaining a search list 795
100. 27.3 Online caching 802
101. 28.1 Solving systems of linear equations 819
102. 28.2 Inverting matrices 833
103. 28.3 Symmetric positive-deûnite matrices and least-squares approximation 838
104. 29.1 Linear programming formulations and algorithms 853
105. 29.2 Formulating problems as linear programs 860
106. 29.3 Duality 866
107. 30.1 Representing polynomials 879
108. 30.2 The DFT and FFT 885
109. 30.3 FFT circuits 894
110. 31.1 Elementary number-theoretic notions 904
111. 31.2 Greatest common divisor 911
112. 31.3 Modular arithmetic 916
113. 31.4 Solving modular linear equations 924
114. 31.5 The Chinese remainder theorem 928
115. 31.6 Powers of an element 932
116. 31.7 The RSA public-key cryptosystem 936
117. 31.8 Primality testing 942
118. 32.1 The naive string-matching algorithm 960
119. 32.2 The Rabin-Karp algorithm 962
120. 32.3 String matching with ûnite automata 967
121. 32.4 The Knuth-Morris-Pratt algorithm 975
122. 32.5 Sufûx arrays 985
123. 33.1 Clustering 1005
124. 33.2 Multiplicative-weights algorithms 1015
125. 33.3 Gradient descent 1022
126. 34.1 Polynomial time 1048
127. 34.2 Polynomial-time veriûcation 1056
128. 34.3 NP-completeness and reducibility 1061
129. 34.4 NP-completeness proofs 1072
130. 34.5 NP-complete problems 1080
131. 35.1 The vertex-cover problem 1106
132. 35.2 The traveling-salesperson problem 1109
133. 35.3 The set-covering problem 1115
134. 35.4 Randomization and linear programming 1119
135. 35.5 The subset-sum problem 1124