Bytebook · DAA

Design and Analysis of Algorithms

Analyse and design efficient algorithms: asymptotic analysis, recurrences, divide and conquer, greedy methods, dynamic programming, backtracking, graph algorithms and NP-completeness.

Back to lessons

Chapter 1 · Analysis of Algorithms

What Is an Algorithm?

The definition and five properties of an algorithm, how to write pseudocode, proving correctness with loop invariants, and the RAM model used to analyse running time.

An algorithm is a finite sequence of well-defined steps that takes some input and produces the correct output for every valid input. A program is an algorithm written in a particular language for a particular machine; the algorithm itself is the idea.

The five properties (Knuth)

Property	Meaning
Input	zero or more quantities supplied from outside
Output	at least one quantity produced
Definiteness	every step is precise and unambiguous
Finiteness	it always terminates after a finite number of steps
Effectiveness	every step is basic enough to be carried out exactly, in finite time

"Keep stirring until it tastes good" fails definiteness. A loop that may never end fails finiteness.

The design and analysis process

Understand the problem — inputs, outputs, constraints, edge cases.
Choose a design technique — brute force, divide and conquer, greedy, dynamic programming, backtracking …
Write the algorithm — usually in pseudocode.
Prove it correct for all inputs.
Analyse its time and space as a function of the input size n.
Implement and test.

Pseudocode

Pseudocode describes an algorithm without the noise of a real language:

Pseudocode

INSERTION-SORT(A, n)
    for j = 2 to n
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

(Textbooks like CLRS index arrays from 1. Translate carefully to 0-based code.)

Proving correctness: loop invariants

A loop invariant is a statement that is true before every iteration of a loop. To prove an algorithm correct with one, show three things:

Initialisation — it is true before the first iteration.
Maintenance — if it is true before an iteration, it remains true before the next.
Termination — when the loop ends, the invariant gives a useful property that shows the algorithm is correct.

For insertion sort, the invariant is: at the start of each iteration, the subarray A[1..j−1] holds the original first j−1 elements in sorted order. When the loop ends with j = n + 1, the whole array is sorted.

C++

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

void insertionSort(vector<int> &a) {
    for (size_t j = 1; j < a.size(); j++) {
        assert(is_sorted(a.begin(), a.begin() + j));     // the loop invariant, checked at run time
        int key = a[j];
        int i = (int)j - 1;
        while (i >= 0 && a[i] > key) { a[i + 1] = a[i]; i--; }
        a[i + 1] = key;
    }
}

int main() {
    vector<int> a = {31, 41, 59, 26, 41, 58};
    insertionSort(a);
    for (int x : a) cout << x << " ";
    cout << "\nsorted: " << boolalpha << is_sorted(a.begin(), a.end()) << endl;
    return 0;
}

Output

26 31 41 41 58 59 
sorted: true

Try it Yourself

The RAM model

To analyse algorithms independently of hardware, we use the Random Access Machine model:

Each simple operation (arithmetic, comparison, assignment, array access, function call) takes one unit of time.
Memory access is constant time.
Instructions run one after another (no parallelism).

The running time T(n) is the number of unit steps for an input of size n. For example, insertion sort does about n²/4 comparisons on average, so T(n) grows like n².

Why analyse at all?

Suppose computer A runs 10⁹ instructions/second and computer B only 10⁷ — 100 times slower. Sort 10 million numbers:

	Algorithm	Steps	Time
Computer A	insertion sort, 2n²	2 × 10¹⁴	about 55 hours
Computer B	merge sort, 50 n log₂ n	about 1.2 × 10¹⁰	about 20 minutes

A better algorithm on a slow machine beats a worse algorithm on a fast machine by orders of magnitude. That is why this subject exists.

Chapter 2 · Analysis of Algorithms

Asymptotic Notations

The formal definitions of O, Ω and Θ (plus little-o and little-ω), proving bounds by finding c and n₀, the order of growth, and the properties exams test.

Asymptotic analysis describes how running time grows as n becomes large, ignoring constant factors and small inputs. It lets us say "merge sort is faster than insertion sort" in a precise, machine-independent way.

Big-O: upper bound

f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

f grows no faster than g. Example: 3n² + 10n + 5 = O(n²). Choose c = 4: we need 3n² + 10n + 5 ≤ 4n², i.e. n² − 10n − 5 ≥ 0, which holds for all n ≥ 11. So c = 4, n₀ = 11 works.

Big-Omega: lower bound

f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.

f grows at least as fast as g. Example: 3n² + 10n + 5 = Ω(n²) with c = 3, n₀ = 1.

Big-Theta: tight bound

f(n) = Θ(g(n)) if there exist positive constants c₁, c₂ and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.

f grows exactly as fast as g. f = Θ(g) if and only if f = O(g) and f = Ω(g). So 3n² + 10n + 5 = Θ(n²).

Little-o and little-omega

Notation	Meaning	Analogy	Example
f = O(g)	f grows no faster than g	≤	n = O(n), n = O(n²)
f = Ω(g)	f grows no slower than g	≥	n² = Ω(n)
f = Θ(g)	same growth rate	=	2n + 3 = Θ(n)
f = o(g)	f grows strictly slower: f/g → 0	<	n = o(n²), but n ≠ o(n)
f = ω(g)	f grows strictly faster: f/g → ∞	>	n² = ω(n)

Order of growth

From slowest to fastest growing:

1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n! < nⁿ

A quick way to compare two functions: compute lim f(n)/g(n) as n → ∞. If it is 0, f = o(g); if it is a positive constant, f = Θ(g); if it is ∞, f = ω(g).

Properties

Transitivity: if f = O(g) and g = O(h), then f = O(h) (same for Ω, Θ).
Reflexivity: f = O(f), f = Ω(f), f = Θ(f).
Symmetry: f = Θ(g) if and only if g = Θ(f).
Transpose symmetry: f = O(g) if and only if g = Ω(f).
Sum rule: O(f) + O(g) = O(max(f, g)).
Product rule: O(f) · O(g) = O(f · g).
Constants vanish: O(c·f) = O(f) for any constant c > 0.
Logs: log_a n = Θ(log_b n) for any bases a, b > 1, so the base is usually omitted.

Checking bounds numerically

You can watch a ratio settle to a constant (Θ) or shrink to zero (little-o):

C++

#include <cstdio>
#include <cmath>

int main() {
    printf("%10s %16s %16s %16s\n", "n", "f(n)/n^2", "n log n / n^2", "n^2 / 2^n");
    for (double n = 10; n <= 1e6; n *= 10) {
        double f = 3 * n * n + 10 * n + 5;
        printf("%10.0f %16.6f %16.6f %16.3g\n", n, f / (n * n), n * log2(n) / (n * n), n * n / pow(2, n));
    }
    return 0;
}

Output

         n         f(n)/n^2    n log n / n^2        n^2 / 2^n
        10         4.050000         0.332193           0.0977
       100         3.100500         0.066439         7.89e-27
      1000         3.010005         0.009966        9.33e-296
     10000         3.001000         0.001329                0
    100000         3.000100         0.000166                0
   1000000         3.000010         0.000020                0

Try it Yourself

The first column approaches 3 (so f = Θ(n²)); the second tends to 0 (n log n = o(n²)); the third collapses to 0 incredibly fast (n² = o(2ⁿ)).

Chapter 3 · Analysis of Algorithms

Analysing Loops & Recursive Code

Turn code into running times: independent and dependent nested loops, logarithmic loops, writing recurrences for recursive functions, and an introduction to amortised analysis.

Independent loops

Count the iterations of each loop and multiply when they are nested:

C++

for (int i = 0; i < n; i++)          // n times
    for (int j = 0; j < m; j++)      // m times each
        work();                      // total n·m → O(nm)

Dependent loops: sum the iterations

When the inner loop depends on the outer one, add up its iteration counts:

C++

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)     // runs i times
        work();

Total = 1 + 2 + … + n = n(n + 1)/2 = Θ(n²).

C++

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)  // runs about n/i times
        work();

Total = n/1 + n/2 + … + n/n = n·(1 + 1/2 + … + 1/n) ≈ n ln n = Θ(n log n) (the harmonic series).

Logarithmic loops

A loop variable that is multiplied or divided by a constant each step runs Θ(log n) times:

C++

for (int i = 1; i < n; i *= 2) work();       // log2 n iterations
for (int i = n; i > 0; i /= 3) work();       // log3 n iterations
for (int i = 2; i < n; i = i * i) work();    // log log n iterations

Measure it yourself

C++

#include <cstdio>

int main() {
    for (long n = 1000; n <= 1000000; n *= 10) {
        long a = 0, b = 0, c = 0, d = 0;
        for (long i = 1; i < n; i *= 2) a++;                         // log n
        for (long i = 1; i <= n; i++) for (long j = 1; j <= n; j += i) b++;   // n log n (harmonic)
        for (long i = 2; i < n; i = i * i) c++;                      // log log n
        for (long i = 1; i * i <= n; i++) d++;                       // sqrt n
        printf("n=%8ld  log:%3ld  harmonic:%9ld  loglog:%2ld  sqrt:%5ld\n", n, a, b, c, d);
    }
    return 0;
}

Output

n=    1000  log: 10  harmonic:     8053  loglog: 4  sqrt:   31
n=   10000  log: 14  harmonic:   103643  loglog: 4  sqrt:  100
n=  100000  log: 17  harmonic:  1266714  loglog: 5  sqrt:  316
n= 1000000  log: 20  harmonic: 14969985  loglog: 5  sqrt: 1000

Try it Yourself

Common patterns

Code shape	Running time
single loop to n	Θ(n)
two nested loops to n	Θ(n²)
`i` doubles each step	Θ(log n)
loop to n with an inner doubling loop	Θ(n log n)
inner loop runs `i` times	Θ(n²)
inner loop runs `n/i` times	Θ(n log n)
loop while `i*i <= n`	Θ(√n)

Recursive code: write a recurrence

For a recursive function, write T(n) in terms of T on smaller inputs plus the work done outside the recursive calls:

Function	Recurrence	Solution
factorial(n) = n · factorial(n−1)	T(n) = T(n−1) + O(1)	Θ(n)
binary search	T(n) = T(n/2) + O(1)	Θ(log n)
merge sort	T(n) = 2T(n/2) + O(n)	Θ(n log n)
naive Fibonacci	T(n) = T(n−1) + T(n−2) + O(1)	Θ(φⁿ) ≈ Θ(1.618ⁿ)
Tower of Hanoi	T(n) = 2T(n−1) + O(1)	Θ(2ⁿ)
selection sort, recursive	T(n) = T(n−1) + O(n)	Θ(n²)

The next lesson shows how to solve recurrences like these.

Best, worst and average case

For linear search on n items:

Best case: key at position 1 → 1 comparison → Θ(1).
Worst case: key absent → n comparisons → Θ(n).
Average case: if the key is equally likely to be at any position, expected comparisons = (1 + 2 + … + n)/n = (n + 1)/2 → Θ(n).

Amortised analysis

Some operations are usually cheap but occasionally expensive. Amortised analysis averages the cost over a sequence of operations (no probability involved).

