HT2026 Design & Analysis of Algorithms notes

Definition 1.3: Insertion sort compares each $\left(𝑖+1\right)$the element and compares it with the previously sorted $𝑖$ elements, inserting it in the correct place.

In CRLS-style pseudocode (as used in Introduction to Algorithms):

Input: An 1-indexed array A of integers
Output: Array A is sorted in non-decreasing order

InsertionSort(A):
  for j = 2 to A.length
    key = A[j + 1]
    // insert A[j + 1] into the sorted sequence A[1..j]
    i = j
    while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i - 1
    A[i + 1] = key

Definition 1.4: The running time of a CLRS program is defined as:

• Line $𝑖$ takes constant time ${𝑐}_{𝑖}$
• When a loop exits normally, the test is executed one more time than the loop body

Remark: The running time of insertion sort as given is $𝑇\left(𝑛\right)={𝑐}_1𝑛+{𝑐}_2\left(𝑛-1\right)+{𝑐}_3\left(𝑛-1\right)+{𝑐}_4\left(𝑛-1\right)+{𝑐}_5{\sum }_{𝑗=1}^{𝑛-1}{𝑡}_{𝑗}+{𝑐}_6{\sum }_{𝑗=1}^{𝑛-1}\left({𝑡}_{𝑗}-1\right)+{𝑐}_7{\sum }_{𝑗=1}^{𝑛-1}\left({𝑡}_{𝑗}-1\right)+{𝑐}_8\left(𝑛-1\right)$ where ${𝑡}_{𝑗}$ is the number of times the test of the while loop is executed for a given value of $𝑗$.

Then in the worst case, ${𝑡}_{𝑗}=𝑗+1$, so $𝑇\left(𝑛\right)=𝑎{𝑛}^2+𝑏𝑛+𝑐$ for some $𝑎,𝑏,𝑐$. Hence $𝑇\left(𝑛\right)$ is quadratic in $𝑛$.

In the best case, ${𝑡}_{𝑗}=1$ so $𝑇\left(𝑛\right)$ is linear.

Definition 1.5: Let $𝑓,𝑔:\mathbb{N}\to {ℝ}^{+}$. Then

If $𝑓\in 𝑂\left(𝑔\left(𝑛\right)\right)$ then $𝑔$ is an asymptotic upper bound for $𝑓$.

Proposition 1.6: The algorithm is correct.

Remark: Some nice properties of insertion sort:

• It is stable (preserves relative order of equal keys)
• In-place
• Online (can sort the list as it is recieved)

Lemma 1.7: Let $𝑓,𝑔,ℎ:\mathbb{N}⟶{ℝ}^{+}$. Then:

• $\forall 𝑐>0.𝑓\in 𝑂\left(𝑔\right)⟹𝑐𝑓\in 𝑂\left(𝑔\right)$
• $\forall 𝑐>0.𝑓\in 𝑂\left(𝑔\right)⟹𝑓\in 𝑂\left(𝑐𝑔\right)$
• ${𝑓}_1\in 𝑂\left({𝑔}_1\right)\wedge {𝑓}_2\in 𝑂\left({𝑔}_2\right)⟹{𝑓}_1+{𝑓}_2\in 𝑂\left({𝑔}_1+{𝑔}_2\right)$
• ${𝑓}_1\in 𝑂\left({𝑔}_1\right)\wedge {𝑓}_2\in 𝑂\left({𝑔}_2\right)⟹{𝑓}_1+{𝑓}_2\in 𝑂\left(max\left({𝑔}_1,{𝑔}_2\right)\right)$
• ${𝑓}_1\in 𝑂\left({𝑔}_1\right)\wedge {𝑓}_2\in 𝑂\left({𝑔}_2\right)⟹{𝑓}_1\cdot {𝑓}_2\in 𝑂\left({𝑔}_1\cdot {𝑔}_2\right)$
• $𝑓\in 𝑂\left(𝑔\right)\wedge 𝑔\in 𝑂\left(ℎ\right)⟹𝑓\in 𝑂\left(ℎ\right)$
• $\forall 𝑙>0.\forall 𝑝\in {\mathrm{𝒫︀}}_{𝑙}.𝑝\left(𝑛\right)\in 𝑂\left({𝑛}^{𝑙}\right)$ where ${\mathrm{𝒫︀}}_{𝑙}$ is the set of $𝑙$-degree polynomials
• $\forall 𝑐>0.lg\left({𝑛}^{𝑐}\right)\in 𝑂\left(lg\left(𝑛\right)\right)$
• $\forall 𝑐,𝑑>0.{lg}^{𝑐}\left(𝑛\right)\in 𝑂\left({𝑛}^{𝑑}\right)$
• $\forall 𝑐>0,𝑑>1.{𝑛}^{𝑐}\in 𝑂\left({𝑑}^{𝑛}\right)$
• $\forall 0\le 𝑐\le 𝑑.{𝑐}^{𝑛}\in 𝑂\left({𝑑}^{𝑛}\right)$

Definition 1.10: If $𝑓\left(𝑛\right)\in \mathrm{\Theta }\left(𝑔\left(𝑛\right)\right)$, $𝑔$ is an asymptotic tight bound for $𝑓$.

Remark: In general, a divide and conquer algorithm working on an input of size $𝑛$ can be defined as:

