HT2026 Design & Analysis of Algorithms notes

Definition 1.1:An algorithm is a finite set of well-defined instructions to accomplish a specific task.

Definition 1.2:An efficient algorithm runs in polynomial time.

Definition 1.3: Insertion sort compares each 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 integer array A
Output: Array A sorted in non-decreasing order

for j = 1 to A.length - 1
  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 where is the number of times the test of the while loop is executed for a given value of .

Then in the worst case, , so for some . Hence is quadratic in .

In the best case, so is linear.

Definition 1.5: Let . Then

If then is an asymptotic upper bound for .

Proposition 1.6: The algorithm is correct.

Proof:

By a loop-invariant argument:

• Initialisation - Prove the invariant holds prior to first iteration
• Maintenance - Prove that if holds just before an iteration, then it holds just before the next iteration
• Termination: Prove that, when the loop terminates, the invariant along with the reason the loop terminates imply the correctness of the program

This is similar to mathematical induction, but rather than proving for all numbers, we expect to exit the loop.

Invariant: At the start of the th iteration, A[1..j] is sorted.

When , is a singleton so is trivially sorted.

The outer loop terminates when j = A.length. So the loop invariant at termination says that A[1..A.length] = A is sorted.

To prove maintenance, we need to prove that, at the end of the while loop, the sequence A[1], ..., A[i], key, A[i+2], ..., A[j+1] are sorted.

The invariant of the while loop is: TODO

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 . Then:

Definition 1.8: If , we say that is an asymptotic lower bound for .

Corollary 1.9: .

Definition 1.10: If , is an asymptotic tight bound for .

Remark: Big // are not closed under function composition.

Definition 2.1: A divide and conquer algorithm divides the problem into subproblems, solves each subproblem separately and combines the results.

Example (merge sort):

1. Split array into 2 ()
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

Overall (worst case).

Psuedocode: TODO

if r > p + 1
  q = floor((p + r) / 2)

Pseudocode for merge subroutine: TODO

todo

Remark: Merging should be left-biased so that mergesort is a stable sort.

Merge sort is not in-place (requires extra space) and is not inline.

Example (merge sort runtime analysis): We have , and .

Then

where , i.e.

Theorem 2.2 (Master Theorem):

Suppose

then

Proof:

TODO

Example (Master theorem for merge sort):

For merge sort, , so we have , , so .

Remark: Suppose a recursion splits into two subproblem with size , and suppose that the division is and the combining is . Then we have , which isn’t directly expressible with the Master Theorem. We can substitute to get ; if we let then . We can then use the Master Theorem, with , giving that . Hence

Theorem 2.3: The running time of every comparison-based sorting algorithm is , i.e. at best it is .

Proof:

In a descision tree of a comparison-based sorting algorithm on an input of length , there are leaves. Every binary tree of depth has at most leaves; so to get to we need a depth of at least .

Definition 2.4: 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 ( if ) but is not in-place; however we can design it to be stable.

Input: An array A of n elements with elements in the range [arrow(0)..k]
Output: An array B consisting of a sorted permutation of A

TODO

Definition 2.5: The Fast Fourier Transform (FFT) can be used to multiply two polynomials of degree in time.

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

   This is nice because each polynomial is an even function. We now have that

2. Represent each polynomial by a list of values at points, which can be computed in by Horner’s rule,

… TODO

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

Remark: Unsorted arrays have insertion and finding the maximum.

Remark: Sorted arrays have insertion (find position by binary search but then shifting is linear) but finding the maximum.

Corollary 3.1: It is not possible to have a data structure with insertion and maximum extraction, as this would give a linear-time comparison-based sorting algorithm which we have seen isn’t possible.

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.

The height of a tree is the longest simple path from the root to a leaf; a binary heap with nodes has height .

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.3: A max-heap is a heap that satisfies the max-heap property.

Definition 3.4: The max-heap property states that the key of any node (except the root) is less than or equal to the key of its parent.

Remark: The maximum element of a max-heap is at the root.

Remark: Min-heaps can be defined similarly.

Remark: Children of a node in a max-heap are not necessarily sorted.

Definition 3.5: 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 worst case like merge sort, but is in-place like insertion sort.

Definition 3.6: 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
• maximuum(S) returns the element of S with the largest key
• extractMax(S) removes and returns the element of S with the largest key
• TODO

If we implement the priority queue as a heap, both insertion and extraction are .

TODO increasing the key value

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, , and want to give units of change.

Then .

More formally,

The running time is . 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 . There are itmes to pick from, of size/weight and value . 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 .

Where there is only one of each item:

The running time is .

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 .

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

Now the running time is .

Example (Longest increasing subsequences): Task: find the longest increasing subsequences of a sequence; the elements in a subsequence don’t need to all be adjacent to each other in the original sequence. TODO

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 , 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 containing , and for every , find the shortest path that starts from , ends in , and passes only once through all the other nodes in . Define to be the length of that path.

Then

TODO

Example (A better algorithm for longest increasing subsequence): TODO

Remark: A directed acyclic graph can be abbreviated to dag.

Definition 5.1: An adjacency matrix of a graph is a matrix where

TODO

Remark: Given an adjacency matrix , is the number of walk of length from to .

If represents an undirected graph, is the degree of .

Remark: An adjacency list for a graph is a list of linked lists, one per vertex: the list for vertex holds the indices of vertices to which has an outgoing edge.

This has size

TODO

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
Output: for each vertex , a backpointer (the predecessor of ) and two timestamps, the discovery time and finishing time .

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 .

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 because each vertex is visited once, and DFSVisit(v) takes where is the degree of ; .

If we map out the edges visited by DFS, we get a forest that we call 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.3 (Parenthesis theorem): For all , exactly one of the following holds:

1. or and neither of and are descendants of each other in the DFS forest
2. and is a descendant of in a DFS tree
3. and is a descendant of in a DFS tree

Using shorthand TODO

Corollary 5.4: Vertex is a descendant of vertex iff .

TODO

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

• Tree edges are edges of the DFS forest; is white when is explored;
• Back edges lead from a node to an ancestor in the DFS tree. is grey when 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 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 is explored.

TODO discovery and finishing times vs edge classification

Theorem 5.6: A directed graph has a cycle iff has a back edge.

Proof:

: If is a back edge, then there is a cycle consisting of the back edge and the path in the DFS tree from to .

: TODO

Definition 5.7: A topological sort of a DAG is a total ordering of vertices, , such that if then .

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

Remark: When DFS is applied to an undirected graph, the DFS trees correspond to the connected components of the graph. These can be identified by the discovery and finishing times.