Example: vector::push_back doubles the capacity when full, copying all elements. A single push can cost O(n), but over n pushes the total copying is 1 + 2 + 4 + … + n < 2n, so each push costs O(1) amortised.

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    long copies = 0;
    for (int i = 0; i < 1000; i++) {
        if (v.size() == v.capacity()) copies += v.size();     // a reallocation copies everything
        v.push_back(i);
    }
    cout << "1000 pushes, total elements copied: " << copies << " (less than 2 x 1000)" << endl;
    cout << "final capacity: " << v.capacity() << endl;
    return 0;
}

Output

1000 pushes, total elements copied: 1023 (less than 2 x 1000)
final capacity: 1024

Try it Yourself

The three classic methods are the aggregate, accounting and potential methods.

Chapter 4 · Analysis of Algorithms

Solving Recurrences & the Master Theorem

Solve recurrences with the substitution method, recursion trees and the Master Theorem — with its three cases, worked examples, and the cases it cannot handle.

1. The substitution method

Guess the form of the solution, then prove it by induction.

Example: T(n) = 2T(⌊n/2⌋) + n. Guess T(n) ≤ c·n log n.

Assume it holds for n/2: T(n/2) ≤ c(n/2)log(n/2). Then

T(n) ≤ 2·c(n/2)log(n/2) + n = c·n log n − c·n·log 2 + n = c·n log n − c·n + n ≤ c·n log n whenever c ≥ 1.

So T(n) = O(n log n).

2. The recursion-tree method

Draw the tree of recursive calls, add the cost at each level, then sum the levels.

T(n) = 2T(n/2) + n:

Each level sums to n (n; n/2 + n/2; four times n/4 …). There are log₂ n levels, so T(n) = n log₂ n.

Level	Nodes	Cost per node	Level total
0	1	n	n
1	2	n/2	n
2	4	n/4	n
…	…	…	…
log₂ n	n	1	n

Total = n × (log₂ n + 1) = Θ(n log n).

3. The Master Theorem

For recurrences of the form

T(n) = a·T(n/b) + f(n), with a ≥ 1, b > 1

compare f(n) with n^(log_b a) (the total cost of the leaves):

Case	Condition	Result
1	f(n) = O(n^(log_b a − ε)) for some ε > 0 — leaves dominate	T(n) = Θ(n^(log_b a))
2	f(n) = Θ(n^(log_b a)) — every level costs the same	T(n) = Θ(n^(log_b a) · log n)
3	f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ c·f(n) for some c < 1 — root dominates	T(n) = Θ(f(n))

Worked examples

Recurrence	a, b, n^(log_b a)	f(n)	Case	Answer
T(n) = 2T(n/2) + n (merge sort)	2, 2, n	n	2	Θ(n log n)
T(n) = T(n/2) + 1 (binary search)	1, 2, 1	1	2	Θ(log n)
T(n) = 8T(n/2) + n²	8, 2, n³	n²	1	Θ(n³)
T(n) = 7T(n/2) + n² (Strassen)	7, 2, n^2.81	n²	1	Θ(n^2.81)
T(n) = 2T(n/2) + n²	2, 2, n	n²	3	Θ(n²)
T(n) = 3T(n/4) + n log n	3, 4, n^0.79	n log n	3	Θ(n log n)
T(n) = 4T(n/2) + n²	4, 2, n²	n²	2	Θ(n² log n)

Extended case 2

If f(n) = Θ(n^(log_b a) · logᵏ n) with k ≥ 0, then T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n). For example, T(n) = 2T(n/2) + n log n = Θ(n log² n).

When the Master Theorem does not apply

Subproblems of different sizes: T(n) = T(n/3) + T(2n/3) + n (use a recursion tree: Θ(n log n)).
Subtract-and-conquer forms: T(n) = T(n − 1) + n (unroll: Θ(n²)); T(n) = 2T(n − 1) + 1 (Θ(2ⁿ)).
f(n) falls in a gap between cases, e.g. T(n) = 2T(n/2) + n/log n.
a < 1 or b ≤ 1.

Unrolling (iteration method)

For T(n) = T(n − 1) + n with T(1) = 1:

T(n) = n + T(n−1) = n + (n−1) + T(n−2) = … = n + (n−1) + … + 2 + 1 = n(n+1)/2 = Θ(n²).

Check a solution by computing it

C++

#include <cstdio>
#include <cmath>
#include <map>

std::map<long, double> memo;
double T(long n) {                       // T(n) = 2T(n/2) + n, T(1) = 1
    if (n <= 1) return 1;
    if (memo.count(n)) return memo[n];
    return memo[n] = 2 * T(n / 2) + n;
}

int main() {
    printf("%10s %14s %14s\n", "n", "T(n)", "T(n)/(n log n)");
    for (long n = 16; n <= (1L << 24); n *= 16)
        printf("%10ld %14.0f %14.4f\n", n, T(n), T(n) / (n * log2((double)n)));
    return 0;
}

Output

         n           T(n) T(n)/(n log n)
        16             80         1.2500
       256           2304         1.1250
      4096          53248         1.0833
     65536        1114112         1.0625
   1048576       22020096         1.0500
  16777216      419430400         1.0417

Try it Yourself

The ratio T(n)/(n log n) settles towards 1, confirming Θ(n log n).

Chapter 5 · Divide and Conquer

Divide and Conquer

The divide, conquer, combine paradigm with full analysis of binary search, merge sort and quick sort, including quick sort's worst case and randomised pivots.

Divide and conquer solves a problem in three steps:

Divide the problem into smaller subproblems of the same kind.
Conquer the subproblems recursively (solve tiny ones directly).
Combine the sub-solutions into a solution for the original problem.

Its running time naturally forms a recurrence T(n) = a·T(n/b) + D(n) + C(n), where D and C are the costs of dividing and combining — tailor-made for the Master Theorem.

Binary search

Divide: compare with the middle element — O(1).
Conquer: search one half.
Combine: nothing.

T(n) = T(n/2) + O(1) → Θ(log n).

Merge sort

Divide: split at the middle — O(1).
Conquer: sort both halves recursively.
Combine: merge two sorted halves — Θ(n).

T(n) = 2T(n/2) + Θ(n) → Θ(n log n) in every case.

C++

#include <iostream>
#include <vector>
using namespace std;

long comparisons = 0;

void merge(vector<int> &a, int lo, int mid, int hi) {
    vector<int> left(a.begin() + lo, a.begin() + mid + 1), right(a.begin() + mid + 1, a.begin() + hi + 1);
    size_t i = 0, j = 0;
    int k = lo;
    while (i < left.size() && j < right.size()) {
        comparisons++;
        a[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    while (i < left.size()) a[k++] = left[i++];
    while (j < right.size()) a[k++] = right[j++];
}

void mergeSort(vector<int> &a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

int main() {
    vector<int> a = {38, 27, 43, 3, 9, 82, 10, 19};
    mergeSort(a, 0, (int)a.size() - 1);
    for (int x : a) cout << x << " ";
    cout << "\ncomparisons: " << comparisons << " (n log2 n = 24)" << endl;
    return 0;
}

Output

3 9 10 19 27 38 43 82 
comparisons: 17 (n log2 n = 24)

Try it Yourself

The divide phase of merge sort on 8 elements: log₂ 8 = 3 levels of splitting. Merging then climbs back up, doing n work per level.

Quick sort

Divide: partition around a pivot — Θ(n). After partitioning, the pivot is in its final position.
Conquer: sort the two parts recursively.
Combine: nothing.

Case	Partition split	Recurrence	Time
Best	always in half	T(n) = 2T(n/2) + n	Θ(n log n)
Worst	always 0 and n − 1 (sorted input, first/last pivot)	T(n) = T(n − 1) + n	Θ(n²)
Average	random splits	—	Θ(n log n), about 1.39 n log₂ n comparisons

Even a consistently lopsided 9-to-1 split gives T(n) = T(9n/10) + T(n/10) + n = Θ(n log n). Only extreme imbalance hurts.

Randomised quick sort

Picking the pivot uniformly at random makes the expected running time Θ(n log n) for every input — no specific input can trigger the worst case reliably.

C++

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

mt19937 rng(42);
long comparisons;

int partition(vector<int> &a, int lo, int hi) {           // Lomuto, pivot at a[hi]
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        comparisons++;
        if (a[j] < pivot) swap(a[++i], a[j]);
    }
    swap(a[i + 1], a[hi]);
    return i + 1;
}

void quickSort(vector<int> &a, int lo, int hi, bool randomPivot) {
    if (lo >= hi) return;
    if (randomPivot) swap(a[uniform_int_distribution<int>(lo, hi)(rng)], a[hi]);
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1, randomPivot);
    quickSort(a, p + 1, hi, randomPivot);
}

int main() {
    int n = 2000;
    vector<int> sortedInput(n);
    for (int i = 0; i < n; i++) sortedInput[i] = i;

    vector<int> a = sortedInput;
    comparisons = 0; quickSort(a, 0, n - 1, false);
    cout << "last-element pivot on sorted input: " << comparisons << " comparisons (about n^2/2)" << endl;

    a = sortedInput;
    comparisons = 0; quickSort(a, 0, n - 1, true);
    cout << "random pivot on sorted input:       " << comparisons << " comparisons (about 1.39 n log2 n)" << endl;
    cout << "still sorted correctly: " << boolalpha << is_sorted(a.begin(), a.end()) << endl;
    return 0;
}

Output

last-element pivot on sorted input: 1999000 comparisons (about n^2/2)
random pivot on sorted input:       22963 comparisons (about 1.39 n log2 n)
still sorted correctly: true

Try it Yourself

Merge sort vs quick sort

	Merge sort	Quick sort
Worst case	Θ(n log n)	Θ(n²) (rare with random pivots)
Extra space	Θ(n)	Θ(log n) stack
Stable	yes	no
Work happens in	the combine step	the divide step
In practice	linked lists, external sorting	arrays in memory (fast, cache-friendly)

Chapter 6 · Divide and Conquer

More Divide and Conquer

Max–min with fewer comparisons, counting inversions with merge sort, Karatsuba's fast multiplication and Strassen's matrix multiplication.

Finding the maximum and minimum

Finding both the max and min of n numbers naively takes 2(n − 1) comparisons. Divide and conquer does it in about 3n/2 − 2:

Split the array in half; find (max, min) of each half recursively.
Combine with two comparisons: max of the maxes, min of the mins.

T(n) = 2T(n/2) + 2, T(2) = 1, T(1) = 0 → T(n) = 3n/2 − 2 for n a power of two.

C++

#include <iostream>
#include <vector>
using namespace std;

int comps = 0;

pair<int, int> maxMin(const vector<int> &a, int lo, int hi) {
    if (lo == hi) return {a[lo], a[lo]};
    if (hi == lo + 1) {
        comps++;
        return a[lo] > a[hi] ? make_pair(a[lo], a[hi]) : make_pair(a[hi], a[lo]);
    }
    int mid = (lo + hi) / 2;
    auto [max1, min1] = maxMin(a, lo, mid);
    auto [max2, min2] = maxMin(a, mid + 1, hi);
    comps += 2;
    return {max(max1, max2), min(min1, min2)};
}

int main() {
    vector<int> a = {22, 13, -5, -8, 15, 60, 17, 31, 47, 9, 3, 50, 2, 41, 11, 28};
    auto [mx, mn] = maxMin(a, 0, (int)a.size() - 1);
    cout << "max " << mx << ", min " << mn << ", comparisons " << comps
         << " (naive: " << 2 * (a.size() - 1) << ")" << endl;
    return 0;
}

Output

max 60, min -8, comparisons 22 (naive: 30)

Try it Yourself

Counting inversions

An inversion is a pair i < j with a[i] > a[j]. The count measures how "unsorted" an array is (used in ranking similarity, e.g. comparing two people's movie rankings). Checking all pairs is Θ(n²). Piggyback on merge sort: while merging, whenever an element from the right half is placed before remaining left-half elements, it forms an inversion with each of them.

C++

#include <iostream>
#include <vector>
using namespace std;

long long mergeCount(vector<int> &a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    long long inv = mergeCount(a, lo, mid) + mergeCount(a, mid + 1, hi);
    vector<int> tmp;
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { tmp.push_back(a[j++]); inv += mid - i + 1; }   // a[j] beats all remaining left elements
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi) tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + lo);
    return inv;
}

