My CLRS solutions
TeX Other
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
chapters
code
data
images
.gitignore
LICENSE
Makefile
README.md
isolatin1.sty
solutions.tex

README.md

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