Design and Analysis of Algorithms

Divide and conquer

Divide and conquer solves a problem in three steps:

1. Divide the problem into smaller sub-problems of the same type.
2. Conquer the sub-problems by solving them recursively (solve directly when small enough, the base case).
3. Combine the solutions of the sub-problems into the solution of the original problem.

Its running time satisfies a recurrence $T(n) = a\,T(n/b) + f(n)$, solved by the master theorem. Examples: merge sort, quick sort, binary search, Strassen's matrix multiplication.

Example: merge sort. Divide the array into two halves, sort each recursively, and merge the two sorted halves in linear time. Thus $T(n) = 2T(n/2) + \Theta(n) \Rightarrow T(n) = \Theta(n \log n).$

Randomized quick sort

Ordinary quick sort picks a fixed pivot (e.g. the last element) and is $O(n^2)$ for already sorted input. Randomized quick sort chooses the pivot at random, so no particular input is bad.

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q - 1)
        RANDOMIZED-QUICKSORT(A, q + 1, r)

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)            // random index in [p, r]
    exchange A[r] with A[i]
    return PARTITION(A, p, r)

PARTITION(A, p, r)
    x = A[r]                    // pivot
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

Time complexity

PARTITION takes $\Theta(n)$ time for $n$ elements.

• Worst case (pivot is always the smallest or largest): $T(n) = T(n-1) + \Theta(n)$, so $T(n) = \Theta(n^2)$. With random pivots this occurs with a very small probability.
• Best case (pivot splits into two equal halves): $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$.
• Expected case: every pivot rank is equally likely, so $E[T(n)] = \frac{1}{n}\sum_{q=0}^{n-1}\big(E[T(q)] + E[T(n-1-q)]\big) + \Theta(n) = \frac{2}{n}\sum_{q=0}^{n-1}E[T(q)] + \Theta(n),$ which solves to $E[T(n)] = O(n \log n)$. Even a 9:1 split every time gives $T(n) = T(9n/10) + T(n/10) + cn = O(n\log n)$.

So the expected running time is $O(n \log n)$ for every input, the worst case is $O(n^2)$, and the space used is $O(\log n)$ expected for the recursion stack.

Divide and conquer

This paradigm solves a problem in three steps.

1. Divide: split the problem into smaller subproblems of the same kind.
2. Conquer: solve the subproblems recursively. A small enough subproblem is solved directly (the base case).
3. Combine: merge the subproblem solutions into the solution of the original problem.

The running time is given by a recurrence $T(n)=aT(n/b)+D(n)+C(n)$, where $D(n)$ and $C(n)$ are the divide and combine costs.

Example: merge sort. Divide the array into two halves. Sort each half recursively. Merge the two sorted halves in $O(n)$ time. The recurrence is $T(n)=2T(n/2)+\Theta(n)$, which gives $T(n)=\Theta(n\log n)$. Other examples are binary search, quick sort and Strassen's matrix multiplication.

Randomized quick sort

Plain quick sort has $O(n^2)$ worst-case behaviour on already sorted input if the first or last element is the pivot. Randomized quick sort picks the pivot at random, so that no particular input is always bad.

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2      q = RANDOMIZED-PARTITION(A, p, r)
3      RANDOMIZED-QUICKSORT(A, p, q-1)
4      RANDOMIZED-QUICKSORT(A, q+1, r)

RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  swap A[r], A[i]
3  return PARTITION(A, p, r)

PARTITION(A, p, r)
1  x = A[r]; i = p - 1
2  for j = p to r-1
3      if A[j] <= x
4          i = i + 1; swap A[i], A[j]
5  swap A[i+1], A[r]
6  return i + 1

Time complexity

• Partition takes $\Theta(n)$ time.
• Worst case: the pivot is always the smallest or largest element, so $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. With random pivots this has probability very small.
• Best case: balanced splits, $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$.
• Expected case: for any input, the expected running time is $O(n\log n)$. The expected number of comparisons is at most $2n\ln n\approx1.39\,n\log_2 n$. The reason is that two elements $z_i<z_j$ are compared only if one of them is the first pivot chosen among $z_i,\dots,z_j$, which has probability $2/(j-i+1)$. Summing over all pairs gives $E[X]=\sum_{i<j}\frac{2}{j-i+1}=O(n\log n)$

Even a split such as 9:1 each time gives $O(n\log n)$, which is why the average case is so good.

Space: $O(\log n)$ expected for the recursion stack.

Recursion tree method

The recurrence is drawn as a tree. The root is the cost of the top-level call (the non-recursive work $f(n)$). Each node has one child for every recursive call, labelled with the cost of that smaller call. Every level is summed, and the level sums are added to get the total. The result is used as a guess and can be confirmed by substitution.

Solving $T(n)=2T(n/2)+1$, with $T(1)=1$

• Level 0 has 1 node of cost 1, so the sum is 1.
• Level 1 has 2 nodes of cost 1 each, so the sum is 2.
• Level 2 has 4 nodes of cost 1 each, so the sum is 4.
• Level $i$ has $2^i$ nodes of cost 1 each, so the sum is $2^i$.

The subproblem size at level $i$ is $n/2^i$. It reaches 1 at $i=\log_2 n$. The last level has $2^{\log_2 n}=n$ leaves, each costing $T(1)=1$.