int main() {
    vector<int> a = {2, 4, 1, 3, 5};
    vector<int> b = {5, 4, 3, 2, 1};
    cout << "inversions in {2,4,1,3,5}: " << mergeCount(a, 0, 4) << endl;   // (2,1) (4,1) (4,3)
    cout << "inversions in {5,4,3,2,1}: " << mergeCount(b, 0, 4) << endl;   // n(n-1)/2
    return 0;
}

Output

inversions in {2,4,1,3,5}: 3
inversions in {5,4,3,2,1}: 10

Try it Yourself

Θ(n log n) instead of Θ(n²).

Karatsuba multiplication

Multiplying two n-digit numbers the school way takes Θ(n²) digit operations. Split each number into halves: x = a·10^m + b and y = c·10^m + d. Then

x·y = ac·10^(2m) + (ad + bc)·10^m + bd.

That needs four half-size products: T(n) = 4T(n/2) + O(n) = Θ(n²) — no gain. Karatsuba's trick (1960) computes the middle term with one extra product:

ad + bc = (a + b)(c + d) − ac − bd

So only three multiplications are needed: T(n) = 3T(n/2) + O(n) = Θ(n^1.585).

C++

#include <iostream>
#include <cmath>
using namespace std;

long long karatsuba(long long x, long long y) {
    if (x < 10 || y < 10) return x * y;
    int digits = max(to_string(x).size(), to_string(y).size());
    int m = digits / 2;
    long long p = (long long)pow(10, m);
    long long a = x / p, b = x % p, c = y / p, d = y % p;
    long long ac = karatsuba(a, c);
    long long bd = karatsuba(b, d);
    long long mid = karatsuba(a + b, c + d) - ac - bd;     // = ad + bc with one multiplication
    return ac * p * p + mid * p + bd;
}

int main() {
    long long x = 12345678, y = 87654321;
    cout << karatsuba(x, y) << endl;
    cout << x * y << " (built-in, for comparison)" << endl;
    return 0;
}

Output

1082152022374638
1082152022374638 (built-in, for comparison)

Try it Yourself

Strassen's matrix multiplication

Ordinary multiplication of two n × n matrices takes Θ(n³). Splitting each matrix into four (n/2) × (n/2) blocks gives 8 block multiplications: T(n) = 8T(n/2) + Θ(n²) = Θ(n³).

Strassen (1969) found a way to combine the blocks using only 7 multiplications (and 18 additions/subtractions):

Product	Formula
M₁	(A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂	(A₂₁ + A₂₂)B₁₁
M₃	A₁₁(B₁₂ − B₂₂)
M₄	A₂₂(B₂₁ − B₁₁)
M₅	(A₁₁ + A₁₂)B₂₂
M₆	(A₂₁ − A₁₁)(B₁₁ + B₁₂)
M₇	(A₁₂ − A₂₂)(B₂₁ + B₂₂)

C₁₁ = M₁ + M₄ − M₅ + M₇, C₁₂ = M₃ + M₅, C₂₁ = M₂ + M₄, C₂₂ = M₁ − M₂ + M₃ + M₆.

T(n) = 7T(n/2) + Θ(n²) = Θ(n^log₂7) ≈ Θ(n^2.81).

C++

#include <iostream>
using namespace std;

int main() {      // Strassen's seven products on 2x2 matrices of numbers
    int a11 = 1, a12 = 3, a21 = 7, a22 = 5;
    int b11 = 6, b12 = 8, b21 = 4, b22 = 2;
    int m1 = (a11 + a22) * (b11 + b22), m2 = (a21 + a22) * b11, m3 = a11 * (b12 - b22);
    int m4 = a22 * (b21 - b11), m5 = (a11 + a12) * b22, m6 = (a21 - a11) * (b11 + b12);
    int m7 = (a12 - a22) * (b21 + b22);
    cout << "Strassen: " << m1 + m4 - m5 + m7 << " " << m3 + m5 << " / " << m2 + m4 << " " << m1 - m2 + m3 + m6 << endl;
    cout << "Normal:   " << a11 * b11 + a12 * b21 << " " << a11 * b12 + a12 * b22 << " / "
         << a21 * b11 + a22 * b21 << " " << a21 * b12 + a22 * b22 << endl;
    return 0;
}

Output

Strassen: 18 14 / 62 66
Normal:   18 14 / 62 66

Try it Yourself

Chapter 7 · Greedy Algorithms

The Greedy Method

Make the locally best choice at every step: the greedy-choice property, activity selection, fractional knapsack, job sequencing with deadlines, and when greedy fails.

A greedy algorithm builds a solution step by step, always making the choice that looks best right now, and never reconsidering it. Greedy algorithms are simple and fast — but they are only correct for problems with two properties:

Greedy-choice property — a globally optimal solution can be reached by making a locally optimal choice.
Optimal substructure — an optimal solution contains optimal solutions to its subproblems.

When greedy fails

Give change for 6 using coins {1, 3, 4}. Greedy takes the largest coin first: 4 + 1 + 1 = 3 coins. But 3 + 3 = 2 coins. Greedy is wrong here — that problem needs dynamic programming. With Indian currency denominations (1, 2, 5, 10, 20, 50 …), greedy happens to be optimal.

Activity selection

Given activities with start and finish times, choose the maximum number of non-overlapping activities (one room, many meetings).

Greedy rule: sort by finish time and repeatedly pick the activity that finishes earliest among those compatible with what you already picked. Finishing early leaves the most room for the rest.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity { char name; int start, finish; };

int main() {
    vector<Activity> acts = {{'A', 1, 4}, {'B', 3, 5}, {'C', 0, 6}, {'D', 5, 7}, {'E', 3, 9},
                             {'F', 5, 9}, {'G', 6, 10}, {'H', 8, 11}, {'I', 8, 12}, {'J', 2, 14}, {'K', 12, 16}};
    sort(acts.begin(), acts.end(), [](const Activity &a, const Activity &b) { return a.finish < b.finish; });
    int lastFinish = -1;
    cout << "Selected:";
    for (const auto &a : acts)
        if (a.start >= lastFinish) {
            cout << " " << a.name << "(" << a.start << "-" << a.finish << ")";
            lastFinish = a.finish;
        }
    cout << endl;
    return 0;
}

Output

Selected: A(1-4) D(5-7) H(8-11) K(12-16)

Try it Yourself

Time: Θ(n log n) for sorting, then Θ(n).

Fractional knapsack

A thief's knapsack holds weight W. Items have values and weights, and fractions of items may be taken (gold dust, not gold bars). Maximise value.

Greedy rule: take items in decreasing order of value per unit weight, taking a fraction of the last one if it does not fit.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Item { const char *name; double value, weight; };

int main() {
    vector<Item> items = {{"silver", 60, 10}, {"gold", 100, 20}, {"silk", 120, 30}};
    double capacity = 50, total = 0;
    sort(items.begin(), items.end(), [](const Item &a, const Item &b) {
        return a.value / a.weight > b.value / b.weight;          // best ratio first
    });
    cout << fixed << setprecision(2);
    for (const auto &it : items) {
        if (capacity <= 0) break;
        double take = min(it.weight, capacity);
        total += take / it.weight * it.value;
        capacity -= take;
        cout << "take " << take << " kg of " << it.name << " (ratio " << it.value / it.weight << ")" << endl;
    }
    cout << "maximum value = " << total << endl;
    return 0;
}

Output

take 10.00 kg of silver (ratio 6.00)
take 20.00 kg of gold (ratio 5.00)
take 20.00 kg of silk (ratio 4.00)
maximum value = 240.00

Try it Yourself

Job sequencing with deadlines

Each job takes one unit of time, has a deadline and a profit earned only if finished by its deadline. Maximise total profit.

Greedy rule: consider jobs in decreasing order of profit, and schedule each in the latest free slot on or before its deadline.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Job { char id; int deadline, profit; };

int main() {
    vector<Job> jobs = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    sort(jobs.begin(), jobs.end(), [](const Job &x, const Job &y) { return x.profit > y.profit; });
    int maxD = 0;
    for (auto &j : jobs) maxD = max(maxD, j.deadline);
    vector<char> slot(maxD + 1, '-');
    int profit = 0;
    for (auto &j : jobs)
        for (int t = j.deadline; t >= 1; t--)
            if (slot[t] == '-') { slot[t] = j.id; profit += j.profit; break; }
    cout << "schedule:";
    for (int t = 1; t <= maxD; t++) cout << " slot" << t << "=" << slot[t];
    cout << "\ntotal profit = " << profit << endl;
    return 0;
}

Output

schedule: slot1=c slot2=a slot3=e
total profit = 142

Try it Yourself

Greedy algorithms you will meet

Problem	Greedy rule	Lesson
Activity selection	earliest finish time	this one
Fractional knapsack	highest value/weight	this one
Job sequencing	highest profit, latest free slot	this one
Huffman coding	merge the two least frequent symbols	Huffman Coding
Minimum spanning tree	cheapest safe edge	Kruskal & Prim
Single-source shortest paths	closest unvisited vertex	Dijkstra

Chapter 8 · Greedy Algorithms

Huffman Coding

Optimal prefix-free codes for data compression: why prefix codes, building the Huffman tree with a min-priority queue, reading off codes, and computing the compressed size.

Text is stored with fixed-length codes: ASCII uses 8 bits for every character. But in English text, e is far more common than z. Huffman coding (David Huffman, 1952) gives frequent characters short codes and rare characters long codes, producing an optimal compression for a given set of frequencies. It is used inside ZIP, gzip, PNG and JPEG.

Prefix-free codes

To decode a bit stream without separators, no code may be a prefix of another. If a = 0 and b = 01, then 01 could be "ab…" or "b". Huffman codes are always prefix-free because every character sits at a leaf of a binary tree.

The algorithm

Create a leaf node for each character with its frequency, and put them all in a min-priority queue.
Repeat until one node remains:
- Remove the two lowest-frequency nodes.
- Create a new internal node with these two as children and frequency = their sum.
- Insert it back into the queue.
The remaining node is the root. Label left edges 0 and right edges 1; each character's code is the path from the root.

The greedy choice is "merge the two rarest symbols first", which pushes them deepest into the tree.

Example

Character	a	b	c	d	e	f
Frequency	45	13	12	16	9	5

Merges: f(5)+e(9)=14 → c(12)+b(13)=25 → 14+d(16)=30 → 25+30=55 → a(45)+55=100.

The Huffman tree. Left edges are 0, right edges are 1, so a = 0, c = 100, b = 101, f = 1100, e = 1101, d = 111.

C++

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char c, int f, Node *l = nullptr, Node *r = nullptr) : ch(c), freq(f), left(l), right(r) {}
};

