Introduction to Algorithms

by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein · 4th Edition · 2022

The definitive textbook on algorithms. Covers fundamentals (sorting, data structures), advanced techniques (DP, greedy, graph algorithms), and specialized topics (multithreading, online algorithms, machine learning).

210Extracted Problems
35Chapters
0Linked to DB
210Book Total
AlgorithmsData StructuresSortingGraphsTextbook
210 shown
  • 1-1Comparison of running times: for each function f(n) and time t, find the largest n solvable.
    1-2Problem 1.2
    Easy
    1-3Problem 1.3
    Medium
    1-4Problem 1.4
    Medium
    1-5Problem 1.5
    Hard
    1-6Problem 1.6
    Easy
  • 2-1Insertion sort on small arrays in merge sort.
    2-2Correctness of bubblesort.
    2-3Correctness of Horner's rule for evaluating polynomials.
    2-4Inversions: give algorithm to count inversions in O(n lg n) time.
    2-5Problem 2.5
    Hard
    2-6Problem 2.6
    Easy
  • 3-1Asymptotic behavior of polynomials.
    3-2Relative asymptotic growths of common functions.
    3-3Ordering by asymptotic growth rates.
    3-4Asymptotic notation properties.
    3-5Problem 3.5
    Hard
    3-6Problem 3.6
    Easy
  • 4-1Recurrence examples: solve recurrences with the master method.
    4-2Parameter-passing costs in divide-and-conquer.
    4-3More recurrence examples with various methods.
    4-4Fibonacci numbers: recursion tree analysis.
    4-5Chip testing: find a good chip using pairwise tests.
    4-6Monge arrays: implement matrix operations on an array with the Monge property.
  • 5-1Probabilistic counting: count distinct elements with limited memory.
    5-2Searching an unsorted array: analyze deterministic vs randomized search.
    5-3Problem 5.3
    Medium
    5-4Problem 5.4
    Medium
    5-5Problem 5.5
    Hard
    5-6Problem 5.6
    Easy
  • 6-1Building a heap using insertion.
    6-2Analysis of d-ary heaps.
    6-3Young tableau: an m×n matrix with sorted rows and columns.
    6-4Problem 6.4
    Medium
    6-5Problem 6.5
    Hard
    6-6Problem 6.6
    Easy
  • 7-1Hoare partition correctness.
    7-2Quicksort with equal element values.
    7-3Stooge sort: analyze this inefficient sorting algorithm.
    7-4Stack depth for quicksort: tail recursion optimization.
    7-5Median-of-3 partition: analysis of the improvement.
    7-6Fuzzy sorting of intervals: sort overlapping intervals.
  • 8-1Lower bounds on comparison-based sorting: probabilistic lower bound.
    8-2Sorting in place in linear time: counting sort with O(1) extra space.
    8-3Sorting variable-length items: sort strings of different lengths in O(n) time.
    8-4Water jugs: match red and blue jugs by capacity.
    8-5Average sorting: sort by averages of k consecutive elements.
    8-6Lower bound on merging sorted lists.
  • 9-1Largest i numbers in sorted order: find and sort the i largest numbers.
    9-2Weighted median: compute the weighted median in O(n lg n) time.
    9-3Small order statistics: find the kth smallest for small k in O(n) time.
    9-4Alternative analysis of RANDOMIZED-SELECT using indicator variables.
    9-5Problem 9.5
    Hard
    9-6Problem 9.6
    Easy
  • 10-1Comparisons among lists: sorted vs unsorted, singly vs doubly linked.
    10-2Mergeable heaps using linked lists: implement mergeable heaps.
    10-3Searching a sorted compact list: use binary search on an array with gaps.
    10-4Problem 10.4
    Medium
    10-5Problem 10.5
    Hard
    10-6Problem 10.6
    Easy
  • 11-1Longest-probe bound for hashing: longest probe sequence in open addressing.
    11-2Slot-size bound for chaining: expected number of keys in a slot.
    11-3Quadratic probing: show that (h(k)+c1i+c2i²) mod m covers all slots.
    11-4Hashing and authentication: design a scheme resistant to adversarial keys.
    11-5Problem 11.5
    Hard
    11-6Problem 11.6
    Easy
  • 12-1Binary search trees with equal keys: handle duplicate keys efficiently.
    12-2Radix trees: insert/search/delete strings in O(h) time.
    12-3Average node depth in a randomly built BST.
    12-4Number of different binary trees on n nodes (Catalan numbers).
    12-5Problem 12.5
    Hard
    12-6Problem 12.6
    Easy
  • 13-1Persistent dynamic sets: maintain all past versions of a BST.
    13-2Join operation on red-black trees: merge two BSTs with all keys in one less than the other.
    13-3AVL trees: compare height-balanced trees with red-black trees.
    13-4Treaps: randomized search trees with BST and heap properties.
    13-5Problem 13.5
    Hard
    13-6Problem 13.6
    Easy
  • 14-1Longest simple path in a DAG: find the longest path in a DAG in O(V+E) time.
    14-2Longest palindrome subsequence: find LPS in O(n²) time.
    14-3Bitonic Euclidean traveling-salesman problem: find shortest bitonic TSP tour.
    14-4Print neatly: word wrap with minimum cost.
    14-5Edit distance: transform one string into another with insert/delete/replace.
    14-6Maximum sum of nonadjacent elements: use O(n) DP without auxiliary storage.
  • 15-1Coin changing: show greedy is optimal for US coins; find counterexample set.
    15-2Scheduling to minimize average completion time: prove greedy is optimal.
    15-3Huffman coding generalization: ternary Huffman codes.
    15-4Minimum maximum spanning tree: find spanning tree that minimizes maximum edge weight.
    15-5Scheduling with profits and deadlines: maximize profit using greedy or DP.
    15-6Offline caching (paging): design LRU and LFD cache eviction policies.
  • 16-1Persistent dynamic sets: use potential method for persistent BSTs.
    16-2Join operation on red-black trees: amortized analysis of RB-join.
    16-3Amortized weight-balanced trees: analyze weight-balanced BST operations.
    16-4Problem 16.4
    Medium
    16-5Problem 16.5
    Hard
    16-6Problem 16.6
    Easy
  • 17-1Dynamic order statistics with binary search trees maintaining order-statistic fields.
    17-2Minimum-gap: maintain the minimum difference between any two numbers in a set.
    17-3Union of intervals: maintain a set of intervals supporting insert/delete/min-gap.
    17-4Problem 17.4
    Medium
    17-5Problem 17.5
    Hard
    17-6Problem 17.6
    Easy
  • 18-1Stacks on secondary storage: implement stacks using B-tree pages.
    18-2Joining and splitting B-trees: implement concat and split operations.
    18-3Problem 18.3
    Medium
    18-4Problem 18.4
    Medium
    18-5Problem 18.5
    Hard
    18-6Problem 18.6
    Easy
  • 19-1Offline minimum: find the min removed from each extraction using disjoint sets.
    19-2Analysis of graph connectivity: use union-find offline.
    19-3Tarjan's off-line least-common-ancestors algorithm.
    19-4Problem 19.4
    Medium
    19-5Problem 19.5
    Hard
    19-6Problem 19.6
    Easy
  • 20-1Longest simple path in a DAG: compute longest path using topological sort.
    20-2Articulation points, bridges, biconnected components.
    20-3Alternating paths and Euler trails: find Euler tour in a directed graph.
    20-4Reachability in an undirected graph: O(V+E) algorithm using BFS/DFS.
    20-5Problem 20.5
    Hard
    20-6Problem 20.6
    Easy
  • 21-1Unique MST: conditions for a unique minimum spanning tree.
    21-2Minimum spanning tree with each edge weight constrained to 1 or 2.
    21-3Second-best minimum spanning tree: find MST of second-minimum total weight.
    21-4Problem 21.4
    Medium
    21-5Problem 21.5
    Hard
    21-6Problem 21.6
    Easy
  • 22-1Parallel machine scheduling: formulate as difference constraints.
    22-2Monotone shortest paths: shortest paths in which every path is monotonic in weight.
    22-3Earliest meeting: compute the earliest meeting time in a DAG.
    22-4Problem 22.4
    Medium
    22-5Problem 22.5
    Hard
    22-6Problem 22.6
    Easy
  • 23-1Transitive closure of a dynamic graph: maintain transitive closure under edge insertions.
    23-2All-pairs shortest paths on a line: simple O(n²) algorithm for a line graph.
    23-3All-pairs shortest paths with matrix multiplication: worst-case O(V³ lg V).
    23-4Problem 23.4
    Medium
    23-5Problem 23.5
    Hard
    23-6Problem 23.6
    Easy
  • 24-1Ford-Fulkerson variations: analyze different augmenting-path choices.
    24-2Escape problem: determine if there is a path for each unit to escape a grid.
    24-3Maximum bipartite matching: show equivalence to max flow in unit-capacity networks.
    24-4Problem 24.4
    Medium
    24-5Problem 24.5
    Hard
    24-6Problem 24.6
    Easy
  • 25-1Edge-disjoint paths: find maximum number of edge-disjoint paths.
    25-2Maximum bipartite matching via max flow: implement Hopcroft-Karp-like algorithm.
    25-3Stable matching with ties and incomplete lists: Gale-Shapley variant.
    25-4Problem 25.4
    Medium
    25-5Problem 25.5
    Hard
    25-6Problem 25.6
    Easy
  • 26-1Parallel matrix operations: analyze span and work of matrix addition/multiplication.
    26-2Parallel merge sort: design a work-efficient parallel mergesort.
    26-3Problem 26.3
    Medium
    26-4Problem 26.4
    Medium
    26-5Problem 26.5
    Hard
    26-6Problem 26.6
    Easy
  • 27-1Paging against a non-oblivious adversary: lower bound analysis.
    27-2The k-server problem: analyze the work-function algorithm.
    27-3Online minimum spanning tree: competitive ratio of greedy algorithm.
    27-4Problem 27.4
    Medium
    27-5Problem 27.5
    Hard
    27-6Problem 27.6
    Easy
  • 28-1Triangular systems of equations: parallel algorithm for back-substitution.
    28-2Inversion of band matrices: analyze Strassen-based inversion of band matrix.
    28-3Problem 28.3
    Medium
    28-4Problem 28.4
    Medium
    28-5Problem 28.5
    Hard
    28-6Problem 28.6
    Easy
  • 29-1Linear programming and maximum flow: formulate max flow as LP.
    29-2Duality of minimum spanning tree and maximum spanning forest.
    29-3The simplex algorithm: geometric interpretation and degenerate pivots.
    29-4Problem 29.4
    Medium
    29-5Problem 29.5
    Hard
    29-6Problem 29.6
    Easy
  • 30-1Divide-and-conquer multiplication of large integers: use FFT for O(n lg n).
    30-2Toeplitz matrices: multiply a Toeplitz matrix by a vector using FFT.
    30-3Problem 30.3
    Medium
    30-4Problem 30.4
    Medium
    30-5Problem 30.5
    Hard
    30-6Problem 30.6
    Easy
  • 31-1Binary gcd algorithm: analyze Stein's algorithm (binary GCD).
    31-2Analysis of bit operations in the Euclidean algorithm.
    31-3RSA attack: breaking RSA when d is small.
    31-4Problem 31.4
    Medium
    31-5Problem 31.5
    Hard
    31-6Problem 31.6
    Easy
  • 32-1String matching based on repetition factors: O(n) algorithm using border analysis.
    32-2Suffix arrays: construct SA in O(n) and use for pattern matching.
    32-3Problem 32.3
    Medium
    32-4Problem 32.4
    Medium
    32-5Problem 32.5
    Hard
    32-6Problem 32.6
    Easy
  • 33-1VC dimension of axis-aligned rectangles: compute VC dimension.
    33-2Error bounds for bagging: analyze ensemble classification error.
    33-3Problem 33.3
    Medium
    33-4Problem 33.4
    Medium
    33-5Problem 33.5
    Hard
    33-6Problem 33.6
    Easy
  • 34-1Independent set: prove INDEPENDENT-SET is NP-complete.
    34-2Vertex cover: prove VERTEX-COVER is NP-complete.
    34-3Set packing: prove SET-PACKING is NP-complete.
    34-4Subgraph isomorphism: prove SUBGRAPH-ISOMORPHISM is NP-complete.
    34-5Longest simple cycle: prove LONGEST-CYCLE is NP-complete.
    34-6Problem 34.6
    Easy
  • 35-1Bin packing: analyze First-Fit and Best-Fit decreasing algorithms.
    35-2Approximating the size of a maximum clique: semidefinite programming.
    35-3Approximating MAX-CUT: analyze randomized and derandomized algorithms.
    35-4Problem 35.4
    Medium
    35-5Problem 35.5
    Hard
    35-6Problem 35.6
    Easy