$T(n)=\sum_{i=0}^{\log_2 n-1}2^i+n=(n-1)+n=2n-1$

So $T(n)=\Theta(n)$.

Check by substitution. Assume $T(n)=2n-1$. Then $2T(n/2)+1=2(n-1)+1=2n-1$, which equals $T(n)$, and $T(1)=1$ holds.

We solve $x\equiv1 \pmod 2$, $x\equiv3\pmod 5$, $x\equiv6\pmod 7$.

The moduli 2, 5, 7 are pairwise coprime, so CRT applies with

$M=2\cdot5\cdot7=70,\quad M_1=\frac{70}{2}=35,\quad M_2=\frac{70}{5}=14,\quad M_3=\frac{70}{7}=10.$

Find the inverses $y_i$ with $M_iy_i\equiv1\pmod{m_i}$:

• $35y_1\equiv1\pmod 2$: $35\equiv1$, so $y_1=1$.
• $14y_2\equiv1\pmod 5$: $14\equiv4$, and $4\cdot4=16\equiv1$, so $y_2=4$.
• $10y_3\equiv1\pmod 7$: $10\equiv3$, and $3\cdot5=15\equiv1$, so $y_3=5$.

Now

$x=\sum a_iM_iy_i=1\cdot35\cdot1+3\cdot14\cdot4+6\cdot10\cdot5=35+168+300=503.$

$x\equiv503 \pmod{70}\Rightarrow 503-7\cdot70=503-490=13.$

$x\equiv13\pmod{70}$.

Check: $13 \bmod 2=1$, $13\bmod5=3$, $13\bmod7=6$. All three hold.

Chinese Remainder Theorem

We solve $x \equiv 1 \pmod 3$, $x \equiv 2 \pmod 5$, $x \equiv 0 \pmod 7$. The moduli 3, 5, 7 are pairwise coprime, so a unique solution exists modulo

$M = 3 \times 5 \times 7 = 105.$

Compute $M_i = M/m_i$ and the inverse $y_i$ of $M_i$ modulo $m_i$:

• $m_1=3$: $M_1 = 35$, $35 \equiv 2 \pmod 3$, and $2y_1 \equiv 1 \pmod 3$ gives $y_1 = 2$.
• $m_2=5$: $M_2 = 21$, $21 \equiv 1 \pmod 5$, so $y_2 = 1$.
• $m_3=7$: $M_3 = 15$, $15 \equiv 1 \pmod 7$, so $y_3 = 1$.

$x = \sum a_i M_i y_i = 1\cdot 35\cdot 2 + 2\cdot 21\cdot 1 + 0\cdot 15\cdot 1 = 70 + 42 = 112.$

$x \equiv 112 \pmod{105} \equiv 7.$

Check: $7 = 2\cdot3+1$ so $7 \equiv 1 \pmod 3$; $7 = 1\cdot5+2$ so $7\equiv 2 \pmod 5$; $7 \equiv 0 \pmod 7$. All hold.

Solution: $x \equiv 7 \pmod{105}$, i.e. $x = 7, 112, 217, \dots$

Recursion tree for $T(n) = 2T(n/2) + n$

Level 0 has one node of cost $n$. Each node of size $m$ costs $m$ and has two children of size $m/2$.

The recursion stops when $n/2^i = 1$, i.e. at depth $i=\log_2 n$, so the tree has $\log_2 n + 1$ levels. Every level contributes $n$, so

$T(n) = \sum_{i=0}^{\log_2 n} n = n(\log_2 n + 1) = n\log_2 n + n.$

Therefore

$T(n) = \Theta(n\log n).$

This agrees with case 2 of the master theorem (merge sort recurrence).

Complexity of an algorithm

The complexity of an algorithm measures the resources it needs as a function of the input size $n$.

• Time complexity: the number of basic operations (steps) executed, $T(n)$.
• Space complexity: the amount of memory used, $S(n)$ (input plus auxiliary space).

It is analysed for the best case, average case and worst case. Since exact running time depends on the machine and language, we describe the growth rate for large $n$ using asymptotic notations.

Asymptotic notations

1. Big-O (upper bound). $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $0 \le f(n) \le c\,g(n) \quad \text{for all } n \ge n_0.$ Geometrically, beyond $n_0$ the curve $f(n)$ lies on or below the curve $c\,g(n)$. It gives a worst-case bound. Example: $3n + 2 = O(n)$, since $3n + 2 \le 4n$ for $n \ge 2$ (so $c = 4$, $n_0 = 2$).

2. Big-Omega (lower bound). $f(n) = \Omega(g(n))$ if there exist $c > 0$ and $n_0$ such that $0 \le c\,g(n) \le f(n) \quad \text{for all } n \ge n_0.$ Beyond $n_0$, $f(n)$ lies on or above $c\,g(n)$. It gives a best-case bound. Example: $3n + 2 = \Omega(n)$ with $c = 3$, $n_0 = 1$.

3. Big-Theta (tight bound). $f(n) = \Theta(g(n))$ if there exist $c_1, c_2 > 0$ and $n_0$ such that $c_1\,g(n) \le f(n) \le c_2\,g(n) \quad \text{for all } n \ge n_0.$ Beyond $n_0$, $f(n)$ is sandwiched between $c_1 g(n)$ and $c_2 g(n)$. Equivalent to $f = O(g)$ and $f = \Omega(g)$. Example: $3n + 2 = \Theta(n)$ with $c_1 = 3$, $c_2 = 4$, $n_0 = 2$. Another: $\tfrac{n^2}{2} - 3n = \Theta(n^2)$ with $c_1 = \tfrac1{14}$, $c_2 = \tfrac12$, $n_0 = 7$.