struct ByFreq {
    bool operator()(Node *a, Node *b) const {
        return a->freq != b->freq ? a->freq > b->freq : a->ch > b->ch;   // min-heap, ties broken by char
    }
};

void collect(Node *n, const string &code, map<char, string> &codes) {
    if (!n->left) { codes[n->ch] = code.empty() ? "0" : code; return; }
    collect(n->left, code + "0", codes);
    collect(n->right, code + "1", codes);
}

int main() {
    vector<pair<char, int>> freq = {{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}};
    priority_queue<Node *, vector<Node *>, ByFreq> pq;
    for (auto [c, f] : freq) pq.push(new Node(c, f));
    char nextId = '1';                       // labels for internal nodes, used only for tie-breaking
    while (pq.size() > 1) {
        Node *x = pq.top(); pq.pop();
        Node *y = pq.top(); pq.pop();
        pq.push(new Node(nextId++, x->freq + y->freq, x, y));
    }
    map<char, string> codes;
    collect(pq.top(), "", codes);
    int bits = 0, total = 0;
    for (auto [c, f] : freq) {
        cout << c << " (freq " << f << "): " << codes[c] << endl;
        bits += f * codes[c].size();
        total += f;
    }
    cout << "Huffman bits: " << bits << ", fixed 3-bit code: " << total * 3
         << ", saving " << 100 - bits * 100 / (total * 3) << "%" << endl;
    return 0;
}

Output

a (freq 45): 0
b (freq 13): 101
c (freq 12): 100
d (freq 16): 111
e (freq 9): 1101
f (freq 5): 1100
Huffman bits: 224, fixed 3-bit code: 300, saving 26%

Try it Yourself

The program's codes may differ from the diagram in which child goes left (ties can be broken either way), but the code lengths and total bits are always the same: 224 bits versus 300 for a fixed 3-bit code.

Analysis

n − 1 merges, each doing O(log n) priority-queue operations → O(n log n).
Huffman's code is optimal among prefix codes: no other prefix code gives a smaller total Σ freq × code length.

Decoding

Start at the root; read bits, going left on 0 and right on 1; when you reach a leaf, output its character and return to the root. With the codes in the diagram, 0101100 splits in only one way, 0 | 101 | 100, and decodes to abc.

Chapter 9 · Greedy Algorithms

Minimum Spanning Trees

Connect every vertex at minimum total cost: spanning trees, Kruskal's algorithm with union-find, Prim's algorithm with a priority queue, traced on the same graph.

A spanning tree of a connected, undirected graph is a subset of its edges that connects all vertices with no cycles — exactly V − 1 edges. A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.

Uses: laying cable or pipelines to connect cities at minimum cost, designing networks, clustering, and approximating harder problems like TSP.

A weighted graph with its minimum spanning tree highlighted: C–E (2), A–B (4), C–F (5), C–D (7) and A–F (8), total weight 26. Because all weights are distinct, this MST is unique.

Kruskal's algorithm

Greedy rule: consider edges from lightest to heaviest; add an edge if it does not create a cycle.

To test "would this edge create a cycle?" quickly, Kruskal uses a union-find (disjoint set) structure: each vertex starts in its own set; an edge (u, v) creates a cycle exactly when u and v are already in the same set.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Edge { int u, v, w; };
vector<int> parent;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }   // path compression

int main() {
    const char *name = "ABCDEF";
    vector<Edge> edges = {{0,1,4},{0,5,8},{1,2,10},{1,5,11},{2,3,7},{2,4,2},{2,5,5},{3,4,9},{4,5,6},{3,5,14}};
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; });
    parent.resize(6);
    iota(parent.begin(), parent.end(), 0);
    int total = 0, used = 0;
    for (const Edge &e : edges) {
        int ru = find(e.u), rv = find(e.v);
        cout << name[e.u] << "-" << name[e.v] << " (" << e.w << "): ";
        if (ru == rv) { cout << "skip, would form a cycle" << endl; continue; }
        parent[ru] = rv;                                   // union the two trees
        total += e.w;
        cout << "take" << endl;
        if (++used == 5) break;                            // V - 1 edges: done
    }
    cout << "MST weight = " << total << endl;
    return 0;
}

Output

C-E (2): take
A-B (4): take
C-F (5): take
E-F (6): skip, would form a cycle
C-D (7): take
A-F (8): take
MST weight = 26

Try it Yourself

Time: sorting dominates → O(E log E) (= O(E log V)).

Prim's algorithm

Greedy rule: grow one tree from a start vertex; at each step add the cheapest edge connecting the tree to a new vertex. A min-priority queue holds the candidate edges.

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    const char *name = "ABCDEF";
    int V = 6;
    vector<vector<pair<int, int>>> adj(V);          // (neighbour, weight)
    int e[][3] = {{0,1,4},{0,5,8},{1,2,10},{1,5,11},{2,3,7},{2,4,2},{2,5,5},{3,4,9},{4,5,6},{3,5,14}};
    for (auto &x : e) { adj[x[0]].push_back({x[1], x[2]}); adj[x[1]].push_back({x[0], x[2]}); }

    vector<bool> inTree(V, false);
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;   // (weight, vertex, from)
    pq.push({0, 0, -1});
    int total = 0;
    while (!pq.empty()) {
        auto [w, v, from] = pq.top(); pq.pop();
        if (inTree[v]) continue;                     // stale entry
        inTree[v] = true;
        total += w;
        if (from >= 0) cout << "add " << name[from] << "-" << name[v] << " (" << w << ")" << endl;
        for (auto [to, wt] : adj[v])
            if (!inTree[to]) pq.push({wt, to, v});
    }
    cout << "MST weight = " << total << endl;
    return 0;
}

Output

add A-B (4)
add A-F (8)
add F-C (5)
add C-E (2)
add C-D (7)
MST weight = 26

Try it Yourself

Time with a binary heap: O(E log V). With an adjacency matrix and no heap: O(V²), which is better for dense graphs.

Kruskal vs Prim

	Kruskal	Prim
Grows	a forest that merges into one tree	a single tree
Picks	globally lightest safe edge	lightest edge leaving the tree
Data structure	sorted edges + union-find	priority queue
Time	O(E log E)	O(E log V) with a heap; O(V²) with a matrix
Better for	sparse graphs	dense graphs

Both always find a minimum spanning tree. If all edge weights are distinct, the MST is unique, so both find the same one.

Chapter 10 · Greedy Algorithms

Shortest Paths: Dijkstra & Bellman–Ford

Single-source shortest paths in weighted graphs: relaxation, Dijkstra's greedy algorithm with a priority queue, why it fails on negative edges, and Bellman–Ford with negative-cycle detection.

Given a weighted graph and a source vertex s, find the shortest-path distance from s to every other vertex. (BFS solves this only when all edges have the same weight.)

Relaxation

Both algorithms repeatedly relax edges. For an edge u → v with weight w:

Pseudocode

RELAX(u, v, w)
    if dist[u] + w < dist[v]
        dist[v] = dist[u] + w
        parent[v] = u

"If going through u gives a shorter route to v, use it."

Dijkstra's algorithm

Greedy rule: repeatedly pick the unvisited vertex with the smallest known distance, mark it final, and relax its outgoing edges. Works when all edge weights are non-negative.

A directed weighted graph. The shortest path S → B → A → C → T has length 3 + 4 + 2 + 4 = 13.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <string>
using namespace std;

int main() {
    const string name = "SABCDT";
    int V = 6;
    vector<vector<pair<int, int>>> adj(V);
    int e[][3] = {{0,1,10},{0,2,3},{2,1,4},{1,3,2},{2,4,8},{2,3,9},{3,5,4},{4,5,5},{3,4,1}};
    for (auto &x : e) adj[x[0]].push_back({x[1], x[2]});

    vector<int> dist(V, INT_MAX), parent(V, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;   // (distance, vertex)
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                         // outdated entry
        cout << "finalise " << name[u] << " at distance " << d << endl;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {                   // relax
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
    }
    string path;
    for (int v = 5; v != -1; v = parent[v]) path = string(1, name[v]) + (path.empty() ? "" : " -> ") + path;
    cout << "shortest S to T: " << dist[5] << " via " << path << endl;
    return 0;
}

Output

finalise S at distance 0
finalise B at distance 3
finalise A at distance 7
finalise C at distance 9
finalise D at distance 10
finalise T at distance 13
shortest S to T: 13 via S -> B -> A -> C -> T

Try it Yourself

Time with a binary heap: O((V + E) log V).

Bellman–Ford

Relax every edge, V − 1 times. After round k, every shortest path using at most k edges is correct, and a shortest path never needs more than V − 1 edges. A V-th round that still improves some distance proves a negative cycle is reachable (no shortest path exists).

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

void bellmanFord(int V, const vector<Edge> &edges, int src) {
    vector<long> dist(V, LONG_MAX);
    dist[src] = 0;
    for (int round = 1; round < V; round++)
        for (const Edge &e : edges)
            if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v]) dist[e.v] = dist[e.u] + e.w;
    for (const Edge &e : edges)
        if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v]) { cout << "negative cycle detected!" << endl; return; }
    for (int v = 0; v < V; v++) cout << "dist[" << v << "] = " << dist[v] << endl;
}

int main() {
    vector<Edge> g1 = {{0,1,6},{0,2,7},{1,2,8},{1,3,5},{1,4,-4},{2,3,-3},{2,4,9},{3,1,-2},{4,0,2},{4,3,7}};
    bellmanFord(5, g1, 0);
    cout << "---" << endl;
    vector<Edge> g2 = {{0,1,1},{1,2,-1},{2,3,-1},{3,1,-1}};      // cycle 1 -> 2 -> 3 -> 1 has weight -3
    bellmanFord(4, g2, 0);
    return 0;
}

Output

dist[0] = 0
dist[1] = 2
dist[2] = 7
dist[3] = 4
dist[4] = -2
---
negative cycle detected!

Try it Yourself

Time: O(V · E) — slower than Dijkstra but handles negative weights.

Comparison

	BFS	Dijkstra	Bellman–Ford	Floyd–Warshall
Edge weights	all equal	non-negative	any (detects negative cycles)	any (no negative cycles)
Sources	single	single	single	all pairs
Time	O(V + E)	O((V + E) log V)	O(VE)	O(V³)
Technique	traversal	greedy	dynamic programming	dynamic programming

Chapter 11 · Dynamic Programming

Dynamic Programming

Solve each subproblem once: overlapping subproblems and optimal substructure, memoisation vs tabulation, and DP solutions for Fibonacci and coin change.

Dynamic programming (DP) solves problems by combining solutions to subproblems — like divide and conquer — but for problems whose subproblems overlap. Instead of recomputing a subproblem every time it appears, DP solves it once and stores the answer.

A problem suits DP when it has:

Optimal substructure — an optimal solution is built from optimal solutions to subproblems.
Overlapping subproblems — the same subproblems recur many times.

The problem with plain recursion

C++

#include <iostream>
using namespace std;

long calls = 0;
long fib(int n) { calls++; return n < 2 ? n : fib(n - 1) + fib(n - 2); }