• If $𝑛$ is small, $𝑛\le \mathrm{𝓁︀}$ for some constant $\mathrm{𝓁︀}$, use constant-time brute force solution
• Otherwise, divide the problem into $𝑎$ subproblems, each $\frac{1}{𝑏}$ the size of the original
• Let the time to divide a size-$𝑛$ problem be $𝐷\left(𝑛\right)$
• Let the time to combine solutions be $𝐶\left(𝑛\right)$.

Let $𝐷\left(𝑛\right)$ be the time taken to split a size-$𝑛$ problem up, and $𝐶\left(𝑛\right)$ be the time taken to combine solutions of subproblems.

Then the running time, $𝑇\left(𝑛\right)$, of a divide-and-conquer algorithm can in general be expressed by the following recurrence:

Theorem 2.2 (Master Theorem):

Suppose

Then

Example (merge sort):

1. Split array into 2 ($𝑂\left(1\right)$)
2. Carry out merge sort of on the subarrays (or for singletons, do nothing)
3. Merge the elements from the sorted sublists in order, which is easy as we just pick the smallest first element from each

Pseudocode:

MergeSort(A, p, r):
  if r > p + 1
    q = $\lfloor$(p + r) / 2⌋
    MergeSort(A, p, q)
    MergeSort(A, q + 1, r)
    Merge(A, p, q, r)

Where Merge is defined as:

// Merge A[p..q] and A[p+1..r] so that A[p..r] is sorted
Merge(A, p, q, r):
  ${𝑛}_1$ = q - p + 1
  ${𝑛}_2$ = r - q
  let L[1..${𝑛}_1$ + 1] and R[1..${𝑛}_2$ + 1] be new arrays
  for i = 1 to ${𝑛}_1$:
  L[i] = A[p + i - 1]
  for j = 1 to ${𝑛}_2$:
    R[j] = A[q + j]
  // Set the last values of the arrays to be larger than
  // anything else we could encounter, so we don't need
  // to check if we have exhausted all the elements of
  // either array if they aren't balanced 
  L[${𝑛}_1$ + 1] = $\infty$
  L[${𝑛}_2$ + 1] = $\infty$
  i = 1
  j = 1
  for k = p to r:
    if L[i] $\le$ R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1

Merge is clearly linear.

Then for MergeSort, in the form given above we have $𝐷\left(𝑛\right)=\mathrm{\Theta }\left(1\right)$, $𝑎=𝑏=2$ and $𝐶\left(𝑛\right)=\mathrm{\Theta }\left(𝑛\right)$.

Then

for some constant $𝑐$.

There are a few approaches we could use to solve for $𝑇\left(𝑛\right)$:

• Guess a solution, and use induction to find constants and prove that it works
• Draw out a recursion tree and sum each level, either to obtain an exact answer or to gain a heuristic to guess and check
• Or use the Master Theorem.

Using the Master Theorem, we get that $𝑇\left(𝑛\right)=𝑛log𝑛$.

Example (Integer multiplication): Suppose we want to multiply two $𝑛$-bit integers, $𝑥$ and $𝑦$.

A simple divide-and-conquer approach would be to split each number into a top and bottom half, ${𝑥}_{𝑙},{𝑥}_{𝑟},{𝑦}_{𝑙},{𝑦}_{𝑟}$, then

Therefore we can compute four multiplications and combine them with three additions (which are linear time in $𝑛$).

The time complexity of this is $𝑇\left(𝑛\right)=4𝑇\left(\frac{𝑛}{2}\right)+𝑂\left(𝑛\right)$, which by the Master Theorem is $𝑂\left({𝑛}^2\right)$.

However, we can do better.

Example (matrix multiplication):

A Naïve matrix multiplication algorithm, based on the definition, operating on $𝑛\times 𝑛$ matrices has time complexity $𝑂\left({𝑛}^3\right)$, as it needs to compute $𝑛$ multiplications, ${𝑛}^2$ times.

A naïve divide-and-conquer approach might split each matrix into four $\frac{𝑛}{2}\times \frac{𝑛}{2}$ matrices, and compute $𝐂=𝐀𝐁$ as

This requires computing 8 subproblems (${𝐀}_{11}{𝐁}_{11},{𝐀}_{12}{𝐁}_{\mathrm{𝟏}\mathrm{𝟏}}$ etc), and the addition of the submatrices is quadratic, so the time complexity is

This is no better than the previous approach, but it is possible to improve upon this.

Definition 2.5: Binary search searches for the presence or position of an element in a sorted array:

// Search for the presence of z in A[p..r]
BinSearch(A, p, r, z):
  if p >= r:
    return "no"
  q = $\lfloor$(p + r) / 2⌋
  if z == A[q]:
    return "yes"
  else if z < A[q]:
    return BinSearch(A, p, q, z)
  else:
    return BinSearch(A, q + 1, r, x)

This has running time $𝑇\left(𝑛\right)\le 𝑇\left(\lceil \frac{𝑛}{2}\rceil \right)+𝑂\left(1\right)$; by the master theorem $𝑇\left(𝑛\right)=𝑂\left(log𝑛\right)$

Definition 2.7: The Select algorithm finds the $𝑖$th-order statistic in linear time. It does this by partitioning the elements of the list around an estimate for the median, based on the medians of sublists of length 5, and from there operating on one of the smaller subgroups.