4. Little-o (strict upper bound). $f(n) = o(g(n))$ if for every $c > 0$ there is $n_0$ with $f(n) < c\,g(n)$ for all $n \ge n_0$; equivalently $\lim_{n\to\infty} f(n)/g(n) = 0$. Example: $n = o(n^2)$ but $n^2 \ne o(n^2)$.

5. Little-omega (strict lower bound). $f(n) = \omega(g(n))$ if for every $c > 0$ there is $n_0$ with $f(n) > c\,g(n)$ for all $n \ge n_0$; equivalently $\lim f(n)/g(n) = \infty$. Example: $n^2 = \omega(n)$.

Order of common growth rates: $1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!$

For example linear search is $O(n)$, binary search is $O(\log n)$, merge sort is $\Theta(n \log n)$ and bubble sort is $O(n^2)$.

Backtracking

Backtracking is a systematic, depth-first way of searching the solution space of a problem for solutions that satisfy given constraints. The solution is built one component at a time as a vector $(x_1, x_2, \dots, x_n)$. After each choice, a bounding (feasibility) test checks whether the partial solution can still lead to a complete valid solution. If it cannot, the algorithm abandons that branch (prunes it) and backtracks to the previous choice to try another value. The search space is viewed as a state-space tree whose nodes are partial solutions. It is used for N-Queens, graph colouring, Hamiltonian cycles, subset sum and Sudoku.

Difference from plain recursion

N-Queens problem

Place $N$ queens on an $N \times N$ chessboard so that no two queens attack each other: no two share a row, a column or a diagonal.

Let $x[i]$ be the column of the queen placed in row $i$. This automatically gives one queen per row. Queens at $(i, x[i])$ and $(k, x[k])$ attack each other if they are in the same column ($x[i] = x[k]$) or on the same diagonal ($|x[i] - x[k]| = |i - k|$).

PLACE(k, i)            // can a queen go in row k, column i?
    for j = 1 to k - 1
        if x[j] == i or abs(x[j] - i) == abs(j - k)
            return false
    return true

NQUEENS(k, n)
    for i = 1 to n
        if PLACE(k, i)
            x[k] = i
            if k == n
                print x[1..n]
            else
                NQUEENS(k + 1, n)

Called as NQUEENS(1, n). For $n = 4$ the solutions are $(2, 4, 1, 3)$ and $(3, 1, 4, 2)$. Working: put a queen in row 1, column 1; row 2 can only go to column 3 (columns 1 and 2 are attacked), then row 3 has no safe column, so backtrack, move queen 2 to column 4, and so on, until row 1 column 2 leads to $(2, 4, 1, 3)$.

Time complexity

• PLACE takes $O(k) = O(n)$ time.
• Without pruning, there would be $n^n$ placements ($n^n$ leaves in the state tree), or $n!$ if we also require distinct columns.
• With backtracking, the number of nodes explored is much smaller, but in the worst case it still grows factorially. At level $k$ there are at most $n - k + 1$ candidate columns for each node, so the number of nodes is bounded by $\sum_{k=0}^{n} n!/(n-k)! = O(n!)$, and each node costs $O(n)$ for PLACE.

Hence the time complexity is $O(n \cdot n!)$ in the worst case (commonly stated as $O(n!)$), exponential in $n$. The space complexity is $O(n)$ for the vector $x$ and the recursion stack.

Selection sort repeatedly selects the smallest element of the unsorted part and swaps it into the next position of the sorted part.

Algorithm

SELECTION-SORT(A, n)
1  for i = 0 to n-2
2      min = i
3      for j = i+1 to n-1
4          if A[j] < A[min]
5              min = j
6      if min != i
7          swap A[i], A[min]

Example: A = [64, 25, 12, 22, 11]. Pass 1 puts 11 first: [11, 25, 12, 22, 64]. Pass 2 puts 12 second: [11, 12, 25, 22, 64]. Pass 3 gives [11, 12, 22, 25, 64]. Pass 4 leaves the array unchanged, so the array is sorted.

Time complexity

The inner loop runs $(n-1-i)$ times for each $i$, whatever the data looks like. The number of comparisons is

$(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}$

• Best, average and worst case: $\Theta(n^2)$ comparisons. The algorithm cannot stop early, even on sorted input.
• Swaps: at most $n-1$, which is $O(n)$. This is useful when writing to memory is costly.

Space complexity

Only the variables $i, j, min$ and one temporary for the swap are used. Space is $O(1)$, so the sort is in place. The usual swap-based version is not stable.

The master theorem solves $T(n)=aT(n/b)+f(n)$ by comparing $f(n)$ with $n^{\log_b a}$.

• Case 1: if $f(n)=O(n^{\log_b a-\epsilon})$ for some $\epsilon>0$, then $T(n)=\Theta(n^{\log_b a})$.
• Case 2: if $f(n)=\Theta(n^{\log_b a})$, then $T(n)=\Theta(n^{\log_b a}\log n)$.
• Case 3: if $f(n)=\Omega(n^{\log_b a+\epsilon})$ and $af(n/b)\le cf(n)$ for some $c<1$, then $T(n)=\Theta(f(n))$.