int main() {
    for (int n : {10, 20, 30}) {
        calls = 0;
        long f = fib(n);
        cout << "fib(" << n << ") = " << f << " took " << calls << " calls" << endl;
    }
    return 0;
}

Output

fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(30) = 832040 took 2692537 calls

Try it Yourself

fib(30) makes over a million calls to compute only 31 distinct values. That is exponential waste.

Approach 1: memoisation (top-down)

Keep the recursion, but cache each result the first time it is computed:

C++

#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo(91, -1);
long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];         // already solved
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    cout << "fib(90) = " << fib(90) << endl;   // instant: 91 subproblems, each solved once
    return 0;
}

Output

fib(90) = 2880067194370816120

Try it Yourself

Approach 2: tabulation (bottom-up)

Fill a table from the smallest subproblems upward, so every value you need is already there:

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 90;
    vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    cout << "fib(90) = " << dp[n] << endl;

    long long a = 0, b = 1;                     // only the last two values are needed: O(1) space
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    cout << "fib(90) = " << a << " (constant space)" << endl;
    return 0;
}

Output

fib(90) = 2880067194370816120
fib(90) = 2880067194370816120 (constant space)

Try it Yourself

	Memoisation (top-down)	Tabulation (bottom-up)
Style	recursive + cache	iterative table
Solves	only the subproblems actually needed	every subproblem
Overhead	function calls, recursion depth	none
Easier to write	often yes — follows the recurrence	needs a correct fill order
Space saving tricks	harder	easy (keep only needed rows)

The DP recipe

Define the state: what does dp[i] (or dp[i][j]) mean, in words?
Write the recurrence: how does a state depend on smaller states?
Base cases.
Fill order: make sure dependencies are computed first.
Answer: which cell holds the final result? (Optionally trace back the choices.)

Example: coin change

Coins {1, 3, 4}, amount 6. Greedy gave 3 coins; DP finds the true minimum.

State: dp[x] = minimum number of coins that make amount x. Recurrence: dp[x] = 1 + min(dp[x − c]) over coins c ≤ x. Base: dp[0] = 0.

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    vector<int> dp(amount + 1, INT_MAX), choice(amount + 1, -1), ways(amount + 1, 0);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x && dp[x - c] != INT_MAX && dp[x - c] + 1 < dp[x]) { dp[x] = dp[x - c] + 1; choice[x] = c; }

    cout << "x:     "; for (int x = 0; x <= amount; x++) cout << x << " ";
    cout << "\ndp[x]: "; for (int x = 0; x <= amount; x++) cout << dp[x] << " ";
    cout << "\nminimum coins for " << amount << " = " << dp[amount] << ": ";
    for (int x = amount; x > 0; x -= choice[x]) cout << choice[x] << " ";
    cout << endl;

    ways[0] = 1;                                   // number of ways (order does not matter)
    for (int c : coins) for (int x = c; x <= amount; x++) ways[x] += ways[x - c];
    cout << "number of ways to make " << amount << " = " << ways[amount] << endl;
    return 0;
}

Output

x:     0 1 2 3 4 5 6 
dp[x]: 0 1 2 1 1 2 2 
minimum coins for 6 = 2: 3 3 
number of ways to make 6 = 4

Try it Yourself

Time O(amount × coins). The second loop answers a different question — how many combinations — with the coin loop outside so each combination is counted once.

DP vs divide and conquer vs greedy

	Divide & conquer	Dynamic programming	Greedy
Subproblems	independent	overlapping	one choice, then one subproblem
Choices	none	tries all, keeps the best	commits to the locally best
Examples	merge sort, quick sort	knapsack, LCS, Floyd–Warshall	Huffman, Kruskal, Dijkstra

Chapter 12 · Dynamic Programming

0/1 Knapsack

Choose whole items to maximise value within a weight limit: the DP table, the recurrence, tracing back the chosen items, and a space-optimised version.

You have n items, each with a weight and a value, and a knapsack of capacity W. Each item is taken whole or not at all (0 or 1). Maximise the total value without exceeding W.

Greedy by value-per-weight fails here (see the greedy lesson); trying all 2ⁿ subsets is too slow. DP solves it in O(nW).

State and recurrence

State: dp[i][w] = the best value achievable using the first i items with capacity w.

For item i (weight wᵢ, value vᵢ), either skip it or take it (if it fits):

dp[i][w] = dp[i−1][w] if wᵢ > w dp[i][w] = max(dp[i−1][w], vᵢ + dp[i−1][w − wᵢ]) otherwise

Base: dp[0][w] = 0 (no items) and dp[i][0] = 0 (no capacity). Answer: dp[n][W].

Watch the table fill

Code with traceback

C++

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
using namespace std;

int main() {
    vector<string> name = {"", "A", "B", "C", "D"};
    vector<int> wt = {0, 1, 3, 4, 5}, val = {0, 1, 4, 5, 7};
    int n = 4, W = 7;
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];                                    // skip item i
            if (wt[i] <= w) dp[i][w] = max(dp[i][w], val[i] + dp[i - 1][w - wt[i]]);   // or take it
        }

    cout << "item\\w";
    for (int w = 0; w <= W; w++) cout << setw(3) << w;
    cout << endl;
    for (int i = 0; i <= n; i++) {
        cout << setw(6) << (i ? name[i] + "(" + to_string(wt[i]) + "," + to_string(val[i]) + ")" : "-");
        for (int w = 0; w <= W; w++) cout << setw(3) << dp[i][w];
        cout << endl;
    }

    cout << "best value = " << dp[n][W] << ", items:";
    for (int i = n, w = W; i > 0; i--)
        if (dp[i][w] != dp[i - 1][w]) { cout << " " << name[i]; w -= wt[i]; }   // value changed: i was taken
    cout << endl;
    return 0;
}

Output

item\w  0  1  2  3  4  5  6  7
     -  0  0  0  0  0  0  0  0
A(1,1)  0  1  1  1  1  1  1  1
B(3,4)  0  1  1  4  5  5  5  5
C(4,5)  0  1  1  4  5  6  6  9
D(5,7)  0  1  1  4  5  7  8  9
best value = 9, items: C B

Try it Yourself

Traceback: start at dp[n][W]. If the value equals the cell above, item i was skipped; otherwise it was taken — subtract its weight and move up.

Space optimisation

Each row depends only on the previous row, so one 1-D array suffices if you loop w downwards (so each item is used at most once):

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> wt = {1, 3, 4, 5}, val = {1, 4, 5, 7};
    int W = 7;
    vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < wt.size(); i++)
        for (int w = W; w >= wt[i]; w--)                 // downwards!
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
    cout << "best value = " << dp[W] << endl;
    return 0;
}

Output

best value = 9

Try it Yourself

Looping w upwards would allow an item to be reused — which solves the unbounded knapsack instead.

Chapter 13 · Dynamic Programming

Longest Common Subsequence

Find the longest sequence common to two strings: subsequences vs substrings, the LCS table and recurrence, traceback, and the related edit-distance problem.

A subsequence keeps characters in order but may skip some: "ACE" is a subsequence of "ABCDE". (A substring must be contiguous.) The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both.

LCS powers diff tools, version control, DNA sequence alignment and plagiarism detection.

Recurrence

State: L[i][j] = length of the LCS of the first i characters of X and the first j characters of Y.

L[i][j] = 0 if i = 0 or j = 0 L[i][j] = L[i−1][j−1] + 1 if X[i] = Y[j] L[i][j] = max(L[i−1][j], L[i][j−1]) otherwise

If the last characters match, they extend the LCS of the shorter prefixes. If not, drop one of them — whichever gives the longer result.

Watch it fill

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string X = "ABCBDAB", Y = "BDCABA";
    int m = X.size(), n = Y.size();
    vector<vector<int>> L(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            L[i][j] = (X[i - 1] == Y[j - 1]) ? L[i - 1][j - 1] + 1 : max(L[i - 1][j], L[i][j - 1]);

    cout << "    ";
    for (char c : Y) cout << " " << c;
    cout << endl;
    for (int i = 0; i <= m; i++) {
        cout << (i ? X[i - 1] : ' ') << " ";
        for (int j = 0; j <= n; j++) cout << " " << L[i][j];
        cout << endl;
    }

    string lcs;                                         // trace back from the bottom-right corner
    for (int i = m, j = n; i > 0 && j > 0; ) {
        if (X[i - 1] == Y[j - 1]) { lcs += X[i - 1]; i--; j--; }
        else if (L[i - 1][j] >= L[i][j - 1]) i--;
        else j--;
    }
    reverse(lcs.begin(), lcs.end());
    cout << "LCS length " << L[m][n] << ": " << lcs << endl;
    return 0;
}

Output

     B D C A B A
   0 0 0 0 0 0 0
A  0 0 0 0 1 1 1
B  0 1 1 1 1 2 2
C  0 1 1 2 2 2 2
B  0 1 1 2 2 3 3
D  0 1 2 2 2 3 3
A  0 1 2 2 3 3 4
B  0 1 2 2 3 4 4
LCS length 4: BCBA

Try it Yourself

Time and space O(mn). Brute force would check all 2ᵐ subsequences of X.

The edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions and substitutions that turn one string into another — the basis of spell checkers.

D[i][j] = D[i−1][j−1] if X[i] = Y[j] D[i][j] = 1 + min(D[i−1][j] (delete), D[i][j−1] (insert), D[i−1][j−1] (substitute)) otherwise

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int editDistance(const string &a, const string &b) {
    vector<vector<int>> D(a.size() + 1, vector<int>(b.size() + 1));
    for (size_t i = 0; i <= a.size(); i++) D[i][0] = i;
    for (size_t j = 0; j <= b.size(); j++) D[0][j] = j;
    for (size_t i = 1; i <= a.size(); i++)
        for (size_t j = 1; j <= b.size(); j++)
            D[i][j] = a[i - 1] == b[j - 1] ? D[i - 1][j - 1]
                    : 1 + min({D[i - 1][j], D[i][j - 1], D[i - 1][j - 1]});
    return D[a.size()][b.size()];
}

int main() {
    cout << "kitten -> sitting: " << editDistance("kitten", "sitting") << endl;
    cout << "sunday -> saturday: " << editDistance("sunday", "saturday") << endl;
    cout << "algorithm -> altruistic: " << editDistance("algorithm", "altruistic") << endl;
    return 0;
}

Output

kitten -> sitting: 3
sunday -> saturday: 3
algorithm -> altruistic: 6

Try it Yourself

Chapter 14 · Dynamic Programming

Matrix Chain Multiplication

Find the cheapest way to parenthesise a product of matrices: why order matters, the m[i][j] recurrence, filling the table by chain length, and printing the optimal parenthesisation.

Multiplying a p × q matrix by a q × r matrix takes p·q·r scalar multiplications. Matrix multiplication is associative — (AB)C = A(BC) — but the cost depends on the order.

Example: A is 10 × 100, B is 100 × 5, C is 5 × 50.

Order	Cost
(AB)C	10·100·5 + 10·5·50 = 5,000 + 2,500 = 7,500
A(BC)	100·5·50 + 10·100·50 = 25,000 + 50,000 = 75,000

Ten times difference for three matrices. For a chain of n matrices, the number of parenthesisations grows exponentially (the Catalan numbers), so we use DP.