Select(A, i):
  medians = []
  for j = 1 to A.length by 5:
    sort A[i..i+5)
    medians[$\lceil$j / 5⌉] = A[i+2] // "baby median"
  x = Select(medians, $\lfloor$(medians.length + 1) / 2⌋) // median of medians
  partition A into lt, gt, based on size compared to x
  k = lt.length
  if i = k + 1:
    return x
  else if i <= k:
    return Select(lt, i)
  else if i > k + 1:
    return Select(gt, i - k - 1)

How good is the median of medians as an estimate of the true median? The number of elements $<𝑥$ is at least $\frac{3𝑛}{10}-6$.

So then the size of each subarray is no more that $\lfloor 7𝑛/10+6\rfloor$.

Then it can be proven that the running time is linear, by guessing that $𝑇\left(𝑛\right)=𝑐𝑛$ for some constant $𝑐$, and using induction.

Theorem 2.8: The running time of every comparison-based sorting algorithm is $\mathrm{\Omega }\left(𝑛log𝑛\right)$, i.e. at best it is $𝑂\left(𝑛log𝑛\right)$.

Definition 2.9: If we know our elements come from a certain discrete interval, we can use counting sort: just count how often each element appears, then insert the relevant number of each elements. This is $𝑂\left(𝑛+𝑘\right)$ ($=𝑂\left(𝑛\right)$ if $𝑘=𝑂\left(𝑛\right)$) but is not in-place; however we can design it to be stable. The height of a tree is the longest simple path from the root to a leaf; a binary heap with $𝑛$ nodes has height $\lfloor log𝑛\rfloor$.

Input: An array A of n elements with elements in the interval $\left[0..𝑘\right]$
Output: An array B consisting of a sorted permutation of A

CountingSort(A, k):
  create array C of size k + 1
  for i = 0 to k:
    C[i] = 0
  for j = 1 to A.length:
    C[A[j]] += 1
  for i = 1 to k:
    C[i] = C[i] + C[i - 1]
  // C[i] now contains the number of elements <= i
  for j = n downto 1:
    B[C[A[j]]] = A[j]
    C[A[j]] -= 1

Definition 2.10: The Fast Fourier Transform (FFT) can be used to multiply two polynomials of degree $\left(𝑛-1\right)$ in $𝑂\left(𝑛log𝑛\right)$ time.

1. Split each polynomial into 2 polynomials of even degree:

   $${𝑎}_0+{𝑎}_1𝑥+{𝑎}_2{𝑥}^2+\dots =\left({𝑎}_0+{𝑎}_2{𝑥}^2+\dots \right)+𝑥\left({𝑎}_1+{𝑎}_3{𝑥}^2+\dots \right).$$

   This is nice because each polynomial is an even function. We now have that $𝐴\left(𝑥\right)={𝐴}_{\text{even}\left({𝑥}^2\right)}+𝑥{𝐴}_{\text{even}\left({𝑥}^2\right)}$

2. Represent each polynomial by a list of values at points, which can be computed in $𝑂\left(𝑛\right)$ by Horner’s rule,

   $$𝐴\left({𝑥}_0\right)={𝑎}_0+{𝑥}_0\left({𝑎}_1+{𝑥}_0\left({𝑎}_2+\dots \right)\right)$$

… TODO

Essentially, we split into two polynomials and recurse. Once we are in point-value form, we can multiply each point, all in $𝑂\left(𝑛\right)$, and then convert back to coefficient form (interpolation).

Definition 3.2: A heap is a data structure that is a tree that is completely filled on all levels except the lowest, which is filled from the left to right.

Heaps can be represented with arrays, with each level stored next to each other, read left-to-right and top-to-bottom. This is unambiguous because the tree is complete, so we know how many children each element has.

For a binary tree, if we have the root at A[0], the left child of A[i] is at A[2i + 1] and the right child is at A[2i + 2]. If arrays are 1-indexed, we instead get A[i]‘s children at A[2i] and A[2i + 1].

Definition 3.6: The MaxHeapify procedure turns a heap into a max heap, where the two subtrees of the root are already max-heaps. This works by ‘bubbling’ the root down into a permissible location.

Input: A 1-indexed array A and index i such that the subtrees of the node A[i] are max-heaps.
Output: A max heap with root at A[i].

MaxHeapify(A, i):
  n = A.size
  l = 2i
  r = 2i + 1
  if l <= n and A[l] > A[i]:
    largest = l
  else:
    largest = i
  if r <= n and A[r] > A[largest]:
    largest = r
  if largest != i:
    swap A[i] and A[largest]
    MaxHeapify(A, largest)

This is $𝑂\left(log𝑛\right)$ because the procedure runs at most once for each depth level in the tree; we can also see this by the master theorem: the two subtrees have a maximum size of $2\frac{𝑛}{3}$, occurring on the left if the bottom row is exactly half full, so

Definition 3.7: The MakeMaxHeap procedure forms a max heap from an unordered array.

We carry out MaxHeapify on every node, starting from the bottom, but skipping leaves, as they are already singleton max-heaps; allows us to skips about half of the nodes.

MakeMaxHeap(A):
  for i = ceil((n + 1) / 2) - 1 downto 1
    MaxHeapify(A, i)