(1) $T(n)=7T(n/2)+n^2$

Here $a=7,\ b=2,\ f(n)=n^2$, so $n^{\log_2 7}=n^{2.807}$.

Since $n^2=O(n^{2.807-\epsilon})$ with $\epsilon\approx0.8$, Case 1 applies.

$T(n)=\Theta(n^{\log_2 7})\approx\Theta(n^{2.81})$

(2) $T(n)=4T(n/4)+kn$

Here $a=4,\ b=4,\ f(n)=kn$, so $n^{\log_4 4}=n$.

Since $f(n)=kn=\Theta(n)$, Case 2 applies.

$T(n)=\Theta(n\log n)$

Problem. There are $n$ items, where item $i$ has weight $w_i$ and profit $p_i$. The knapsack has capacity $W$. Any fraction $x_i\in[0,1]$ of an item may be taken. We maximise $\sum p_ix_i$ subject to $\sum w_ix_i\le W$.

Greedy strategy. Take items in decreasing order of profit per unit weight $p_i/w_i$. Take each item wholly while it fits. Take a fraction of the first item that does not fit, and then stop.

Algorithm

FRACTIONAL-KNAPSACK(p, w, n, W)
1  for i = 1 to n: ratio[i] = p[i] / w[i]
2  sort items in decreasing order of ratio
3  remaining = W; profit = 0
4  for i = 1 to n (in sorted order)
5      if w[i] <= remaining
6          x[i] = 1; remaining -= w[i]; profit += p[i]
7      else
8          x[i] = remaining / w[i]
9          profit += x[i] * p[i]
10         break
11 return profit

Example. $W=50$, with $(p,w)=(60,10),(100,20),(120,30)$. The ratios are 6, 5 and 4. Take item 1 in full (10 kg, profit 60). Take item 2 in full (20 kg, profit 100). Capacity left is 20, so take $20/30$ of item 3, giving profit 80. Total profit $=240$.

Correctness. Suppose an optimal solution did not use the highest-ratio item as fully as it could. Replacing some weight of a lower-ratio item with that item would not reduce the profit. So the greedy choice is safe, and the problem also has optimal substructure.

Time complexity. Computing the ratios takes $O(n)$. Sorting takes $O(n\log n)$. The selection loop takes $O(n)$. The total is $O(n\log n)$. Using a max-heap instead of a full sort gives the same bound.

Heap sort first builds a max-heap, then repeatedly swaps the root (the maximum) with the last element of the heap, shrinks the heap by one, and restores the heap property with heapify.

Data (1-indexed): $[2,\,9,\,3,\,12,\,15,\,8,\,11]$. The children of index $i$ are $2i$ and $2i+1$.

Step 1: Build the max-heap (heapify from index 3 down to 1)

• Index 3: 3 has children 8 and 11. Swap with 11: $[2,9,11,12,15,8,3]$.
• Index 2: 9 has children 12 and 15. Swap with 15: $[2,15,11,12,9,8,3]$.
• Index 1: 2 has children 15 and 11. Swap with 15: $[15,2,11,12,9,8,3]$. Then 2 has children 12 and 9, so swap with 12: $[15,12,11,2,9,8,3]$.

The max-heap is $[15,12,11,2,9,8,3]$.

Step 2: Extract the maximum repeatedly (the sorted part follows the bar)

Result: $[2,\,3,\,8,\,9,\,11,\,12,\,15]$.

Building the heap takes $O(n)$. Each of the $n-1$ extractions takes $O(\log n)$. The total is $O(n\log n)$, with $O(1)$ extra space.

Dynamic programming (DP) is a technique for solving problems by breaking them into overlapping subproblems. Each subproblem is solved only once, and its answer is stored in a table (bottom-up tabulation) or a cache (top-down memoisation). It is mainly used for optimisation problems, for example matrix chain multiplication, 0/1 knapsack, LCS and shortest paths.

Elements of dynamic programming

1. Optimal substructure. An optimal solution to the problem contains optimal solutions to its subproblems. For example, in matrix chain multiplication, the best split of $A_i\dots A_j$ uses the best parenthesisations of the two halves.
2. Overlapping subproblems. The same subproblems occur again and again in the recursion. Storing each answer avoids recomputation. For example, a naive Fibonacci recursion computes $F(n-2)$ many times. This is the feature that separates DP from divide and conquer.
3. Recurrence (recursive formulation). The value of a problem is defined in terms of smaller ones, for example $c[i][j]=\min_k\{c[i][k]+c[k+1][j]+p_{i-1}p_kp_j\}$.
4. Table and order of computation. A table stores the subproblem values. Subproblems are filled from the smallest to the largest, so that every value needed is already available.
5. Construction of the solution. A second table records the choices made (for example the split point $k$). The actual solution is rebuilt from it by tracing back.

Steps: characterise the structure of an optimal solution, define its value recursively, compute the values bottom-up, and construct the optimal solution from the stored information.

Vertex cover problem. A vertex cover of an undirected graph $G=(V,E)$ is a set $C\subseteq V$ such that every edge has at least one endpoint in $C$. The optimisation version asks for a cover of minimum size. This is NP-hard, so no polynomial-time exact algorithm is known.