Recurrence

Matrix Aᵢ has dimensions p[i−1] × p[i]. State: m[i][j] = minimum cost to multiply Aᵢ … Aⱼ.

m[i][i] = 0 m[i][j] = min over i ≤ k < j of ( m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j] )

Split the chain after Aₖ: multiply the left part, the right part, then the two results. Store the best k in s[i][j] to rebuild the parenthesisation.

Fill order: by increasing chain length L = 2, 3, …, n (each cell needs shorter chains).

C++

#include <iostream>
#include <vector>
#include <climits>
#include <string>
using namespace std;

vector<vector<int>> s;
string paren(int i, int j) {
    if (i == j) return "A" + to_string(i);
    return "(" + paren(i, s[i][j]) + paren(s[i][j] + 1, j) + ")";
}

int main() {
    vector<int> p = {30, 35, 15, 5, 10, 20, 25};     // A1: 30x35, A2: 35x15, ..., A6: 20x25
    int n = p.size() - 1;
    vector<vector<long>> m(n + 1, vector<long>(n + 1, 0));
    s.assign(n + 1, vector<int>(n + 1, 0));
    for (int L = 2; L <= n; L++)
        for (int i = 1; i + L - 1 <= n; i++) {
            int j = i + L - 1;
            m[i][j] = LONG_MAX;
            for (int k = i; k < j; k++) {
                long cost = m[i][k] + m[k + 1][j] + (long)p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }
    cout << "minimum scalar multiplications: " << m[1][n] << endl;
    cout << "optimal order: " << paren(1, n) << endl;
    cout << "m[2][5] = " << m[2][5] << endl;
    return 0;
}

Output

minimum scalar multiplications: 15125
optimal order: ((A1(A2A3))((A4A5)A6))
m[2][5] = 7125

Try it Yourself

This is the classic CLRS example: the answer is 15,125 with ((A1(A2A3))((A4A5)A6)).

Time O(n³) (n² cells, each trying up to n splits), space O(n²).

Chapter 15 · Dynamic Programming

All-Pairs Shortest Paths: Floyd–Warshall

Shortest distances between every pair of vertices with a three-loop DP, its recurrence over intermediate vertices, negative-cycle detection, and Warshall's transitive closure.

Dijkstra and Bellman–Ford find shortest paths from one source. Floyd–Warshall finds them between all pairs in one go, works with negative edges (but not negative cycles), and is just three nested loops.

The idea

Number the vertices 1 … n. Let dᵏ[i][j] be the shortest distance from i to j using only vertices 1 … k as intermediate stops. Either the best path avoids vertex k, or it goes through k:

dᵏ[i][j] = min( dᵏ⁻¹[i][j], dᵏ⁻¹[i][k] + dᵏ⁻¹[k][j] )

Start with d⁰ = the edge weights (∞ where there is no edge, 0 on the diagonal). After k = n, every vertex has been allowed as an intermediate: the matrix holds all shortest distances. The table can be updated in place.

A directed graph with 4 vertices used in the program below.

C++

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int INF = 1e9;

void print(const vector<vector<int>> &d, int k) {
    cout << "after k = " << k << ":" << endl;
    for (auto &row : d) {
        for (int x : row) cout << setw(5) << (x >= INF ? string("inf") : to_string(x));
        cout << endl;
    }
}

int main() {
    int n = 4;
    vector<vector<int>> d = {
        {0,   3,   INF, 7},
        {8,   0,   2,   INF},
        {5,   INF, 0,   1},
        {2,   INF, INF, 0}};
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        if (k == 0 || k == n - 1) print(d, k + 1);
    }
    bool negCycle = false;
    for (int i = 0; i < n; i++) if (d[i][i] < 0) negCycle = true;
    cout << "negative cycle: " << (negCycle ? "yes" : "no") << endl;
    return 0;
}

Output

after k = 1:
    0    3  inf    7
    8    0    2   15
    5    8    0    1
    2    5  inf    0
after k = 4:
    0    3    5    6
    5    0    2    3
    3    6    0    1
    2    5    7    0
negative cycle: no

Try it Yourself

Time Θ(V³), space Θ(V²). It is the best choice for dense graphs or when you need every pair. A negative value on the diagonal at the end means a negative cycle.

Warshall's algorithm: transitive closure

Replace min and + with OR and AND to answer "is there any path from i to j?". The result is the transitive closure of the graph — see Relations in Discrete Mathematics.

C++

#include <iostream>
using namespace std;

int main() {
    int n = 4;
    int R[4][4] = {{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}, {1, 0, 1, 0}};
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
    cout << "reachability matrix:" << endl;
    for (auto &row : R) { for (int x : row) cout << " " << x; cout << endl; }
    return 0;
}

Output

reachability matrix:
 1 1 1 1
 1 1 1 1
 0 0 0 0
 1 1 1 1

Try it Yourself

Chapter 16 · Search, Graphs & Complexity

Backtracking

Explore a state-space tree and abandon dead ends early: the N-Queens problem, subset sum, graph colouring and Hamiltonian cycles.

Backtracking builds a solution one choice at a time. After each choice it checks whether the partial solution can still lead to a valid answer; if not, it undoes the last choice (backtracks) and tries the next option. It is a depth-first search of the state-space tree with pruning.

Pseudocode

BACKTRACK(partial)
    if partial is a complete solution: report it
    for each choice c that can extend partial
        if c keeps partial valid:        // the pruning test
            add c
            BACKTRACK(partial)
            remove c                     // undo: backtrack

N-Queens

Place N queens on an N × N chessboard so that no two attack each other (same row, column or diagonal). Place one queen per row; for each row, try every column that is safe.

C++

#include <iostream>
#include <vector>
using namespace std;

int n, solutions = 0, nodes = 0;
vector<int> col;                               // col[r] = column of the queen in row r

bool safe(int r, int c) {
    for (int i = 0; i < r; i++)
        if (col[i] == c || abs(col[i] - c) == r - i) return false;   // same column or diagonal
    return true;
}

void place(int r) {
    nodes++;
    if (r == n) {
        if (++solutions == 1) {                 // print the first solution as a board
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) cout << (col[i] == j ? "Q " : ". ");
                cout << endl;
            }
        }
        return;
    }
    for (int c = 0; c < n; c++)
        if (safe(r, c)) { col[r] = c; place(r + 1); }       // choose, explore (undo is implicit)
}

int main() {
    for (n = 4; n <= 8; n += 4) {
        col.assign(n, -1); solutions = 0; nodes = 0;
        place(0);
        cout << n << "-queens: " << solutions << " solutions, " << nodes << " nodes explored" << endl << endl;
    }
    return 0;
}

Output

. Q . . 
. . . Q 
Q . . . 
. . Q . 
4-queens: 2 solutions, 17 nodes explored

Q . . . . . . . 
. . . . Q . . . 
. . . . . . . Q 
. . . . . Q . . 
. . Q . . . . . 
. . . . . . Q . 
. Q . . . . . . 
. . . Q . . . . 
8-queens: 92 solutions, 2057 nodes explored

Try it Yourself

Without pruning there would be 8⁸ ≈ 16.7 million placements for N = 8; backtracking explores about two thousand nodes.

Subset sum

Given positive integers and a target, find subsets that add up exactly to the target. For each number, branch on include or exclude; prune when the sum exceeds the target or the remaining numbers cannot reach it.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> w = {3, 5, 6, 7};
int target = 15;
vector<int> chosen;

void subsetSum(int i, int sum, int remaining) {
    if (sum == target) {
        cout << "{";
        for (size_t k = 0; k < chosen.size(); k++) cout << (k ? ", " : "") << chosen[k];
        cout << "}" << endl;
        return;
    }
    if (i == (int)w.size() || sum + remaining < target || sum > target) return;   // prune
    chosen.push_back(w[i]);
    subsetSum(i + 1, sum + w[i], remaining - w[i]);          // include w[i]
    chosen.pop_back();
    subsetSum(i + 1, sum, remaining - w[i]);                 // exclude w[i]
}

int main() {
    subsetSum(0, 0, 3 + 5 + 6 + 7);
    return 0;
}

Output

{3, 5, 7}

Try it Yourself

Graph colouring

Colour the vertices with at most m colours so that no two adjacent vertices share a colour. Try colours for each vertex in turn, backtracking on conflicts.

C++

#include <iostream>
#include <vector>
using namespace std;

int V = 5, m = 3;
int adj[5][5] = {{0,1,1,1,0},{1,0,1,0,1},{1,1,0,1,1},{1,0,1,0,1},{0,1,1,1,0}};
vector<int> colour(5, 0);

bool ok(int v, int c) {
    for (int u = 0; u < V; u++) if (adj[v][u] && colour[u] == c) return false;
    return true;
}

bool solve(int v) {
    if (v == V) return true;
    for (int c = 1; c <= m; c++)
        if (ok(v, c)) {
            colour[v] = c;
            if (solve(v + 1)) return true;
            colour[v] = 0;                     // backtrack
        }
    return false;
}

int main() {
    const char *names[] = {"red", "green", "blue"};
    if (solve(0)) for (int v = 0; v < V; v++) cout << "vertex " << v << ": " << names[colour[v] - 1] << endl;
    else cout << "not colourable with " << m << " colours" << endl;
    return 0;
}

Output

vertex 0: red
vertex 1: green
vertex 2: blue
vertex 3: green
vertex 4: red

Try it Yourself

The smallest m that works is the graph's chromatic number. Deciding whether a graph is 3-colourable is NP-complete.

Hamiltonian cycle

A Hamiltonian cycle visits every vertex exactly once and returns to the start. Backtracking extends a path one unvisited neighbour at a time and backtracks at dead ends. No polynomial algorithm is known; it is NP-complete.

Problem	Choice at each level	Pruning test
N-Queens	column for the next row	no attack
Subset sum	include / exclude next number	sum too big, or cannot reach target
Graph colouring	colour for the next vertex	no neighbour has that colour
Hamiltonian cycle	next vertex on the path	adjacent and unvisited
Sudoku	digit for the next empty cell	row, column and box rules

Chapter 17 · Search, Graphs & Complexity

Branch and Bound

Optimisation by bounding: FIFO, LIFO and least-cost branch and bound, solving 0/1 knapsack with an upper bound, and the travelling salesperson problem.

Branch and bound (B&B) is used for optimisation problems (find the best solution, not all solutions). Like backtracking, it explores a state-space tree, but at every node it computes a bound — the best value any solution in that subtree could possibly achieve. If the bound is no better than the best complete solution found so far, the whole subtree is pruned.

	Backtracking	Branch and bound
Problem type	decision / find all solutions	optimisation
Search order	depth-first	FIFO (BFS), LIFO (DFS) or least-cost (best-first)
Pruning	when a constraint fails	when the bound cannot beat the best so far
Examples	N-Queens, Sudoku	0/1 knapsack, TSP, job assignment

Search strategies

FIFO B&B — live nodes in a queue (breadth-first).
LIFO B&B — live nodes in a stack (depth-first).
Least-cost (LC) B&B — live nodes in a priority queue, always expanding the most promising node first. Usually the fastest to reach the optimum.

0/1 knapsack with B&B