This is definitely $𝑂\left(𝑛log𝑛\right)$, but in fact a tighter bound is $𝑂\left(𝑛\right)$.

Definition 3.8: Heap sort:

1. Build a max-heap
2. Starting from the root, swap the maximum with the final element in the backing array, and ignore the final node from now on (it remains in the backing array, but we decrement the heap size), then carry out MaxHeapify on the root (this is fine because the children are still max-heaps)
3. Repeat until the heap size is 1

This is $𝑂\left(𝑛log𝑛\right)$ worst case like merge sort, but is in-place like insertion sort.

Definition 3.9: A priority queue maintains a set of elements, each with an associated key. Max-priority queues give priority to elements with larger keys; min-priority keys are defined similarly.

Max-priority queues have the following operations:

• Insert(S, x, k) inserts element x with key k into S
• Maximum(S) returns the element of S with the largest key
• ExtractMax(S) removes and returns the element of S with the largest key
• IncreaseKey(S, x, k) increases the value of x’s key to k, which is assumed to be at least as large as the existing key

If we implement the max-/min-priority queue as a max-/min-heap, both Insert and ExtractMax are $𝑂\left(log𝑛\right)$, and are as described above. Maximum is $𝑂\left(1\right)$ and simply returns the root of the heap.

Definition 3.10: IncreaseKey works by modifying the key, and then bubbles the node up until it satisfies the max-heap property. Note that it does not just call MaxHeapify on the parents of the node, as this would unnecessarily visit sibling nodes as well.

Here A is 1-indexed as before.

IncreaseKey(A, i, key):
  require(key >= A[i])
  A[i] = key
  while i > 1 and A[floor(i / 2)] < A[i]:
    swap A[i] and A[floor(i / 2)]
    i = floor(i / 2)

This is also $𝑂\left(log𝑛\right)$ as the while loop cannot run more times than the height of the heap.

Definition 4.1: Dynamic programming is an optimisation in which we define a sequence of subproblems such that:

• The subproblems are ordered from smalles to largest
• The largest is the one we want to solve
• The optimal solution of a subproblem can be constructed from the optimal solutions of smaller subproblems (this property is optimal substructure)

We then solve from smallest to largest and store the solutions.

Example (Change-making): Suppose we have lots of coins of different denominations, ${𝑥}_1,\dots ,{𝑥}_{𝑛}$, and want to give $𝑢$ units of change.