Approximation algorithm (2-approximation)

APPROX-VERTEX-COVER(G)
1  C = empty set
2  E' = E
3  while E' is not empty
4      pick any edge (u, v) in E'
5      add both u and v to C
6      remove from E' every edge incident on u or v
7  return C

It runs in $O(V+E)$ time.

Example. Take the edges $E=\{(a,b),(b,c),(c,d),(d,e),(e,f),(d,f)\}$.

• Pick $(b,c)$. Add $b,c$ and remove $(a,b),(b,c),(c,d)$.
• Pick $(d,e)$. Add $d,e$ and remove $(d,e),(e,f),(d,f)$.
• No edges remain, so $C=\{b,c,d,e\}$ with size 4.

The optimal cover is $\{b,d,e\}$ or $\{b,d,f\}$, of size 3, so the answer is within a factor of 2 of the optimum.

Why the ratio is 2. The edges picked in line 4 form a matching, because no two of them share a vertex. Any cover, including an optimal one $C^*$, must contain at least one endpoint of each matched edge, so $|C^*|\ge|M|$, where $M$ is the set of picked edges. The algorithm returns $|C|=2|M|\le2|C^*|$. It is therefore a 2-approximation.

Minimum spanning tree (MST). For a connected, weighted, undirected graph, an MST is a spanning tree with the least total edge weight.

Prim's algorithm (greedy). Start from any vertex. At each step, add the cheapest edge that connects a vertex in the tree to a vertex outside it. Repeat until all $V$ vertices are in the tree. The cut property guarantees that every such edge belongs to some MST.

PRIM(G, w, r)
1  for each vertex u: key[u] = infinity; parent[u] = NIL
2  key[r] = 0
3  Q = all vertices (min-priority queue on key)
4  while Q is not empty
5      u = EXTRACT-MIN(Q)
6      for each v adjacent to u
7          if v in Q and w(u, v) < key[v]
8              parent[v] = u
9              key[v] = w(u, v)       // DECREASE-KEY

Example. Take the edges $A\text{-}B=2,\ A\text{-}C=3,\ B\text{-}C=1,\ B\text{-}D=4,\ C\text{-}D=5$. Starting from $A$, pick $A\text{-}B(2)$, then $B\text{-}C(1)$, then $B\text{-}D(4)$. The MST weight is 7.

Time complexity

• Adjacency matrix with a linear scan to find the minimum: $O(V^2)$.
• Adjacency list with a binary min-heap: building the heap costs $O(V)$. There are $V$ EXTRACT-MINs costing $O(\log V)$ each, and up to $E$ DECREASE-KEYs costing $O(\log V)$ each. The total is $O(E\log V)$.
• Fibonacci heap: $O(E+V\log V)$.

Prim's algorithm is best for dense graphs. Kruskal's algorithm, which runs in $O(E\log E)$, is often preferred for sparse graphs.

These classes are defined for decision problems (answer yes or no). The size of the input is $n$.

Class P. The problems solvable by a deterministic algorithm in polynomial time, $O(n^k)$. Examples: sorting, shortest path, MST, searching, and testing whether a number is the GCD of two others.

Class NP. The problems whose proposed solution (certificate) can be verified in polynomial time. Equivalently, they are solvable in polynomial time by a non-deterministic machine. Examples: Hamiltonian cycle (a given cycle is checked in $O(n)$), subset sum, graph colouring, SAT. Every problem in P is also in NP, so $P\subseteq NP$. Whether $P=NP$ is still open.

Class NP-complete (NPC). A problem $L$ is NP-complete if:

1. $L\in NP$, and
2. every problem $L'\in NP$ reduces to $L$ in polynomial time ($L'\le_pL$).