At each node, decide whether to include the next item. The upper bound of a node is its current value plus the value obtainable by filling the remaining capacity fractionally with the remaining items (sorted by value/weight). Since the fractional relaxation is never worse than the real 0/1 answer, it is a valid optimistic bound.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Item { int w, v; };
struct Node { int level, value, weight; double bound; };
vector<Item> items;
int W;

double bound(const Node &u) {
    if (u.weight >= W) return 0;
    double b = u.value;
    int w = u.weight, j = u.level + 1;
    for (; j < (int)items.size() && w + items[j].w <= W; j++) { w += items[j].w; b += items[j].v; }
    if (j < (int)items.size()) b += (W - w) * (double)items[j].v / items[j].w;   // fractional fill
    return b;
}

int main() {
    items = {{2, 40}, {5, 30}, {10, 50}, {5, 10}};   // (weight, value)
    W = 16;
    sort(items.begin(), items.end(), [](Item a, Item b) { return a.v * b.w > b.v * a.w; });
    auto cmp = [](const Node &a, const Node &b) { return a.bound < b.bound; };
    priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);   // least-cost: largest bound first
    Node root{-1, 0, 0, 0};
    root.bound = bound(root);
    pq.push(root);
    int best = 0, expanded = 0;
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (u.bound <= best || u.level == (int)items.size() - 1) continue;   // prune
        expanded++;
        Node take{u.level + 1, u.value + items[u.level + 1].v, u.weight + items[u.level + 1].w, 0};
        if (take.weight <= W && take.value > best) best = take.value;
        take.bound = bound(take);
        if (take.weight <= W && take.bound > best) pq.push(take);
        Node skip{u.level + 1, u.value, u.weight, 0};
        skip.bound = bound(skip);
        if (skip.bound > best) pq.push(skip);
    }
    cout << "best value = " << best << " (nodes expanded: " << expanded << ")" << endl;
    return 0;
}

Output

best value = 90 (nodes expanded: 5)

Try it Yourself

Travelling salesperson problem (TSP)

Visit every city exactly once and return home with the minimum total distance. Brute force checks (n − 1)! tours. B&B builds tours city by city and bounds each partial tour with a lower bound — for example, the cost so far plus, for every unvisited city, half the sum of its two cheapest edges, or the reduced-cost-matrix bound used in many textbooks. Partial tours whose bound already exceeds the best tour found are pruned.

TSP is NP-hard: B&B makes it practical for moderate sizes, but no polynomial algorithm is known. A DP solution (Held–Karp) runs in O(n² · 2ⁿ), far better than O(n!).

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int n = 4;
int dist[4][4] = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
int best = INT_MAX;
vector<int> path, bestPath;
vector<bool> used(4, false);

void tsp(int city, int cost) {
    if (cost >= best) return;                         // bound: cannot beat the best tour
    if ((int)path.size() == n) {
        if (cost + dist[city][0] < best) { best = cost + dist[city][0]; bestPath = path; }
        return;
    }
    for (int next = 0; next < n; next++)
        if (!used[next]) {
            used[next] = true; path.push_back(next);
            tsp(next, cost + dist[city][next]);
            used[next] = false; path.pop_back();
        }
}

int main() {
    used[0] = true; path = {0};
    tsp(0, 0);
    cout << "shortest tour: " << best << " via";
    for (int c : bestPath) cout << " " << c;
    cout << " 0" << endl;
    return 0;
}

Output

shortest tour: 80 via 0 1 3 2 0

Try it Yourself

Chapter 18 · Search, Graphs & Complexity

Topological Sort & Connectivity

Order tasks with dependencies using Kahn's algorithm and DFS, find connected and strongly connected components, and detect cycles in directed graphs.

Topological sort

A topological order of a directed acyclic graph (DAG) lists the vertices so that every edge u → v has u before v. It answers "in what order can I do these tasks?" — course prerequisites, build systems, spreadsheet recalculation, package installation.

Course prerequisites as a DAG. Any topological order is a valid study plan.

Kahn's algorithm (BFS)

Repeatedly output a vertex with in-degree 0 (no remaining prerequisites) and remove its outgoing edges.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int main() {
    vector<string> name = {"C1", "C2", "DS", "DM", "OOP", "DAA"};
    vector<vector<int>> adj(6);
    int edges[][2] = {{0, 2}, {1, 2}, {2, 5}, {3, 5}, {0, 4}, {2, 4}};
    vector<int> indeg(6, 0);
    for (auto &e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }

    queue<int> q;
    for (int v = 0; v < 6; v++) if (indeg[v] == 0) q.push(v);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if (order.size() < 6) cout << "cycle detected: no topological order" << endl;
    else { cout << "study order:"; for (int v : order) cout << " " << name[v]; cout << endl; }
    return 0;
}

Output

study order: C1 C2 DM DS DAA OOP

Try it Yourself

If some vertices never reach in-degree 0, the graph has a cycle and no topological order exists. Time O(V + E).

DFS-based topological sort

Run DFS; when a vertex finishes (all its descendants are done), push it onto a stack. Reading the stack top-down gives a topological order.

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<vector<int>> adj(6);
vector<int> state(6, 0);                 // 0 = new, 1 = on the current path, 2 = finished
vector<int> finishOrder;
bool cycle = false;

void dfs(int u) {
    state[u] = 1;
    for (int v : adj[u]) {
        if (state[v] == 1) cycle = true;            // back edge: a directed cycle
        else if (state[v] == 0) dfs(v);
    }
    state[u] = 2;
    finishOrder.push_back(u);
}

int main() {
    vector<string> name = {"C1", "C2", "DS", "DM", "OOP", "DAA"};
    int edges[][2] = {{0, 2}, {1, 2}, {2, 5}, {3, 5}, {0, 4}, {2, 4}};
    for (auto &e : edges) adj[e[0]].push_back(e[1]);
    for (int v = 0; v < 6; v++) if (state[v] == 0) dfs(v);
    cout << "topological order:";
    for (int i = (int)finishOrder.size() - 1; i >= 0; i--) cout << " " << name[finishOrder[i]];
    cout << "\ncycle: " << (cycle ? "yes" : "no") << endl;
    return 0;
}

Output

topological order: DM C2 C1 DS OOP DAA
cycle: no

Try it Yourself

The three DFS states also detect cycles in directed graphs: reaching a vertex that is still on the current path (state 1) means a back edge, hence a cycle.

Connected components

In an undirected graph, run BFS or DFS from each unvisited vertex; each run discovers one connected component. O(V + E).

Strongly connected components

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices where every vertex can reach every other. Kosaraju's algorithm finds all SCCs in O(V + E):

Run DFS on the graph and record vertices by finish time.
Reverse every edge.
Run DFS on the reversed graph in decreasing finish order; each tree found is one SCC.

C++

#include <iostream>
#include <vector>
using namespace std;

int V = 6;
vector<vector<int>> g(V), rg(V);
vector<bool> seen;
vector<int> order, comp;

void dfs1(int u) { seen[u] = true; for (int v : g[u]) if (!seen[v]) dfs1(v); order.push_back(u); }
void dfs2(int u) { seen[u] = true; comp.push_back(u); for (int v : rg[u]) if (!seen[v]) dfs2(v); }

int main() {
    int edges[][2] = {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}};
    for (auto &e : edges) { g[e[0]].push_back(e[1]); rg[e[1]].push_back(e[0]); }
    seen.assign(V, false);
    for (int v = 0; v < V; v++) if (!seen[v]) dfs1(v);
    seen.assign(V, false);
    for (int i = V - 1; i >= 0; i--)
        if (!seen[order[i]]) {
            comp.clear();
            dfs2(order[i]);
            cout << "SCC:";
            for (int v : comp) cout << " " << v;
            cout << endl;
        }
    return 0;
}

Output

SCC: 0 2 1
SCC: 3 5 4

Try it Yourself

Chapter 19 · Search, Graphs & Complexity

String Matching

Find a pattern in a text: the naive algorithm, Rabin–Karp's rolling hash, and the Knuth–Morris–Pratt algorithm with its prefix function — with complexities.

Given a text T of length n and a pattern P of length m, find every position where P occurs in T. This runs every time you press Ctrl+F, search DNA databases, or filter spam.

Naive algorithm

Try every alignment of P against T and compare character by character.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string T = "AABAACAADAABAABA", P = "AABA";
    int comparisons = 0;
    for (size_t s = 0; s + P.size() <= T.size(); s++) {
        size_t j = 0;
        while (j < P.size()) { comparisons++; if (T[s + j] != P[j]) break; j++; }
        if (j == P.size()) cout << "match at " << s << endl;
    }
    cout << "comparisons: " << comparisons << endl;
    return 0;
}

Output

match at 0
match at 9
match at 12
comparisons: 30

Try it Yourself

Worst case O((n − m + 1) · m), e.g. T = "aaaa…a", P = "aaab".

Rabin–Karp

Compare hash values first, and only compare characters when the hashes match. The trick is a rolling hash: the hash of the next window is computed from the previous one in O(1) by removing the leading character and adding the trailing one.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string T = "31415926535897932384626", P = "26";
    const long long base = 10, mod = 13;
    int n = T.size(), m = P.size();
    long long h = 1;                                   // base^(m-1) % mod
    for (int i = 0; i < m - 1; i++) h = h * base % mod;
    long long hp = 0, ht = 0;
    for (int i = 0; i < m; i++) { hp = (hp * base + (P[i] - '0')) % mod; ht = (ht * base + (T[i] - '0')) % mod; }
    int spurious = 0;
    for (int s = 0; s + m <= n; s++) {
        if (hp == ht) {
            if (T.compare(s, m, P) == 0) cout << "match at " << s << endl;
            else spurious++;                                 // hash collision
        }
        if (s + m < n) ht = ((ht - (T[s] - '0') * h % mod + mod) * base + (T[s + m] - '0')) % mod;   // roll
    }
    cout << "spurious hits: " << spurious << endl;
    return 0;
}

Output

match at 6
match at 21
spurious hits: 1

Try it Yourself

Expected time O(n + m); worst case O(nm) if many hashes collide (a "spurious hit"). Rabin–Karp shines when searching for many patterns at once.

Knuth–Morris–Pratt (KMP)

When a mismatch happens, the naive algorithm slides the pattern by one and re-checks characters it has already seen. KMP never moves backwards in the text. It precomputes the prefix function π (also called the LPS array): π[q] = the length of the longest proper prefix of P[0..q] that is also a suffix of it. On a mismatch, it shifts the pattern so that this already-matched prefix lines up.

For P = "ABABCABAB": π = [0, 0, 1, 2, 0, 1, 2, 3, 4].

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> prefixFunction(const string &P) {
    vector<int> pi(P.size(), 0);
    for (size_t q = 1, k = 0; q < P.size(); q++) {
        while (k > 0 && P[k] != P[q]) k = pi[k - 1];     // fall back to a shorter border
        if (P[k] == P[q]) k++;
        pi[q] = k;
    }
    return pi;
}

int main() {
    string T = "ABABDABACDABABCABABABABCABAB", P = "ABABCABAB";
    vector<int> pi = prefixFunction(P);
    cout << "pi:";
    for (int x : pi) cout << " " << x;
    cout << endl;
    for (size_t i = 0, q = 0; i < T.size(); i++) {
        while (q > 0 && P[q] != T[i]) q = pi[q - 1];
        if (P[q] == T[i]) q++;
        if (q == P.size()) { cout << "match at " << i - P.size() + 1 << endl; q = pi[q - 1]; }
    }
    return 0;
}

