Skip to content Skip to content

CLRS-Lean

Chapter 1. The Role of Algorithms in Computing

Chapter 2. Getting Started

2.1. Insertion Sort

2.2. Analyzing Algorithms

2.3. Designing Algorithms

Chapter 3. Characterizing Running Times

3.1. Asymptotic Notation

3.2. Asymptotic Notation: Formal Definitions

3.3. Standard Notations and Common Functions

Chapter 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

Branching

4.5. The Master Method for Solving Recurrences

4.6. Proof of the Continuous Master Theorem

4.7. Akra–Bazzi Recurrences

Chapter 5. Probabilistic Analysis and Randomized Algorithms

5.1. The Hiring Problem

5.2. Indicator random variables

5.3. Randomized algorithms

FisherYates

5.4. Probabilistic analysis

Chapter 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

Chapter 7. Quicksort

7.1. Description of Quicksort

7.2. Performance of Quicksort

7.3. Randomized Quicksort

ExplicitRandomness

7.4. Analysis of Quicksort

Chapter 8. Sorting in Linear Time

8.1. Lower Bounds for Sorting

8.2. Counting Sort

8.3. Radix Sort

8.4. Bucket Sort

Chapter 9. Medians and Order Statistics

9.1. Minimum and Maximum

9.2. Selection in Expected Linear Time

9.3. Selection in Worst-Case Linear Time

Chapter 10. Elementary Data Structures

10.1. Simple Array-Based Data Structures

10.2. Linked Lists

10.3. Representing Rooted Trees

Chapter 11. Hash Tables

11.1. Direct-Address Tables

11.2. Chained Hash Tables

11.3. Hash Functions

11.4. Open Addressing

11.5. Perfect Hashing

Chapter 12. Binary Search Trees

12.1. What Is a Binary Search Tree?

12.2. Querying a Binary Search Tree

12.3. Insertion and Deletion

Chapter 13. Red-Black Trees

13.1. Red-Black Trees

13.2. Rotations

13.3. Insertion

13.4. Deletion

Chapter 14. Dynamic Programming

14.1. Rod Cutting

14.2. Matrix-Chain Multiplication

14.3. Elements of Dynamic Programming

14.4. Longest Common Subsequence

14.5. Optimal Binary Search Trees

Chapter 15. Greedy Algorithms

15.1. Activity Selection

15.2. Greedy-Choice Property and Optimal Substructure (Meta-Theorems)

15.3. Huffman Codes

15.4. Offline caching

Chapter 16. Amortized Analysis

16.1. Aggregate Analysis

16.2. The Accounting Method

16.3. The Potential Method

16.4. Dynamic Tables

Chapter 17. Augmenting Data Structures

17.1. Dynamic Order Statistics

17.2. How to Augment a Data Structure

17.3. Interval Trees

Chapter 18. B-Trees

18.1. B-Tree Model

18.2. B-Tree Insertion

18.3. B-Tree Deletion

Chapter 19. Data Structures for Disjoint Sets

19.1. Disjoint-Set Operations

19.2. Linked-List Representation of Disjoint Sets

19.3. Disjoint-Set Forests

19.4. Analysis of Union by Rank with Path Compression

Chapter 20. Elementary Graph Algorithms

20.1. Representing Graphs

20.2. Breadth-First Search

20.3. Depth-First Search

20.4. Topological Sort

20.5. Strongly Connected Components

Chapter 21. Minimum Spanning Trees

21.1. Growing a Minimum Spanning Tree

21.2. Kruskal and Prim

ArrayPrim

Chapter 22. Single-Source Shortest Paths

22.1. The Bellman-Ford Algorithm

22.2. Single-Source Shortest Paths in DAGs

22.3. Dijkstra's Algorithm

22.4. Difference Constraints and Shortest Paths

22.5. Proofs of Shortest Paths

Chapter 23. All-Pairs Shortest Paths

MatrixExecution

23.1. All-Pairs Shortest Paths Model

23.2. The Floyd-Warshall Algorithm

23.3. Johnson's Algorithm for Sparse Graphs

Chapter 24. Maximum Flow

24.1. Flow Networks

24.2. The Edmonds-Karp Algorithm

SparseExecution

24.3. Maximum Bipartite Matching

24.4. Push-Relabel Algorithms

24.5. Relabel-to-Front

Theorem 24.6. Max-Flow Min-Cut

Chapter 25. Matchings in Bipartite Graphs

25.1. Maximum bipartite matching revisited

25.2. The stable-marriage problem

25.3. The Hungarian algorithm for the assignment problem

Chapter 26. Parallel Algorithms

26.1. The Basics of Fork-Join Parallelism

26.2. Parallel Matrix Multiplication

26.3. Parallel Merge Sort

Chapter 27. Online Algorithms

27.1. Waiting for an Elevator

27.2. Maintaining a Search List

27.3. Online Caching

Chapter 28. Matrix Operations

28.1. Solving Systems of Linear Equations

28.2. Inverting Matrices

28.3. Symmetric Positive-Definite Matrices and Least Squares

Chapter 29. Linear Programming

29.1. Standard and Slack Forms

29.2. Formulating Problems as Linear Programs

Chapter 30. Polynomials and the FFT

30.1. Representing Polynomials

30.2. The DFT and FFT

30.3. Efficient FFT Implementations

Chapter 31. Number-Theoretic Algorithms

31.1. Elementary Number-Theoretic Notions

31.2. Greatest Common Divisor

31.3. Modular Arithmetic

31.4. Solving Modular Linear Equations

31.5. The Chinese Remainder Theorem

31.6. Powers of an Element

31.7. The RSA Public-Key Cryptosystem

31.8. Primality Testing

Chapter 32. String Matching

32.1. The Naive String-Matching Algorithm

32.2. The Rabin–Karp Algorithm

32.3. String Matching with Finite Automata

32.4. The Knuth–Morris–Pratt Algorithm

32.5. Suffix Arrays

Chapter 33. Machine-Learning Algorithms

33.1. Clustering

33.2. Multiplicative-Weights Algorithms

33.3. Gradient Descent

Chapter 34. NP-Completeness

34.1. Polynomial Time

34.2. Polynomial-Time Verification

34.3. NP-Completeness and Reducibility

34.4. NP-Completeness Proofs

34.5. NP-Complete Problems

Chapter 35. Approximation Algorithms

35.1. The Vertex-Cover Problem

35.2. The Traveling-Salesperson Problem

35.3. The Set-Covering Problem

35.4. Randomization and Linear Programming

35.5. The Subset-Sum Problem

Progress Dashboard

Proof Status

Online Material

Reusable CLRS Proof Patterns

Finite Probability Toolkit

Extensions Beyond the Textbook

Contributor Guide

CLRS-Lean
Chapter 34. NP-Completeness
34.4. NP-Completeness Proofs
34.4. Verified bounded TM2 builders
34.4. List Pair Eq

Browse chapters

Imports

import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.PolyBuilder.ListPairEq.Runtime

Fixed equality checker for separated finite-alphabet lists