If any NP-complete problem is solved in polynomial time, then $P=NP$. The first NP-complete problem proved was SAT (Cook's theorem). Other examples: 3-SAT, clique, vertex cover, Hamiltonian cycle, travelling salesman (decision version), subset sum.

NP-hard problems satisfy condition 2 only. They need not be in NP, for example the halting problem. So NPC $=$ NP $\cap$ NP-hard.

Relationship (assuming $P\ne NP$): P and NPC are disjoint subsets of NP, and NP-hard contains NPC.

(1) Backtracking strategy

Backtracking builds a solution one component at a time, as a depth-first search of the state-space tree. After each step it checks whether the partial solution can still lead to a valid complete one. If it cannot (a bounding or constraint test fails), the search abandons that branch, goes back to the previous choice, and tries the next alternative. This pruning makes it much faster than exhaustive search in practice, although the worst case is still exponential.

General scheme:

BACKTRACK(partial):
    if partial is a complete solution: output it
    for each candidate c that extends partial:
        if c is feasible (promising):
            add c; BACKTRACK(partial); remove c    // undo

Typical applications: N-queens, graph colouring, Hamiltonian cycle, subset sum, and maze solving.

(2) Tractable and intractable problems

• Tractable problems can be solved by algorithms that run in polynomial time, $O(n^k)$. They are practical to solve even for large inputs. Examples: sorting ($O(n\log n)$), shortest paths and MST.
• Intractable problems have no known polynomial-time algorithm. The best known algorithms take super-polynomial (exponential or factorial) time, for example $O(2^n)$ or $O(n!)$. They become infeasible even for moderate $n$. Examples: the travelling salesman problem, Hamiltonian cycle, 0/1 knapsack (in terms of the input length), and graph colouring. Some intractable problems are shown to be NP-complete or NP-hard. In practice they are handled by approximation algorithms, heuristics or backtracking.

Elementary properties of an algorithm

An algorithm is a finite sequence of well-defined steps that solves a problem. It should have the following properties.

1. Input: zero or more quantities are supplied from outside.
2. Output: at least one result is produced.
3. Definiteness: each step is precise and unambiguous.
4. Finiteness: the algorithm terminates after a finite number of steps for every valid input.
5. Effectiveness: every step is basic enough to be carried out exactly, in finite time.
6. Correctness and generality: it gives the right output for all valid inputs, not only for particular ones.

Why we need algorithms

• They give a precise, language-independent method for solving a problem, which can be checked for correctness before coding.
• They let us compare solutions by running time and memory use, independently of the machine. For example, searching $10^6$ sorted items takes about 20 steps with binary search, but up to $10^6$ with linear search.
• Efficient algorithms save time and resources, and they make problems feasible that would otherwise be impractical, for example sorting, routing, searching and cryptography.
• They are the basis for programming and for reuse across applications.

RAM model of analysis

The Random Access Machine (RAM) is an abstract machine used to count the cost of an algorithm.

• Instructions run one after another, with no concurrency.
• Each basic operation (arithmetic, comparison, assignment, array access, branch, function call) takes one unit (constant) time.
• Memory is unlimited, and every memory location is accessed in constant time. There is no memory hierarchy or caching.
• Each word has a fixed size, for example enough bits to hold a number.

The running time is the number of primitive steps executed, expressed as a function $T(n)$ of the input size $n$.

Example: sum of an array

$T(n)=c_1+c_2(n+1)+c_3n+c_4=(c_2+c_3)n+(c_1+c_2+c_4)=an+b$

So $T(n)=\Theta(n)$ and the running time is linear. Only the growth rate matters, so the constants are dropped.

Dynamic programming approach

Dynamic programming (DP) solves a problem by combining solutions of overlapping subproblems. It needs two properties: optimal substructure and overlapping subproblems. Each subproblem is solved once and stored in a table, then looked up whenever it is needed again. Typical steps are to define the subproblems, write a recurrence, fill the table bottom-up, and trace back to build the solution.

Difference from plain recursion

0/1 knapsack by dynamic programming

There are $n$ items with weights $w_i$ and profits $p_i$, and capacity $W$. Each item is taken whole or not at all. Let $B[i][w]$ be the maximum profit using the first $i$ items with capacity $w$.

$B[i][w]=\begin{cases}0 & i=0 \text{ or } w=0\\ B[i-1][w] & w_i>w\\ \max\{B[i-1][w],\ p_i+B[i-1][w-w_i]\} & w_i\le w\end{cases}$

KNAPSACK(p, w, n, W)
1  for i = 0 to n: B[i][0] = 0
2  for j = 0 to W: B[0][j] = 0
3  for i = 1 to n
4      for j = 1 to W
5          if w[i] <= j
6              B[i][j] = max(B[i-1][j], p[i] + B[i-1][j-w[i]])
7          else
8              B[i][j] = B[i-1][j]
9  return B[n][W]

The items in the solution are found by tracing back from $B[n][W]$. If $B[i][j]\ne B[i-1][j]$, item $i$ is taken and $j$ decreases by $w_i$.

Example. $W=5$ with $(w,p)=(2,3),(3,4),(4,5),(5,6)$. The best choice is items 1 and 2, with weight 5 and profit 7, so $B[4][5]=7$.

Complexity

The table has $(n+1)(W+1)$ entries, and each is computed in $O(1)$ time. So the time is $O(nW)$ and the space is $O(nW)$, which can be reduced to $O(W)$ by keeping one row. This is pseudo-polynomial, because $W$ is a number and not the input length.

Algorithm

FIND-MAX(A, n)
1  max = A[1]
2  for i = 2 to n
3      if A[i] > max
4          max = A[i]
5  return max

The algorithm assumes the maximum is the first element. It then scans the rest of the array, replacing max whenever a larger element is seen.

Example. A = [7, 3, 9, 4]. Starting with max = 7, element 3 is smaller, 9 is larger so max = 9, and 4 is smaller. The result is 9.

Time complexity

The loop makes exactly $n-1$ comparisons in every case. The assignment in line 4 runs at most $n-1$ times, so

$T(n)=an+b$

The best, average and worst cases are all $\Theta(n)$. The algorithm uses $O(1)$ extra space. Every element must be examined at least once, so $\Omega(n)$ is also a lower bound and the algorithm is optimal.

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order. After pass $i$, the $i$ largest elements have bubbled to their final places at the end.

Algorithm

BUBBLE-SORT(A, n)
1  for i = 1 to n-1
2      swapped = false
3      for j = 1 to n-i
4          if A[j] > A[j+1]
5              swap A[j], A[j+1]
6              swapped = true
7      if swapped == false
8          break

Example. A = [5, 1, 4, 2]. Pass 1 gives [1, 4, 2, 5]. Pass 2 gives [1, 2, 4, 5]. Pass 3 makes no swap, so the algorithm stops.

Time complexity

• Pass $i$ makes $n-i$ comparisons, so the total is $(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}=\Theta(n^2)$
• Worst case (reverse sorted): $\Theta(n^2)$ comparisons and $\Theta(n^2)$ swaps.
• Average case: $\Theta(n^2)$.
• Best case (already sorted): with the swapped flag, a single pass of $n-1$ comparisons is enough, so $\Theta(n)$. Without the flag it is still $\Theta(n^2)$.

Space: $O(1)$, in place. The sort is stable, because equal elements are never swapped.

Optimization problem

An optimization problem asks for the best solution among all feasible solutions, according to an objective function that is to be maximised or minimised. A solution that satisfies the constraints is called feasible, and the best feasible one is optimal. Examples: shortest path (minimise distance), minimum spanning tree (minimise total weight), knapsack (maximise profit), and Huffman coding (minimise the code length).

Greedy strategy

A greedy algorithm builds the solution step by step. At every step it makes the choice that looks best at that moment (the locally optimal choice), and never reconsiders it. It hopes that these local choices lead to a global optimum.

Typical structure:

1. A candidate set from which a solution is built.
2. A selection function that picks the best candidate.
3. A feasibility function that checks whether the candidate can be added.
4. An objective function and a solution test.

A greedy algorithm gives the correct optimum only when the problem has:

• Greedy-choice property: a globally optimal solution can be reached by making a locally optimal choice.
• Optimal substructure: after a greedy choice, the remaining problem is a smaller problem of the same kind.

Examples where greedy is optimal: fractional knapsack, activity selection, Huffman coding, Prim's and Kruskal's MST, Dijkstra's shortest path, and job sequencing with deadlines. For problems such as 0/1 knapsack greedy can fail, and dynamic programming is used.

Greedy algorithms are usually simple and fast (often $O(n\log n)$ because of an initial sort).

Problem. There are $n$ jobs. Job $i$ has a deadline $d_i$ and a profit $p_i$, earned only if the job is finished by its deadline. Each job takes one unit of time, and only one job runs at a time. We choose a feasible set of jobs, and an order for them, to maximise total profit.

Greedy strategy. Sort the jobs in decreasing order of profit. For each job in turn, place it in the latest free time slot that is on or before its deadline. If no such slot is free, the job is rejected.

JOB-SEQUENCING(jobs, n)
1  sort jobs in decreasing order of profit
2  d_max = maximum deadline; slot[1..d_max] = empty
3  for i = 1 to n
4      for t = min(d_max, d[i]) down to 1
5          if slot[t] is empty
6              slot[t] = job i; profit += p[i]
7              break
8  return slot, profit

Example. Jobs with (deadline, profit): J1 (2, 100), J2 (1, 19), J3 (2, 27), J4 (1, 25), J5 (3, 15). Sorted by profit: J1 (100), J3 (27), J4 (25), J2 (19), J5 (15).

• J1: deadline 2, take slot 2.
• J3: deadline 2, slot 2 is taken, so take slot 1.
• J4: deadline 1, slot 1 is taken, so reject.
• J2: deadline 1, slot 1 is taken, so reject.
• J5: deadline 3, take slot 3.

The sequence is J3, J1, J5, with profit $27+100+15=142$.

Complexity

• Sorting takes $O(n\log n)$.
• The slot search takes up to $O(n)$ per job, so the simple version takes $O(n^2)$ in the worst case.
• Using a disjoint-set (union-find) structure to find the latest free slot gives about $O(n\log n)$ overall.

The simple algorithm therefore runs in $O(n^2)$, and the improved one in $O(n\log n)$.

Memoization

Memoization is a top-down technique that speeds up a recursive algorithm by storing the result of each subproblem the first time it is computed. When the same subproblem comes up again, the stored value is returned instead of recomputing it. The word comes from "memo". A table (array or hash map) keeps the results.

Example: Fibonacci

MEMO-FIB(n)
1  if memo[n] is defined: return memo[n]
2  if n <= 1: return n
3  memo[n] = MEMO-FIB(n-1) + MEMO-FIB(n-2)
4  return memo[n]

The naive recursion takes $O(2^n)$ time. With memoization each $F(k)$ is computed once, so the time is $O(n)$.

Comparison with dynamic programming

Both avoid repeated work, and both have the same asymptotic time in the usual case, which is the number of distinct subproblems times the work per subproblem.

Backtracking

Backtracking is a general method for problems where a solution is a sequence of choices (a vector $(x_1,\dots,x_n)$) subject to constraints. It searches the state-space tree depth first. At each node the partial solution is extended by one choice. If the partial solution already violates a constraint (or cannot lead to a better solution), the node is pruned and the search goes back (backtracks) to the previous level to try another option. When a complete valid solution is found, it is reported (or the search continues for all solutions).

BACKTRACK(k)
    for each value v in the choices for x[k]
        x[k] = v
        if feasible(x[1..k])
            if k == n: output x
            else BACKTRACK(k+1)

Examples: N-queens, graph colouring, sum of subsets, Hamiltonian cycle, and maze solving. For example, in 4-queens, if a queen placed in row 3 has no safe column, the algorithm returns to row 2 and moves that queen.

Difference from recursion

Backtracking is normally implemented using recursion, so backtracking uses recursion, but not every recursive algorithm is backtracking.

These classes are defined for decision problems (yes or no answers).

P. The class of problems that a deterministic algorithm can solve in polynomial time $O(n^k)$. Examples: sorting, searching, shortest path, MST. These are regarded as efficiently solvable (tractable).

NP. The class of problems for which a given solution (certificate) can be verified in polynomial time. Equivalently, they are solved in polynomial time by a non-deterministic machine. Examples: Hamiltonian cycle, subset sum, SAT, graph colouring. Every problem in P is in NP, so $P\subseteq NP$. Whether $P=NP$ is the major open question.

NP-complete (NPC). A problem $L$ is NP-complete if:

1. $L\in NP$, and
2. every problem in NP can be reduced to $L$ in polynomial time.

NP-complete problems are the hardest problems in NP. If any one of them is solved in polynomial time, then every problem in NP is, and $P=NP$. Examples: SAT (the first, by Cook's theorem), 3-SAT, clique, vertex cover, and the decision version of the travelling salesman problem.

A problem that satisfies only condition 2 is NP-hard. So $NPC=NP\cap NP\text{-hard}$.

To prove a new problem NP-complete, we show it is in NP and reduce a known NP-complete problem to it in polynomial time.

(a) NP-hard problems and NP-completeness

A problem $H$ is NP-hard if every problem in NP can be reduced to $H$ in polynomial time. NP-hard problems are at least as hard as every problem in NP. They need not be decision problems and need not be in NP. Examples: the halting problem, the optimisation travelling salesman problem.

A problem is NP-complete if it is both in NP and NP-hard. So NP-complete problems are the hardest problems inside NP. Examples: SAT, 3-SAT, clique, vertex cover, Hamiltonian cycle, subset sum.

Consequences:

• If one NP-complete problem has a polynomial-time algorithm, then $P=NP$.
• If $P\ne NP$, no NP-complete problem can be solved in polynomial time.
• Cook's theorem showed that SAT is NP-complete. Other problems are then proved NP-complete by reduction from known NP-complete problems.

(b) Problem reduction

A problem $A$ is reducible to a problem $B$ ($A\le_pB$) if there is a polynomial-time function $f$ that converts any instance $x$ of $A$ into an instance $f(x)$ of $B$, such that

$x \text{ is a yes-instance of } A \iff f(x) \text{ is a yes-instance of } B$

So an algorithm for $B$, with the conversion, solves $A$. Meaning:

• If $B$ is easy (in P), then $A$ is easy.
• If $A$ is hard (NP-complete), then $B$ is at least as hard.

Example: the Hamiltonian cycle problem reduces to the travelling salesman problem. Give the edges of the graph cost 1 and the missing edges cost 2. The graph has a Hamiltonian cycle if and only if the tour has cost at most $n$.

Reduction is the main tool for proving NP-completeness: show the problem is in NP, then reduce a known NP-complete problem to it.

Divide and conquer

This strategy has three steps.

1. Divide the problem into smaller subproblems of the same type.
2. Conquer them by solving them recursively. Small subproblems are solved directly.
3. Combine the sub-solutions to get the solution of the original problem.

The time is described by $T(n)=aT(n/b)+f(n)$. Examples: merge sort, quick sort, binary search, Strassen's matrix multiplication.

Selection problem. Find the $i$-th smallest element of an array of $n$ distinct elements. Sorting would take $O(n\log n)$. Randomized-select has expected time $O(n)$ but its worst case is $O(n^2)$. The median-of-medians algorithm guarantees $O(n)$ in the worst case.

SELECT(A, n, i)

1. Divide the $n$ elements into $\lceil n/5\rceil$ groups of 5 elements (the last group may be smaller).
2. Sort each group (insertion sort) and find its median.
3. Recursively call SELECT to find $x$, the median of these $\lceil n/5\rceil$ medians.
4. Partition the array around $x$. Let $k$ be the rank of $x$, so $k-1$ elements are less than $x$.
5. If $i=k$, return $x$. If $i<k$, recursively select the $i$-th smallest in the lower part. Otherwise select the $(i-k)$-th smallest in the upper part.

Analysis

At least half of the $\lceil n/5\rceil$ group medians are $\ge x$. Each of those groups (except possibly the last and the group containing $x$) has at least 3 elements $\ge x$. So the number of elements greater than $x$ is at least

$3\left(\left\lceil\frac12\left\lceil\frac n5\right\rceil\right\rceil-2\right)\ge\frac{3n}{10}-6$

By symmetry, at least $3n/10-6$ elements are less than $x$. So in step 5 the recursion is on at most $7n/10+6$ elements.

Costs: steps 1, 2 and 4 take $O(n)$. Step 3 takes $T(\lceil n/5\rceil)$. Step 5 takes at most $T(7n/10+6)$. Hence

$T(n)\le T(\lceil n/5\rceil)+T(7n/10+6)+O(n)$

Guess $T(n)\le cn$. Then, for large $n$,

$T(n)\le c\frac n5+c\left(\frac{7n}{10}+6\right)+an=\frac{9cn}{10}+6c+an=cn-\left(\frac{cn}{10}-6c-an\right)\le cn$

provided $\frac{cn}{10}-6c-an\ge0$, which holds for a large enough constant $c$ and $n\ge$ some $n_0$ (for example $c\ge20a$ and $n\ge120$).

Therefore the worst-case time is $T(n)=O(n)$. The groups of 5 are essential: because $1/5+7/10<1$, the work shrinks geometrically.