Output

pi: 0 0 1 2 0 1 2 3 4
match at 10
match at 19

Try it Yourself

Preprocessing O(m) + matching O(n) = O(n + m) in the worst case.

Algorithm	Preprocessing	Matching (worst)	Idea
Naive	none	O((n − m + 1)m)	try every shift
Rabin–Karp	O(m)	O((n − m + 1)m), expected O(n + m)	rolling hash
KMP	O(m)	O(n)	prefix function, never backtrack in T
Finite automaton	O(m·	Σ	)

Chapter 20 · Search, Graphs & Complexity

P, NP, NP-Complete & NP-Hard

Tractable and intractable problems: decision problems, the classes P and NP, polynomial-time reductions, NP-complete and NP-hard problems, Cook's theorem, and coping with hardness.

Some problems are solved in polynomial time — sorting, shortest paths, MST. Others, like TSP, 0/1 knapsack and graph colouring, have resisted every attempt for decades. Complexity theory explains this difference.

Decision problems

Complexity classes are defined for decision problems, whose answer is yes or no. Optimisation problems have decision versions: "Is there a tour of length ≤ k?" instead of "What is the shortest tour?". If you can solve one quickly, you can usually solve the other.

The class P

P = decision problems that can be solved in polynomial time, O(nᵏ) for some constant k. These are considered tractable.

Examples: sorting, searching, shortest paths, MST, matching, primality testing (AKS, 2002).

The class NP

NP (nondeterministic polynomial) = decision problems whose yes-answers can be verified in polynomial time, given a suitable certificate (a proposed solution).

Example — SUBSET-SUM: "Do some of these numbers add up to 15?" Finding a subset may be hard, but checking a proposed subset is easy: add it up.

Every problem in P is also in NP (if you can solve it, you can verify it), so P ⊆ NP.

Reductions

Problem A reduces to problem B (A ≤ₚ B) if any instance of A can be transformed in polynomial time into an instance of B with the same answer. Then B is at least as hard as A: a fast algorithm for B would give a fast algorithm for A.

NP-complete and NP-hard

NP-hard: every problem in NP reduces to it. It is at least as hard as anything in NP (it need not be in NP itself, and need not be a decision problem).
NP-complete (NPC): NP-hard and in NP — the hardest problems inside NP.

Cook–Levin theorem (1971): SAT (Boolean satisfiability) is NP-complete. It was the first. To show a new problem X is NP-complete:

Show X ∈ NP (a certificate can be checked in polynomial time).
Reduce a known NP-complete problem to X.

Classic chain of reductions from SAT. Each problem is NP-complete (the TSP and knapsack decision versions included).

Famous NP-complete problems

Problem	Question
SAT / 3-SAT	Can the Boolean formula be made true?
Clique	Does the graph contain k mutually adjacent vertices?
Vertex cover	Can k vertices touch every edge?
Independent set	Are there k pairwise non-adjacent vertices?
Hamiltonian cycle	Is there a cycle through every vertex exactly once?
TSP (decision)	Is there a tour of length ≤ k?
Graph k-colouring (k ≥ 3)	Can the graph be coloured with k colours?
Subset sum, 0/1 knapsack (decision)	Is there a subset with the required sum/value?

P vs NP

Nobody knows whether P = NP. If any single NP-complete problem had a polynomial algorithm, every NP problem would — so P would equal NP. Most researchers believe P ≠ NP. It is one of the seven Millennium Prize Problems (US $1 million prize).

The picture if P ≠ NP: P sits inside NP, and the NP-complete problems are where NP overlaps NP-hard, outside P.

Coping with NP-hard problems

Exact but exponential: backtracking, branch and bound, DP (fine for small n).
Approximation algorithms with guaranteed ratios: e.g. a 2-approximation for vertex cover; for metric TSP, the MST-based tour is at most 2 × optimal.
Heuristics: greedy, local search, simulated annealing, genetic algorithms — good answers quickly, no guarantee.
Special cases: 2-SAT and 2-colouring are in P; knapsack with small W uses the O(nW) DP.

Chapter 21 · Search, Graphs & Complexity

Algorithms Cheat Sheet

Design and Analysis of Algorithms on one page: notations, recurrences, the Master Theorem, every algorithm's complexity, technique selection and exam favourites.

Asymptotic notations

Notation	Definition (for n ≥ n₀)	Meaning
f = O(g)	f(n) ≤ c·g(n)	upper bound
f = Ω(g)	f(n) ≥ c·g(n)	lower bound
f = Θ(g)	c₁·g(n) ≤ f(n) ≤ c₂·g(n)	tight bound
f = o(g)	f/g → 0	strictly smaller
f = ω(g)	f/g → ∞	strictly larger

Growth: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ

Master Theorem: T(n) = aT(n/b) + f(n)

Compare f(n) with n^(log_b a)	Result
f smaller by a polynomial factor	Θ(n^(log_b a))
f equal (up to logᵏ)	Θ(n^(log_b a) · log n)
f larger by a polynomial factor (+ regularity)	Θ(f(n))

Common recurrences

Recurrence	Solution	Example
T(n) = T(n/2) + 1	Θ(log n)	binary search
T(n) = 2T(n/2) + n	Θ(n log n)	merge sort
T(n) = T(n − 1) + n	Θ(n²)	quick sort worst case
T(n) = 2T(n − 1) + 1	Θ(2ⁿ)	Tower of Hanoi
T(n) = 3T(n/2) + n	Θ(n^1.585)	Karatsuba
T(n) = 7T(n/2) + n²	Θ(n^2.81)	Strassen

Algorithm complexities

Algorithm	Technique	Time
Binary search	D&C	O(log n)
Merge sort	D&C	O(n log n)
Quick sort	D&C	O(n log n) avg, O(n²) worst
Heap sort	heap	O(n log n)
Activity selection	greedy	O(n log n)
Fractional knapsack	greedy	O(n log n)
Huffman coding	greedy	O(n log n)
Kruskal	greedy + union-find	O(E log E)
Prim	greedy + heap	O(E log V)
Dijkstra	greedy + heap	O((V + E) log V)
Bellman–Ford	DP	O(VE)
Floyd–Warshall	DP	O(V³)
0/1 knapsack	DP	O(nW)
LCS	DP	O(mn)
Matrix chain	DP	O(n³)
BFS / DFS / topological sort	traversal	O(V + E)
N-Queens, subset sum	backtracking	exponential
KMP	string matching	O(n + m)

Which technique?

Clue in the problem	Try
split in halves, combine answers	divide and conquer
locally best choice is provably safe	greedy
overlapping subproblems, "count the ways", "minimum/maximum of"	dynamic programming
find all arrangements, satisfy constraints	backtracking
optimise over an exponential search space	branch and bound
problem is NP-hard and n is large	approximation or heuristics

Exam favourites

Define algorithm; properties; loop invariant for insertion sort.
Prove 3n² + 2n = Θ(n²) by finding c₁, c₂, n₀.
Solve recurrences with the Master Theorem and recursion trees.
Trace merge sort and quick sort partition; best/worst cases.
Activity selection, fractional knapsack, job sequencing tables.
Huffman tree and codes; average code length.
Kruskal and Prim on a given graph; Dijkstra table.
0/1 knapsack, LCS and matrix-chain tables with traceback.
Floyd–Warshall matrices D⁰ … Dⁿ.
N-Queens state-space tree; subset sum.
KMP prefix function for a pattern.
P, NP, NP-complete, NP-hard with examples; Cook's theorem.

Design and Analysis of Algorithms

What Is an Algorithm?

#The five properties (Knuth)

#The design and analysis process

#Pseudocode

#Proving correctness: loop invariants

#The RAM model

#Why analyse at all?

Asymptotic Notations

#Big-O: upper bound

#Big-Omega: lower bound

#Big-Theta: tight bound

#Little-o and little-omega

#Order of growth

#Properties

#Checking bounds numerically

Analysing Loops & Recursive Code

#Independent loops

#Dependent loops: sum the iterations

#Logarithmic loops

#Measure it yourself

#Common patterns

#Recursive code: write a recurrence

#Best, worst and average case

#Amortised analysis

Solving Recurrences & the Master Theorem

#1. The substitution method

#2. The recursion-tree method

#3. The Master Theorem

#Worked examples

#Extended case 2

#When the Master Theorem does not apply

#Unrolling (iteration method)

#Check a solution by computing it

Divide and Conquer

#Binary search

#Merge sort

#Quick sort

#Randomised quick sort

#Merge sort vs quick sort

More Divide and Conquer

#Finding the maximum and minimum

#Counting inversions

#Karatsuba multiplication

#Strassen's matrix multiplication

The Greedy Method

#When greedy fails

#Activity selection

#Fractional knapsack

#Job sequencing with deadlines

#Greedy algorithms you will meet

Huffman Coding

#Prefix-free codes

#The algorithm

#Example

#Analysis

#Decoding

Minimum Spanning Trees

#Kruskal's algorithm

#Prim's algorithm

#Kruskal vs Prim

Shortest Paths: Dijkstra & Bellman–Ford

#Relaxation

#Dijkstra's algorithm

#Bellman–Ford

#Comparison

Dynamic Programming

#The problem with plain recursion

#Approach 1: memoisation (top-down)

#Approach 2: tabulation (bottom-up)

#The DP recipe

#Example: coin change

0/1 Knapsack

#State and recurrence

#Watch the table fill

#Code with traceback

#Space optimisation

Longest Common Subsequence

#Recurrence

#Watch it fill

The five properties (Knuth)

The design and analysis process

Pseudocode

Proving correctness: loop invariants

The RAM model

Why analyse at all?

Big-O: upper bound

Big-Omega: lower bound

Big-Theta: tight bound

Little-o and little-omega

Order of growth

Properties

Checking bounds numerically

Independent loops

Dependent loops: sum the iterations

Logarithmic loops

Measure it yourself

Common patterns

Recursive code: write a recurrence

Best, worst and average case

Amortised analysis

1. The substitution method

2. The recursion-tree method

3. The Master Theorem

Worked examples

Extended case 2

When the Master Theorem does not apply

Unrolling (iteration method)

Check a solution by computing it

Binary search

Merge sort

Quick sort

Randomised quick sort

Merge sort vs quick sort

Finding the maximum and minimum

Counting inversions

Karatsuba multiplication

Strassen's matrix multiplication

When greedy fails

Activity selection

Fractional knapsack

Job sequencing with deadlines

Greedy algorithms you will meet

Prefix-free codes

The algorithm

Example

Analysis

Decoding

Kruskal's algorithm

Prim's algorithm

Kruskal vs Prim

Relaxation

Dijkstra's algorithm

Bellman–Ford

Comparison

The problem with plain recursion

Approach 1: memoisation (top-down)

Approach 2: tabulation (bottom-up)

The DP recipe

Example: coin change

State and recurrence

Watch the table fill

Code with traceback

Space optimisation

Recurrence

Watch it fill

Related: edit distance

Recurrence

The idea

Warshall's algorithm: transitive closure

N-Queens

Subset sum

Graph colouring

Hamiltonian cycle

Search strategies

0/1 knapsack with B&B

Travelling salesperson problem (TSP)

Topological sort

Kahn's algorithm (BFS)

DFS-based topological sort