CLRS Third Edition Solutions

These are my personal solutions for the problems from Introdution to Algorithms, Third Edition.

The compiled PDF is available on my website.

Selected Topics

Foundations

• The role of algorithms in computing (1.1-1.2)
  • Algorithms — 5 pr — done
  • Algorithms as a technology — 3 pr — done
  • Problems — 1 pr — done
• Getting started (2.1-2.3)
  • Insertion sort — 4 pr — done
  • Analyzing algorithms — 4 pr — done
  • Designing algorithms — 7 pr — 1 starred — done
  • Problem — 4 — done
• Growth of functions (3.1-3.2)
  • Asymptotic notation — 8 pr — done
  • Standard notations and common functions — 8 pr — 2 starred — done
  • Problems — 6 pr — skipped
• Divide-and-Conquer (4.1-4.5)
  • The maximum-subarray problem — 5 pr — done
  • Strassen’s algorithm for matrix multiplication — 7 pr — done
  • The substitution method for solving recurrences — 9 pr — done
  • The recursion-tree method for solving recurrences — 9 pr — done
  • The master method for solving recurrences — 5 pr — 1 starred — done
  • Problems — 6 pr — done
• Probabilist Analysis and Randomized Algorithms (5.1-5.3)
  • The hiring problem — 3 pr — 2 starred — done
  • Indicator random variables — 5 pr — done
  • Randomized algorithms — 7 pr — 1 starred — done
  • Problems — 2 pr — done

Sorting and Order Statistics

• Heapsort (6.1-6.5)
  • Heaps — 7 pr — done
  • Maintaining the heap property — 6 pr — done
  • Building a heap — 3 pr — done
  • The heapsort algorithm — 5 pr — 1 starred — done
  • Priority queues — 9 pr — done
  • Problems — 3 pr — done
• Quicksort (7.1-7.4)
  • Description of quicksort — 4 pr — done
  • Performance of quicksort — 6 pr — 1 starred — done
  • A randomized version of quicksort — 2 pr — done
  • Analysis of quicksort — 6 pr — 1 starred — done
  • Problems — 6 pr — done
• Sorting in Linear Time (8.1-8.4)
  • Lower bounds for sorting — 4 pr — done
  • Counting sort — 4 pr — done
  • Radix sort — 5 pr — 1 starred — done
  • Bucket sort — 5 pr — 2 starred — done
  • Problems — 7 pr — done
• Medians and Order Statistics (9.1-9.3)
  • Minimum and maximum — 2 pr — 1 starred — done
  • Selection in expected linear time — 4 pr — done
  • Selection in worst-case linear time — 9 pr — 1 starred — done
  • Problems — 4 pr — done

Data Structures

• Elementary Data Structures (10.1-10.4)
  • Stacks and queues — 7 pr
  • Linked lists — 8 pr — 1 starred
  • Implementing pointers and objects — 5 pr
  • Representing rooted trees — 6 pr — 2 starred
  • Problems — 3 pr
• Hash Tables (11.1-11.4)
  • Direct-address tables — 4 pr — 1 starred
  • Hash tables — 6 pr
  • Hash functions — 6 pr — 2 starred
  • Open addressing — 5 pr — 2 starred
  • Problems — 4 pr
• Binary Search Trees (12.1-12.4)
  • What is a binary search tree? — 5 pr
  • Querying a binary search tree — 9 pr
  • Insertion and deletion — 6 pr
  • Randomly built binary search trees — 5 pr — 1 starred
  • Problems — 4 pr
• Red-Black Trees (13.1-13.4)
  • Properties of red-black trees — read only
  • Rotations — read only
• Augmenting Data Structures (14.1-14.3)
  • Dynamic order statistics — read only
  • How to augment a data structure — read only

Advanced Design and Analysis Techniques

• Dynamic Programming (15.1-15.5)
  • Rod cutting — 5 pr
  • Matrix-chain multiplication — 6 pr
  • Elements of dynamic programming — 6 pr
  • Longest common subsequence — 6 pr — 1 starred
  • Optimal binary search trees — 4 pr — 1 starred
  • Problems — 12 pr
• Greedy Algorithms (16.1-16.3)
  • An activity-selection problem — 5 pr
  • Elements of the greedy strategy — 7 pr — 1 starred
  • Huffman codes — 9 pr
  • Problems — 5 pr
• Amortized Analysis (17.1)
  • Aggregate analysis — 3 pr

Graph Algorithms

• Elementary Graph Algorithms (22.1-22.5)
  • Representations of graphs — 8 pr
  • Breadth-first search — 9 pr — 1 starred
  • Depth-first search — 13 pr — 1 starred
  • Topological sort — 5 pr
  • Strongly connected components — 7 pr
  • Problems — 4 pr
• Minimum Spanning Trees (23.1-23.2)
  • Growing a minimum spanning tree — 11 pr — 1 starred
  • The algorithms of Kruskal and Prim — 8 pr — 2 starred
  • Problems — 4 pr
• Single-Source Shortest Paths (24.1-24.5)
  • The Bellman-Ford algorithm — 6 pr — 2 starred
  • Single-source shortest paths in directed acyclic graphs — 4 pr
  • Dijkstra’s algorithm — 10 pr
  • Problems — 6 pr
• All-Pairs Shortest Paths (25.1-25.3)
  • Shortest paths and matrix multiplication — read only
  • The Floyd-Warshall algorithm — read only

Selected Topics

• Number-Theoretic Algorithms (31.1-31.2)
  • Elementary number-theoretic notions — read only
  • Greatest common divisor — read only
• String Matching (32.1-32.2)
  • The naive string-matching algorithm — read only
  • The Rabin-Karp algorithm — read only

Appendix

• Summations (A.1-A.2)
  • Summation formulas and properties — 8 pr — 4 starred — done
  • Bounding summations — 5 pr — done
  • Problems — 1 pr — done
• Sets, Etc. (B.1-B.5)
  • Sets — 6 pr — 1 starred — done
  • Relations — 5 pr — done
  • Functions — 4 pr — 1 starred — done
  • Graphs — 6 pr — 1 starred
  • Trees — 7 pr — 3 starred
  • Problems — 3 pr
• Counting and Probability (C.1-C.4)
  • Counting — 15 pr — 5 starred — done
  • Probability — 10 pr — 5 starred — done
  • Discrete and random variables — 10 pr — 3 starred — done
  • The geometric and binomial distributions — 9 pr — 5 starred
  • Problems — 1 pr
• Matrices (D.1-D.2)
  • Matrices and matrix operations — 4 pr
  • Basic matrix properties — 8 pr
  • Problems — 2 pr