Then $𝐶\left(𝑢\right)≔min\mathrm{\#︎}\text{coins summing up to}𝑢$.

More formally,

The running time is $𝑂\left(𝑢𝑛\right)$. This is polynomial in $𝑛$ and $𝑣$ (i.e. in the number of inputs), but is exponential in the size of the inputs.

Example (Knapsack problem): A burglar has a knapsack with capacity $𝑊\in \mathbb{N}$. There are $𝑛$ itmes to pick from, of size/weight ${𝑤}_1,\dots ,{𝑤}_{𝑛}\in \mathbb{N}$ and value ${𝑣}_1,\dots ,{𝑣}_{𝑛}\in \mathbb{N}$. We want to find the most valuable configuration of items to steal, assuming that there is either 1 of each item, or an unlimited quantity of each.

Assuming first an unlimited supply of each item:

Total running time is $𝑂\left(𝑢𝑛\right)$.

Where there is only one of each item:

The running time is $𝑂\left(𝑢𝑛\cdot 2^{𝑛}\right)$.

But we can modify $𝐾$ to make it not exponential, by rather than passing a set of indices, passing the largest index that is considered - since if we remove item $𝑗$, we should have an optimal solution for $𝑗-1$.

This formulation is stating that for each index $𝑗$, we either pick that item or discard it.

Now the running time is $𝑂\left(𝑢𝑛\right)$.

Example (Longest simple path): This is an example of a problem that does not have optimal substructure: the longest simple paths from $𝐴$ to $𝐵$ and from $𝐵$ to $𝐶$ might share a vertex, so cannot be combined. We would therefore need to store not only the length of the longest path of a subproblem, but also the path itself; so dynamic programming cannot be used for this.

However, if the graph is acyclic, the problem does have optimal substructure.

Example (Travelling salesperson problem): Given a complete undirected graphs with weights ${𝑑}_{𝑖𝑗}$ associated with each edge $\left(𝑖,𝑗\right)$, find the Hamiltonian cycle with minimal total distance (sum of edge weights).

This is NP-complete, so we don’t know if there is a polynomial time solution, but we can verify a solution in polynomial time.

Brute force is very bad, but dynamic programming gives a better (but not polynomial) solution.

Subproblems: for every subset $𝑆\subseteq \left\{1,\dots ,𝑛\right\}$ containing $1$, and for every $𝑗\in 𝑆,𝑗\ne 1$, find the shortest path that starts from $1$, ends in $𝑗$, and passes only once through all the other nodes in $𝑆$. Define $𝐶\left[𝑆,𝑗\right]$ to be the length of that path.

Then

TODO

Definition 5.1: An adjacency matrix of a graph $𝐺≔\left(𝑉,𝐸\right)$ is a $\left|𝑉\right|\times \left|𝑉\right|$ matrix $𝐀$ where

This has size $𝑂\left({\left|𝑉\right|}^2\right)$, but has constant lookup for determining if an edge is present.

For undirected graphs, the adjacency matrix is symmetric.

Remark: Given an adjacency matrix $𝐴$, ${\left({𝐴}^{𝑛}\right)}_{𝑖𝑗}$ is the number of walk of length $𝑛$ from $𝑖$ to $𝑗$.

If $𝐴$ represents an undirected graph, ${\left({𝐴}^2\right)}_{𝑖,𝑖}$ is the degree of $𝑖$.

Remark: An adjacency list for a graph $𝐺≔\left(𝑉,𝐸\right)$ is a list of $\left|𝑉\right|$ linked lists, one per vertex: the list for vertex $𝑢$ holds the indices of vertices to which $𝑢$ has an outgoing edge.

This has size $𝑂\left(\left|𝑉\right|+\left|𝐸\right|\right)$ but does not not allow for checking for the presence of an edge in constant time.

For undirected graphs, if $𝑢$ is in $𝑣$’s adjacency list, then $𝑣$ is in $𝑢$’s.

Definition 5.2: Depth-first search (DFS) is a linear-time algorithm that tells us what parts of a graph are reachable from a given vertex. It works for both digraphs and undirected graphs.

As soon as a new vertex is discovered, explore from it. As DFS progresses, we assign each vertex a colour:

• not discovered yet (e.g. white)
• discovered, but not fully explored yet (e.g. grey)
• finished (e.g. black)

Input: A graph $𝐺≔\left(𝑉,𝐸\right)$
Output: for each vertex $𝑣\in 𝑉$, a backpointer $𝜋\left(𝑣\right)$ (the predecessor of $𝑣$) and two timestamps, the discovery time $𝑑\left[𝑣\right]$ and finishing time $𝑓\left[𝑣\right]$.

DFS(V, E):
  for u in V:
    colour[u] = white
    pi[u] = null
  time = 0
  for u in V:
    if colours[u] = white:
      DFSVisit(u)

DFSVisit(u):
  time += 1
  d[u] = time
  colour[u] = grey
  for v in neighbours(v):
    if colour[v] = white:
      pi[v] = u
      DFSVisit(v)
  time = time + 1
  f[u] = time
  colour[u] = black

Note that $\forall 𝑣\in 𝑉.1\le 𝑑\left[𝑣\right]<𝑓\left[𝑣\right]\le 2\left|𝑉\right|$.

Note that $𝜋,𝑑,𝑓$ are dependent upon the order in which the vertices in the graph are visited, and on the order of the vertices in the adjacency/neighbour lists.

This has running time $𝑂\left(\left|𝑉\right|+\left|𝐸\right|\right)$ because each vertex is visited once, and DFSVisit(v) takes $\mathrm{\Theta }\left(𝑑\left(𝑣\right)\right)$ where $𝑑\left(𝑣\right)$ is the degree of $𝑣$; ${\sum }_{𝑣\in 𝑉}𝑑\left(𝑣\right)=2\left|𝐸\right|$.

Definition 5.3: Let ${𝐸}_{𝜋}$ be the edges visited by DFS,

Then let ${𝐺}_{𝜋}=\left(𝑉,{𝐸}_{𝜋}\right)$ be the DFS forest, consisting of DFS trees (note that this is a slight abuse of notation because trees and forests are usually undirected).

Theorem 5.5 (Parenthesis theorem): For all $𝑢,𝑣\in 𝑉$, exactly one of the following holds:

1. $𝑑\left[𝑢\right]<𝑓\left[𝑢\right]<𝑑\left[𝑣\right]<𝑓\left[𝑣\right]$ or $𝑑\left[𝑣\right]<𝑓\left[𝑣\right]<𝑑\left[𝑢\right]<𝑓\left[𝑢\right]$ and neither of $𝑢$ and $𝑣$ are descendants of each other in the DFS forest
2. $𝑑\left[𝑢\right]<𝑑\left[𝑣\right]<𝑓\left[𝑣\right]<𝑓\left[𝑢\right]$ and $𝑣$ is a descendant of $𝑢$ in a DFS tree
3. $𝑑\left[𝑣\right]<𝑑\left[𝑢\right]<𝑓\left[𝑢\right]<𝑓\left[𝑣\right]$ and $𝑢$ is a descendant of $𝑣$ in a DFS tree

Using the shortand “$(𝑥$” for $𝑑\left[𝑥\right]$ and “$𝑥)$” for $𝑓\left[𝑥\right]$, $\left(𝑢𝑢\right)\left(𝑣𝑣\right)$ and $\left(𝑢\left(𝑣𝑣\right)𝑢\right)$ are possible (and the symmetric cases), but $\left(𝑢\left(𝑣𝑢\right)𝑣\right)$ is not possible.

Corollary 5.6: Vertex $𝑣$ is a descendant of vertex $𝑢$ iff $𝑑\left[𝑢\right]<𝑑\left[𝑣\right]<𝑓\left[𝑣\right]<𝑓\left[𝑢\right]$.

Theorem 5.7 (White edge theorem): A vertex $𝑣$ is a descendant of $𝑢$ iff, at time $𝑑\left[𝑢\right]$, there exists a path from $𝑢$ to $𝑣$ consisting of entirely white vertices.

Definition 5.8: We can classify edges of the searched graph:

• Tree edges $\left(𝑢,𝑣\right)$ are edges of the DFS forest; $𝑣$ is white when $\left(𝑢,𝑣\right)$ is explored;
• Back edges $\left(𝑢,𝑣\right)$ lead from a node to an ancestor in the DFS tree. $𝑣$ is grey when $\left(𝑢,𝑣\right)$ is explored;
• Forward edges lead from a node $𝑢$ to a non-child descendant in the DFS tree, i.e. they lead to a descendant but are not edges in the DFS forest. $𝑣$ is black when $\left(𝑢,𝑣\right)$ is explored;
• Cross edges do not lead to an ancestor or descendant; this could be between nodes in the same tree or in a different tree. $𝑣$ is black when $\left(𝑢,𝑣\right)$ is explored.

Remark: We can link the parentheses of $𝑢,𝑣$ to the classification of the edge $\left(𝑢,𝑣\right)$:

• If $𝑑\left[𝑢\right]<𝑑\left[𝑣\right]<𝑓\left[𝑣\right]<𝑓\left[𝑢\right]$, then $\left(𝑢,𝑣\right)$ is either a tree edge or a forward edge.
• If $𝑑\left[𝑣\right]<𝑑\left[𝑢\right]<𝑓\left[𝑢\right]<𝑓\left[𝑣\right]$, then $\left(𝑢,𝑣\right)$ is a back edge.
• If $𝑑\left[𝑣\right]<𝑓\left[𝑣\right]<𝑑\left[𝑢\right]<𝑓\left[𝑢\right]$, then $\left(𝑢,𝑣\right)$ is a cross edge.
• $𝑑\left[𝑢\right]<𝑓\left[𝑢\right]<𝑑\left[𝑣\right]<𝑓\left[𝑣\right]$ cannot happen because if $𝑣$ is not discovered when $𝑢$ is discovered, and $\left(𝑢,𝑣\right)\in 𝐸$, then $𝑣$ would be explored before $𝑢$ is finished.

Theorem 5.9: A directed graph $𝐺$ has a cycle iff $𝐺$ has a back edge.

Definition 5.10: A topological sort of a DAG $𝐺≔\left(𝑉,𝐸\right)$ is a total ordering of vertices, $<\subseteq 𝑉\times 𝑉$, such that if $\left(𝑢,𝑣\right)\in 𝐸$ then $𝑢<𝑣$, and otherwise $𝑢\nless 𝑣$.

TopologicalSort(V, E):
  f[v | v in V] = DFS(V, E)
  return V sorted according to decreasing f[v]

This has running time $𝑂\left(\left|𝑉\right|+\left|𝐸\right|\right)$.

Proposition 5.11 (correctness of topological sort): Given a DAG $𝐺≔\left(𝑉,𝐸\right)$, if $\left(𝑢,𝑣\right)\in 𝐸$ then $𝑓\left[𝑢\right]>𝑓\left[𝑣\right]$.

Lemma 5.14: Given distinct strongly connected components $𝐶,{𝐶}^{\prime }$ of a digraph $𝐺$, $𝑢,𝑣\in 𝐶,{𝑢}^{\prime },{𝑣}^{\prime }\in {𝐶}^{\prime }$, if there is a path from $𝑢$ to ${𝑢}^{\prime }$ in $𝐺$, then there is not a path from ${𝑣}^{\prime }$ to $𝑣$ in $𝐺$.

Definition 5.15: The SCC graph of a digraph $𝐺≔\left(𝑉,𝐸\right)$ is the graph ${𝐺}^{\text{SCC}}≔\left({𝑉}^{\text{SCC}},{𝐸}^{\text{SCC}}\right)$, such that

• ${𝑉}^{\text{SCC}}$ has one vertex ${𝑣}_{𝐶}$ for every SCC $𝐶$ in $𝐺$
• $\left({𝑣}_{𝐶},{𝑣}_{{𝐶}^{\prime }}\right)\in {𝐸}^{\text{SCC}}$ iff there exist $𝑢\in 𝐶,{𝑢}^{\prime }\in {𝐶}^{\prime }$ such that there is a path from $𝑢$ to ${𝑢}^{\prime }$.

Definition 5.16: We extend discovery and finishing times for sets of vertices $𝑈\subseteq 𝑉$:

• $𝑑\left[𝑈\right]≔min\left\{𝑑\left[𝑢\right]|𝑢\in 𝑈\right\}$, the earliest discovery time amongst $𝑈$;
• $𝑓\left[𝑈\right]≔max\left\{𝑓\left[𝑢\right]|𝑢\in 𝑈\right\}$, the latest finishing time amongst $𝑈$.

Lemma 5.18: Let $𝐶,{𝐶}^{\prime }$ be distinct SCCs in $𝐺≔\left(𝑉,𝐸\right)$. If there is an edge from $𝐶$ to ${𝐶}^{\prime }$, then $𝑓\left[𝐶\right]>𝑓\left[{𝐶}^{\prime }\right]$.

Lemma 5.19: If $𝐶\ne {𝐶}^{\prime }$ and $𝑓\left[𝐶\right]<𝑓\left[{𝐶}^{\prime }\right]$, then there cannot be an edge from $𝐶$ to ${𝐶}^{\prime }$.

Definition 5.20: For a digraph $𝐺≔\left(𝑉,𝐸\right)$, the transpose of $𝐺$ is ${𝐺}^{\top }=\left(𝑉,{𝐸}^{\top }\right)$ where

Remark: For distinct SCCs $𝐶,{𝐶}^{\prime }$ in $𝐺$, if $𝑓\left[𝐶\right]>𝑓\left[{𝐶}^{\prime }\right]$, then

• in $𝐺$ there cannot be an edge from ${𝐶}^{\prime }$ to $𝐶$
• in ${𝐺}^{\top }$ there cannot be an edge from $𝐶$ to ${𝐶}^{\prime }$.

This means that running DFS on ${𝐺}^{\top }$ starting from the SCC with the largest finishing time, we will not find edges to any other SCC.

Definition 5.22: The SCC algorithm, or Kosoraju’s algorithm, identifies all SCCs in a digraph $𝐺$:

• run DFS on $𝐺$
• run DFS on ${𝐺}^{\top }$, exploring in order of decreasing finishing time of the first DFS
• the trees in the DFS forest of the second DFS correspond to the SCCs of $𝐺$

Definition 6.1: Consider a digraph $𝐺≔\left(𝑉,𝐸\right)$ with weight function $𝑤:𝐸\to ℝ$.

The weight or length of a path $𝑝≔⟨{𝑣}_0,\dots ,{𝑣}_{𝑘}⟩$ is

Definition 6.2: The shortest-path weight between two vertices $𝑢,𝑣$ is

Definition 6.4: A FIFO queue (first in, first out) is a data structure with the following operations:

• enqueue($𝑄$, $𝑥$) - inserts x at the end of a queue
• dequeue($𝑄$) - removes and returns the item at the head of the queue
• isempty($𝑄$) - equivalent to $𝑄\ne \varnothing$

All of these operations can be implemented in $𝑂\left(1\right)$ if using a linked list with a pointer to the start and end.

Definition 6.5: Considering first the simple case where all weights are equal to 1. Let $𝛿\left(𝑢,𝑣\right)$ be the minimum number of edges on a path from $𝑢$ to $𝑣$, if such a path exists, otherwise $𝛿\left(𝑢,𝑣\right)=\infty$.

Given a source vertex $𝑠$, breadth-first search (BFS) finds all vertices ${𝑣}_{𝑖}$s reachable from $𝑠$, the shortest path lengths $𝛿\left(𝑠,{𝑣}_{𝑖}\right)$, and the shortest paths from $𝑠$ to the ${𝑣}_{𝑖}$s.

Idea:

• send out waves of increasing length from the source $𝑠$
• when a vertex $𝑣$ is reached, put it in the (FIFO) queue $𝑄$
• when all of $𝑣$s neighbours have been reached, remove $𝑣$ from $𝑄$

The output is a distance d[v] and predecessor $𝜋$[v] for every v $\in$ V.

BFS(V, E, s):
  for v $\in$ V \ { s }:
    d[v] = $\infty$
    $𝜋$[v] = null
  d[s] = 0
  Q = $\varnothing$
  enqueue(Q, s)
  while Q != $\varnothing$:
    u = dequeue(Q)
    for v $\in$ adj(u):
      if d[v] = $\infty$:
        d[v] = d[u] + 1
        $𝜋$[v] = u
        enqueue(Q, v)

Definition 6.6: The BFS tree consists of vertices reachable from $𝑠$ and edges $\left(𝑢,𝑣\right)$ where $𝑢=𝜋\left[𝑣\right]$.

More formally, the BFS tree is the graph

Lemma 6.9: If $𝑢$ is enqueued before $𝑣$, then $𝑑\left[𝑢\right]\le 𝑑\left[𝑣\right]$. Furthermore, if $𝑄=⟨{𝑣}_1,\dots ,{𝑣}_{𝑟}⟩$ is the queue at any given step of BFS, then

Theorem 6.11: $𝑑\left[𝑣\right]=𝛿\left(𝑠,𝑣\right)$.

Definition 6.13: Dijkstra’s algorithm is essentially BFS for weighted graphs. It solves the “single-source shortest path” problem for non-negative weights.

It uses a min-priority queue $𝑄$ rather than a FIFO queue, with keys given by the shortest-path weight estimates $𝑑\left[𝑣\right]$.

At termination:

• $𝑑\left[𝑣\right]$ is the distance from $𝑠$ to $𝑣$
• $𝜋\left[𝑣\right]$ is the predecessor of $𝑣$ on a shortest path from $𝑠$ to $𝑣$, if such a path exists

Dijkstra(V, E, w, s):
  for each v $\in$ V:
    d[v] = $\infty$
    $𝜋$[v] = null
  d[s] = 0
  Q = MakeMinQueue(V) with d[v] as keys
  while Q != $\varnothing$:
    u = ExtractMin(Q)
    for each v $\in$ adj(u):
      if d[u] + w(u, v) < d[v]:
        d[v] = d[u] + w(u, v)
        $𝜋$[v] = u
        DecreaseKey(Q, v, d[v])

Invariants for the while loop:

TODO initialisation

Then suppose that ${𝐼}_1$ holds before an iteration of the while loop. For any vertex $𝑣\in 𝑉$, either $𝑑\left[𝑣\right]$ did not change, or it did change. If $𝑑\left[𝑣\right]$ did not change, then $𝑑\left[𝑣\right]\ge 𝛿\left(𝑠,𝑣\right)$ by ${𝐼}_1$. Otherwise, let $𝑢$ be the vertex selected by ExtractMin in this iteration of the loop. Then we have that

Now suppose that ${𝐼}_2$ holds before an iteration. Then for any $𝑣\in {𝑆}^{\prime }$, either:

• $𝑣\in {𝑆}^{\prime }$, then $𝑑\left[𝑣\right]=𝛿\left(𝑠,𝑣\right)$ by ${𝐼}_2$
• $𝑣\notin 𝑆$ and there is no path from $𝑠$ to $𝑣$, then $𝑑\left[𝑣\right]\ge 𝛿\left(𝑠,𝑣\right)=\infty ⟹𝑑\left[𝑣\right]=\infty$
• $𝑣\notin 𝑆$ and there is a path from $𝑠$ to $𝑣$. Then there is also a shortest path $𝑠\stackrel{𝑝}{\twoheadrightarrow }𝑣$ TODO

TODO finish maintenance of ${𝐼}_2$

At termination, $𝑆=𝑉$, so $\forall 𝑣\in 𝑉.𝑑\left[𝑣\right]=𝛿\left(𝑠,𝑣\right)$.

TODO remark about optimal substructure

Theorem 6.15: For $𝑣\ne 𝑠,𝑑\left[𝑣\right]<\infty$, $𝜋\left[𝑣\right]$ is the predecessor of $𝑣$ on a shortest path from $𝑠$ to $𝑣$.

Definition 6.16: The Bellman-Ford algorithm takes a graph with weight function $𝑤:𝐸\to ℝ$ (possibly negative), and returns false if there exists a negative-weight cycle reachable from $𝑠$, otherwise true, along with $𝑑\left[𝑣\right],𝜋\left[𝑣\right]$ for each $𝑣\in 𝑉$.

BellmanFord(V, E, w, s):
  for each v $\in$ V:
    d[v] = $\infty$
    $𝜋$[v] = null
  d[s] = 0
  for i = 1 to $|$v| - 1: // run enoguh times to correctly compute distamce
    for each (u, v) $\in$ E:
      if d[u] + w(u, v) < d[v]: // Loop body the same as Dijkstra!
        d[v] = d[u] + w(u, v)
        $𝜋$[v] = u
  for (u, v) $\in$ E:
    if d[u] + w(u, v) < d[v]: // check for negative-weight cycles
      return false
  return true

This is $𝑂\left(\left|𝑉\right|\left|𝐸\right|\right)$.

TODO invariants

Definition 6.17: The Floyd-Warshall algorithm solves the all-pairs shortest paths problem for graphs with non-negative weights; that is, it gives the shortest path between every pair of vertices.

Suppose we have vertex set $𝑉=\left\{1,\dots ,𝑛\right\}$.

Let $𝑑\left[𝑖,𝑗;𝑘\right]$ be the length of the shortest path from $𝑖$ to $𝑗$, all of whose intermediate nodes are in the interval $\left[1,𝑘\right]$.

We initialise

Since there are no negative cycles, a shortest path from $𝑖$ to $𝑗$ using vertices in $\left[1,𝑘\right]$ goes through $𝑘$ at most once, so we use the recurrence

This covers all possible routes because we consider all $𝑘$, and choose to either pass through $𝑘$, or not pass through $𝑘$.

The algorithm is just dynamic programming as usual (TODO write it out anyway).

The running time is $𝑂\left({\left|𝑉\right|}^3\right)$.

Remark: Some other options for all-pairs shortest paths:

• Run Bellman-Ford for every vertex as a source: $𝑂\left({\left|𝑉\right|}^2\left|𝐸\right|\right)$, which is $𝑂\left({\left|𝑉\right|}^3\right)$ for sparse graphs and $𝑂\left({\left|𝑉\right|}^4\right)$ for dense graphs.

• Run Dijkstra for every vertex as a source (if all weights not-negative): $𝑂\left(\left|𝑉\right|log\left|𝑉\right|\left(\left|𝑉\right|+\left|𝐸\right|\right)\right)$, which is $𝑂\left({\left|𝑉\right|}^{2}log\left|𝑉\right|\right)$ for sparse graphs and $𝑂\left({\left|𝑉\right|}^{3}log\left|𝑉\right|\right)$ for dense graphs.

Lemma 7.3:

An undirected graph is a tree iff every pair of vertices is connected by a unique (simple) path.

Lemma 7.4: If a graph $𝐺≔\left(𝑉,𝐸\right)$ is a tree, than $\left|𝐸\right|=\left|𝑉\right|-1$.

Remark: A spanning tree is:

• a minimal connected subgraph (removing an edge disconnects it)
• a maximal acyclic subgraph (adding an edge creates a cycle).

Therefore any spanning tree has exactly $\left|𝑉\right|-1$ edges.

Lemma 7.6: Every connected graph has a spanning tree.

Definition 7.9: A cut is a partition of the vertex set into $𝑆$ and $𝑉\backslash 𝑆$.

An edge $\left(𝑢,𝑣\right)\in 𝐸$ crosses a cut if one endpoint is in $𝑆$ and the other is in $𝑉\backslash 𝑆$.