CS2040S Notes

Loop Invariants

Should be the same throughout the algorithm.

Used to prove correctness of algorithm and to understand how an algorithm works.

There are stronger and weaker invariants, stronger invariants are more detailed.

Some examples:

"At the end of iteration j: the first j items in the array are in sorted order." (insertion sort) -- also true for selection sort (but there is a stronger one for it)

After iteration j: the first j items in the array are in sorted order and are the j smallest items in the array." (selection sort)

Big O Definition

$T(n) = O(f(n))$ if T grows no faster than f.

There exists constants $c > 0$ and $n_0 > 0$ such that for all $n > n_0$: $T(n)<=cf(n)$.

Big Omega Definition

$T(n) = \Omega(f(n))$ if T grows no slower than f.

There exists constants $c > 0$ and $n_0 > 0$ such that for all $n > n_0$: $T(n)>=cf(n)$.

Big Theta Definition

$T(n) = \Theta(f(n))$ if T grows at the same rate as f.

$T(n) = \Theta(f(n))$ if and only if $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$

Note: $\log(n!)$ is $O(n\log n)$

Sterling's Approximation: $n! \approx \sqrt{2\pi n}(\frac{n}{e})^n$

Amortised Analysis

"Average" cost but NOT average.

Definition: Operation has amortised cost of T(n) if for every integer k, the cost of k operations is <=kT(n)

Must be true for ALL operations.

Properties of Different Sorting Algorithms

Different sorting algorithms have their place! Sometimes you want an algorithm with specific properties.

Absolute speed is usually not a good indicator (by itself)

BogoSort

Randomly generate a permutation and check if sorted. $O(n*n!)$

Not in-place. Not stable.

Bubble Sort

repeat n times:
  for j <- 1 to n-1:
    if A[j] > A[j+1] then swap(A[j], A[j+1])
  break if no swap is done (means sorted)

Compare and swap each element.

Average: $O(n^2)$ Best: $O(n)$ -- sorted (no swaps done) Worst: $O(n^2)$ -- reverse sorted n iterations of the array

Bubble sort iterates through the entire array (maximum of) n times and terminates early if no swap is done.

Loop Invariant: At the end of iteration j, the biggest j items are correctly sorted in the final j positions of the array.

Correctness: after n iterations, the array is sorted

In-place. Stable algorithm.

Selection Sort

Checks for the minimum element n times and swaps. Always: $\Theta(n^2)$

Loop Invariant: At the end of the iteration j, the smallest j items are correctly sorted in the first j positions of the array.

In-place. Not stable algorithm, swaps change element. (but possible to be stable if careful) At most $n$ swaps.

Insertion Sort

Average: $O(n^2)$ Best: $O(n)$ -- sorted (no swaps done) Worst: $O(n^2)$ -- reverse sorted

$O(nk)$ where k is the maximum distance of element from its sorted index

Loop Invariant: At the end of the iteration j, the first j items in the array are in sorted order.

Fast if the array is (almost) sorted.

In-place. Can be stable, iterate while A[i] > key and not >=

Merge Sort

Divide and conquer algorithm that splits the array into half recursively.

Average: $O(n\log n)$ Worst: $T(n)=2T(n/2)+cn$ -> $O(n\log n)$

In practice, Insertion Sort is faster than Merge Sort when arrays are < 1000 in size. Could be due to the need to copy array. So, it is possible to combine merge and insertion sort together to have a faster sorting algorithm than each of them alone.

Not in-place (possible but very tricky or slower, using array shifting) But can minimise memory used by only copying array at merge portion instead of at recursive call. Stable algorithm.

Quick Sort

Divide and conquer algorithm.

Using pivots to partitioning the array into 2: elements that are <= or > compared to the pivot. There is a double-pivot variant of quicksort that is faster than the single-pivot variant.

Average case: $O(n\log n)$ Worst case: $O(n^2)$ -- sorted or reverse sorted array (only for head or tail pivots)

Loop invariant: For every i < low: B[i] < pivot For every i >= high: B[i] > pivot

This version handles duplicates well. 3-way partitioning of the array (easy in theory but a lot of corner cases!)

< pivot | = pivot | in-progress | > pivot

Counting Sort

Good for small ranges of values with high amount of repetition.

Maintain another array as a counter. Count in $O(n)$. Then, re-construct the array using the counter in $O(n)$.

Can be stable if re-construct using a mix of original array and counter.

Stable but not in-place.

Radix Sort

Good for sorting integers or strings. Sort by first index of each container (), then second, etc. Or least significant to most significant digit.

$O(nm)$ where n is the size of the array and m is the size of the largest container.

Only faster than quicksort if small container sizes. $n>2^m$ to be faster.

Makes use of counting sort as a subroutine.

So, stable (if sort in correct order of least to most significant bits) but not in-place.

Other Notes

(For CS2040S) Total space ever allocated. Ignore memory allocators, garbage collectors, stack frames etc.

Option 1

1. Sort the array
2. Return the element number k $O(n\log n)$

Option 2

Only do the minimum amount of sorting necessary.

1. Pick a random pivot
2. Partition around the pivot
3. Then we know the pivot is the $i^{th}$ element.
4. Choose left or right half depending on if our target element is less than or more than the current element.
5. Recurse on the chosen side (not both!).

Worst "best case" of a 9:1 split. $T(n)=T(9n/10)+O(n)$ $O(n)$

// https://leetcode.com/problems/kth-largest-element-in-an-array/
class Solution {
  Random rng = new Random();

  private int randomInt(int lo, int hi) {
    // hi is inclusive
    return lo + rng.nextInt(hi - lo + 1);
  }

  private void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
  }

  // this is a simple 2-way partitioning

  // there are better (and more complex) partitioning algorithms, notably:
  // 3-way partitioning same complexities but has better average real time (when duplicate values are involved)
  // Median of medians worst case O(n log n) https://en.wikipedia.org/wiki/Median_of_medians
  private int partition(int[] nums, int lo, int hi) {
    // returns the rank of the pivot
    int pivot = randomInt(lo, hi);
    int value = nums[pivot];
    swap(nums, lo, pivot);
    int pointer = lo + 1;
    for (int i = lo + 1; i <= hi; i++) {
      int x = nums[i];
      if (x < value) {
        swap(nums, i, pointer++);
      }
    }
    swap(nums, lo, pointer - 1);
    return pointer - 1;
  }

  private int findKthSmallest(int[] nums, int lo, int hi, int k) {
    int index = partition(nums, lo, hi);
    if (index > k) {
      return findKthSmallest(nums, lo, index - 1, k);
    } else if (index < k) {
      return findKthSmallest(nums, index + 1, hi, k);
    } else {
      return nums[k];
    }
  }

  public int findKthLargest(int[] nums, int k) {
    // quick select => O(n)
    int N = nums.length;
    return findKthSmallest(nums, 0, N - 1, N - k);
  }
}

Finding the largest $k$ elements in an unsorted array.

1. Quick select to find the $k^{th}$ largest element in the array.
2. 2 Options
3. Scan through the array and collect those >= $k^{th}$ largest item as found in (1).
4. Select everything from $k^{th}$ and to the right of it in the quick selected array.

Finding the smallest $k$ elements is similar.

Height of Tree

The height of a rooted tree is the maximum level of any vertex of the tree. The leaves have height 0. Empty node has height -1.

Depth First Search

1. Pre-order
   • Apply function on root (or current vertex)
   • Traverse left subtree
   • Traverse right subtree
2. In-order
   • Traverse left subtree
   • Apply function on root (or current vertex)
   • Traverse right subtree
3. Post-order
   • Traverse left subtree
   • Traverse right subtree
   • Apply function on root (or current vertex)

Easy with recursion. Or use a stack to simulate recursion. $O(n)$ to traverse the entire tree. Each node is visited at most once.

Breadth-First Search (Level Order Traversal)

BFS starts at the root and visits its adjacent vertices, and then moves to the next level. Use a queue to traverse.

Searching

Recurse left or right depending on less or more respectively to find a key or insertion position.

Insertion

search(x) then place there

Finding Successor

If searching for a key not in the tree. search(x) will find either predecessor or successor.

1. result = search(x)
2. If result > x, return result
3. If result < x, return search(result)
4. If result == x
5. if there is right subtree, return minimum in right subtree.
6. if no right subtree, go up the tree until you find a value > x, then return value

But if x is the maximum value, then this algorithm will simply return the root (which is wrong).

Removing Node

If leaf (no child), just remove.

If only has 1 child, simply replace with child.

If there are 2 children swap it with the successor and then remove the node.

Successor of a node (must be the minimum in the right subtree of node) being deleted must have only 1 child.

This will make sure that BST property is upheld.

$O(height)$

Tree Rotations

Right rotation requires a left child. Left rotation requires a right child.

Rotations always have inverses!

Right rotation:

(not inclusive of checking if valid)
w = v.left
w.parent = v.parent
v.parent = w
v.left = w.right
w.right = v

After an insertion, use tree rotations to re-balance the tree. Maximum of 1 node being out of balanced. So, balance the first unbalanced node.

Left-heavy if left sub-tree has larger height than right sub-tree. Right-heavy if right sub-tree has larger height than left sub-tree.

Inserting into AVL Trees

Check if height-balanced when unrolling recursion (and updating heights).

Rebalance trees using tree rotation.

Steps for inserting into AVL Tree.

1. Insert key in BST.
2. Walk up the tree

• At every step, check for balance.
• If out-of-balance, use rotations to re-balance and return.
  • Only need to fix the lowest out-of-balance node.

Minimum number of rotations after an insertion is 0. Maximum number of rotations after an insertion is 2. This is because inserting increases the height and rotations reduce the height, so they effectively cancel each other out.

Deleting in AVL Trees

1. If v has two children, swap it with its ancestor.
2. Delete node v from binary tree (and reconnect children)
3. Rotate to balance (similarly to insertion BUT have to keep balancing all the way up to the root)

Maximum number of rotations is $O(\log n)$. This is because deleting reduces the height but rotations also reduce the height. Thus, it is not sufficient to only fix lowest out-of-balance node.

Usages

1. Searching strings
2. Sorting/enumerating strings

Partial String Operations

1. Prefix queries
2. Longest prefix
3. Wildcards (pi??le)

Variants

Compressed tries (only unchain the nodes if needed). Using hash table instead of array.

Code

// can also use a null-terminating character as a node to indicate the end (instead of a boolean)
public class Trie {
    static class TrieNode {
        char value;
        boolean isEnd;
        // can replace this array with hash table
        TrieNode[] nextNodes;

        TrieNode(char value, boolean isEnd) {
            this.value = value;
            this.isEnd = isEnd;
            this.nextNodes = new TrieNode[26];
        }
    }

    private final TrieNode root;

    Trie() {
        this.root = new TrieNode('0', false);
    }

    void insert(String word) {
        char[] chars = word.toCharArray();
        int N = chars.length;
        TrieNode node = this.root;
        for (int i = 0; i < N; i++) {
            char c = chars[i];
            if (node.nextNodes[c - 'a'] == null) {
                node.nextNodes[c - 'a'] = new TrieNode(c, false);
            }
            node = node.nextNodes[c - 'a'];
            if (i == N - 1) {
                node.isEnd = true;
            }
        }
    }

    boolean search(String word) {
        TrieNode node = this.root;
        for (char c : word.toCharArray()) {
            if (node.nextNodes[c - 'a'] == null) {
                return false;
            }
            node = node.nextNodes[c - 'a'];
        }
        return node.isEnd;
    }

    boolean startsWith(String word) {
        TrieNode node = this.root;
        for (char c : word.toCharArray()) {
            if (node.nextNodes[c - 'a'] == null) {
                return false;
            }
            node = node.nextNodes[c - 'a'];
        }
        return true;
    }
}

Time Complexity

Theoretically $O(\log n)$ Practically $O(1)$ because of memory access times

Selecting

select(k)

def select(v, k):
  rank = v.left.weight + 1
  if (k == rank):
    return v
  elif k < rank:
    return select(v.left, k)
  else if k > rank:
    return select(v.right, k - rank)

Rank

rank(node)

def rank(node):
  rank = node.left.weight + 1
  while node != null:
    if node is left child:
      do nothing
    elif node is right child:
      rank += node.parent.left.weight (left sibling) + 1
    node = node.parent
  return rank

Interval Search

def interval_search(x):
  c = root
  while (c != null and x is not in c.interval):
    if c.left == null:
      c = c.right
    else if x > c.left.max:
      c = c.right
    else:
      // always search left if left.max > x
      c = c.left
  return c.interval

$O(\log n)$ if balanced

If search goes left, if there is no interval in left subtree, then there is no interval in right subtree either. If search goes right, there is no overlap in left subtree.

Interval Search (all intervals that work)

1. Repeat until no more intervals found
2. Search for interval
3. Add to list
4. Delete interval
5. Repeat for all intervals on list
6. Add interval back to tree

$O(k\log n)$ where k is the number of intervals that work but a faster solution (albeit more complicated) works in $O(k+\log n)$

One Dimensional Range Queries

1. Use a BST
2. Store all the points in the leaves of the tree. (Internal nodes only store copies)
3. Each internal node stores the MAX of any leaf in the left subtree

## find the first node that is bounded within the query
def findSplit(lo, hi):
  v = root
  while true:
    if hi <= v.key:
      v = v.left
    else if low > v.key:
      v = v.right
    else
      break

def query(lo, hi):
  v = findSplit(lo, hi)
  leftTraversal(v, lo, hi)
  rightTraversal(v, lo, hi)

def collect_all_leaf(v):
  collects if its in the range

def leftTraversal(v, lo, hi):
  if lo <= v.key:
    collect_all_leaf(v.right)
    leftTraversal(v.left, lo, hi)
  else:
    leftTraversal(v.right, lo, hi)

def rightTraversal(v, lo, hi):
  if v.key <= hi:
    collect_all_leaf(v.left)
    rightTraversal(v.right, lo, hi)
  else:
    rightTraversal(v.left, lo, hi)

Two Dimensional Range Queries

Can build a x-tree using only x-coordinates For every node in the x-tree, build a y-tree out of nodes in subtree using only y-coordinates.

Query: $O(\log^2 n + k)$

• $O(\log n)$ to find split node
• $O(\log n)$ recursing steps
• $O(\log n)$ y-tree-searches of cost $O(\log n)$
• $O(k)$ enumerating output

Space: $O(n\log n)$

• Each point appears in at most one y-tree per level
• There are $O(\log n)$ levels
• Each node appears in at most $O(\log n)$ y-trees The rest of the x-tree takes $O(n)$ space.

Building: $O(n\log n)$ but not easy

No longer a dynamic data structure because rotations are no longer efficient $O(n)$ thus cannot maintain balance.

n-Dimensional Range Queries

Possible to extend to higher dimensions. BUT have to store a d-1 dimensional range tree in each node of a 1D range tree.

Search

$O(h)$

Construction

Example here for 2D.

Alternate x and y. WLOG, treat as x findMedian using quick select (and remove the coord after selecting it)

1. findMedian(points) based on x
2. Partition around the median
3. Then, recurse on left and right partitions (on y now) and take them as left and right children

$T(n) = 2T(n/2) + O(n)$ $T(n) = (n\log n)$

Minimum/Maximum Coordinates

For minimum x-coordinate. Finding maximum (and the equivalents for y-coordinate) is similar.

1. If leaf node, return itself.
2. If at x-level, search left child.
3. If at y-level, search BOTH left and right children and return the minimum. (because either could bear the minimum x-coordinate)

For a perfectly balanced kd-tree Even: $T(n)=T(n/2)+O(1)$ Odd: $T(n)=2T(n/2)+O(1)$ Overall: $T(n)=2T(n/4)+O(1)$ $T(n)=\sqrt n$

Problems with Direct Access Tables

Treating everything as a number. Longest english word is 28 letters and 5 bits per letter => 140 bits max So, 2^140 size array can store EVERY english words (approx number of atoms in observable universe, so obviously too much space!)

Chaining

If m == n, can still insert but will be less efficient.

n > m is better for enumerating all the keys in a hash table (not normally prioritised) As long as m > n, equally efficient. (unlike open addressing)

Put all the items that collide in the same bucket using a linkedlist of items in that bucket.

Total Space: O(m+n) Table size: O(m) Linkedlist size: O(n)

Linkedlist wander all over the memory (bad for cache access) Needs to keep allocating list nodes into memory

Table Size

Assume hashing with chaining Assume simple uniform hashing Expected search time: O(1 + n/m) Optimal size: $m=\Theta(n)$

if m < 2n: too many collisions if m > 10n: too much wasted space note that: 2 and 10 above are arbitrary

PROBLEM: don't know what is n in advance

IDEA: grow and shrink the table size as necessary (similar to dynamic arrays)

Open Addressing

If m == n, can no longer insert!

Idea: Find another bucket.

Pros

• Saves space
  • Empty slots vs linked lists
• Rarely allocate new memory
  • No linkedlist nodes to allocate
• Better cache performance
  • Table is stored in contiguous memory
  • Fewer accesses to the cache
  • Compare to linkedlist being in different places in the memory

Cons

• More sensitive to choice of hash functions
  • Clustering is a common problem
• Performance degrades badly as $\alpha$ approaches 1
  • Even around a quarter full is already slow

for i in 0..m:
  if buckets[hash(x) + i % m] is empty:
    insert x into this bucket
    break

for i in 0..m:
  if buckets[(hash(x) + i * i) % m] is empty:
    insert x into this bucket
    break

Assuming the key is a N-bit binary value, so x = 2, N = N.

hash = 0
for j in range(N):
  hash = hash XOR T[key[j]][j]

Java Map

Standard is to use HashMap<Key,Value> interface java.util.Map<Key,Value>

• void clear()

• boolean containsKey(Object k)

• boolean containsValue(Object v) // may not be efficient!

• Value get(Object k)

• Value put(Key k, Value v)

• Value remove(Object k)

• int size()

• Set<Map.Entry<Key,Value>> entrySet()

• Set<Key> keySet()

• Collection<Value> values() Above 3 are not sorted and not necessarily efficient

Java Map Rules

• No duplicate keys allowed (checked during insertion)
  • need to search on insertion
• No mutable keys
  • no longer clear which key to use (original vs modified)
• Must redefine equals() method to be consistent
  • Reflexive
  • Symmetric
  • Transitive
  • Consistent
  • Null is null

More Java HashMap Behaviour

• Returns null when key is not in map
• Returns null when value is null

It is implemented with chaining. It will hash the hashCode of your object again to a value that can fit in the internal table! Because of this, table_hash == table_hash does not imply that hash == hash.

TreeMap (dictionary in Java)

• Supports most HashMap operations with MORE operations! (because dictionary is an ordered data structure)

Design decisions

• Allow duplicate keys
  • No: need to search on insertion
  • Yes: faster insertion
• What to do if user inserts duplicate key
  • Override existing key
  • Add new value (key will have 2 values)
  • Error
• Insert empty/null
  • Deletes existing key, value pair
  • Inserts a null
  • Error

Wide Interfaces

Lots of functionality Easy to use No guarantee of efficiency (some operations are not optimised) Java mostly has wide interfaces

Narrow Interfaces

Limited functionality Enforces proper usage Restricts usage

Hash Code Method

Every Object in Java has a hashCode() method By default Java hashCode returns the memory location of the object. Every Object hashes to a different location. Should override this!

Rules:

1. Always returns the same value, if the object has not changed
2. If two objects are equal, then they return the same hash code

• If two objects have the same hash code, they might not be equal

For Integer:

public int hashCode() {
  return value;
}

For Long:

public int hashCode() {
  return (int) (value ^ (value >>> 32))
}

For String:

s[0] * 31^(n-1) +
s[1] * 31^(n-2) +
s[n-1] * 31^(0)

// 31 is just a prime number that happens to work well

Graph Definitions

Multi Graphs: Has more than 1 edge between same pair of nodes

Hyper graphs: Has edges that connect > 2 nodes

Multi graphs and hyper graphs not covered in CS2040S. (both not considered regular graphs for CS2040S).

(Simple) Path: Set of edges connecting 2 nodes, path intersects each node at most once (no repeated nodes).

Connected: Every pair of nodes is connected by a path.

Disconnected: Some pair of nodes not connected by a path.

Connected Components: Set of nodes that are reachable (exists some path) from each other.

Cycle: "Path" where first and last node are the same.

(Unrooted) Tree: Connected graph with no cycles. Tree with N vertices has N - 1 edges.

Forest: Graph with no cycles (>= 1 trees)

Degree of Node: Number of adjacent edges. * can draw example picture

Degree of Graph: Maximum degree of all the nodes.

Diameter: The maximum distance between two nodes, following the shortest path. Only interested in reachable nodes (not defined for unreachable).

Finding diameter:

1. Take every pair of nodes
2. Find shortest path distance between each pair
3. Return longest distance found in step 2

Sparse: Average degree of nodes VS total number of nodes. E = O(V) is sparse

Special Graphs

Star: One central node, all edges connect center to edges. (also a tree) Degree = n - 1 Diameter = 2

Clique (Complete Graph): All pairs are connected by edges. Degree = n - 1 Diameter = 1

Line (or path): Line graph Degree = 2 Diameter = n - 1 Line is also a bipartite graph.

Cycle: Circle Degree = 2 Diameter = n / 2 or (n - 1) / 2 based on odd/even Even length cycle is a bipartite graph. Odd length cycle cannot be a bipartite graph.

Bipartite Graph: Nodes divided into two sets with no edges between nodes in the same set. Maximum Diameter = n - 1 (essentially a Line Graph) To prove bipartite graph: re-arrange/colour into a bipartite graph

A graph does NOT contain an odd length cycle <=> it is a bipartite graph. https://math.stackexchange.com/questions/311665/proof-a-graph-is-bipartite-if-and-only-if-it-contains-no-odd-cycles

Modelling Problems

4-Colouring Problem Nodes: tiles Edges: pairs of adjacent tiles A map in a plane can be coloured using 4 colours such that adjacent tiles sharing a common boundary do not share the same colour.

Sliding Puzzle Every state is a node. Moves = edges

For n = 9 Maximum degree: 4 (maximum possible of moves) Nodes = 9! Edges: 4*9! (4 from maximum degree)

Diameter = scrambled -> unscrambled

Rubik's Cube Every state is a node. Moves = edges

Number of nodes (for 2x2x2 cube) = 7! * 3^8 (7! and not 8! because symmetry rule, fix one of the pieces) ^ upper bound that includes illegal states

For 3x3x3 cube: 43 quintillion vertices (approximately)

Diameter of n x n x n cube: $\Theta(n^2 /\log n)$

Graph Representation

Chosen based on if graph is dense or sparse and what type of queries to be optimised for.

If a graph is dense, then use an adjacency matrix, else use an adjacency list. Dense: |E| = $\Theta(V^2)$

// or LinkedList<Integer>
class NeighbourList extends LinkedList<Node> {}

class Node {
  int key;
  NeighbourList neighbours;
}

class Graph {
  Node[] nodes;
}

// Don't do this:
List<List<Integer>> nodes;
// ^ harder to read, debug, extend

class Graph {
  Node[][] matrix;
  boolean[][] matrix;
  // use boolean if don't care about path lengths
}

Graph Searching

1. Start at s -> end at f
2. Visit all nodes in the graph

Only visit every node once!

BFS/DFS visits every node and edge in the graph, but NOT every path in the graph.

Visiting every possible path is exponential (an undirected graph), so we clearly don't want to do this unless there is no other better choice (which there IS).

DON'T modify BFS/DFS to backtrack/re-visit, probably will be end up being exponential or infinite loops.

BFS/DFS forms a tree/forest (depends on number of connected components).

For a connected graph, this is because n - 1 new nodes will be discovered from the source node. With each discovery, the parent pointer is an edge. The final structure will thus consist of n nodes and n - 1 edges and will form one connected component. Thus, it is a tree by definition of a tree.

// need to restart for nodes not visited (if not connected)

BFS(Node[] nodeList, int startId) {
  // keep track of visited nodes
  boolean[] visited = new boolean[nodeList.length];
  // even though Java boolean[] default is already false
  Arrays.fill(visited, false);

  int[] parent = new int[nodeList.length];
  Arrays.fill(parent, -1);

  Collection<Integer> frontier = new Collection<>();
  frontier.add(startId);

  while (!frontier.isEmpty()) {
    // can reuse same queue if using queue (just keep track of number of nodes in a level)
    Collection<Integer> nextFrontier = new Collection<>();
    for (Integer v : frontier) {
      // do things to v here
      for (Integer w : nodeList[v].neighbours) {
        if (!visited[w]) {
          // only visit each node once
          visited[w] = true;
          parent[w] = v;
          nextFrontier.add(w);
        }
      }
    }
    frontier = nextFrontier;
  }
}

DFS_visit(Node[] nodeList, boolean[] visisted, int startId) {
  for (Integer v : nodeList[startId].neighbours) {
    if (!visited[v]) {
      visited[v] = true;
      DFS_visit(nodeList, visited, v);
    }
  }
}

DFS(Node[] nodeList) {
  boolean[] visited = new boolean[nodeList.length];
  Arrays.fill(visited, false);

  for (int start = 0; start < nodeList.length; start++) {
    if (!visisted[start]) {
      visisted[start] = true;
      DFS_visit(nodeList, visisted, start);
    }
  }
}

Adjacency List

Exactly the same but only store outgoing edges in linked list

Adjacency Matrix

Exactly the same but no longer symmetrical matrix

BFS

Follow outgoing edges Ignore incoming edges

DFS

Follow outgoing edges Backtrack (through incoming edges) when unrolling recursion

DFS for Topological Ordering

Can use post-order DFS to find Topological Ordering. Process each node when it is last visited and put it at the BACK of the ordering. Also, need to start the DFS multiple times because we don't know wheres the actual start(s).

for (int start = 0; start < nodeList.length; start++) {
  if (!visisted[start]) {
    visisted[start] = true;
    DFS_visit(nodeList, visisted, start);
    // post-order
    add to end of ordering
  }
}

O(V + E) time complexity because its just a DFS with an extra O(1) on each node

Reverse of post-order DFS.

Kahn's Algorithm for Topological Ordering

Kahn's Algorithm is a form of BFS. A bit more difficult to implement than DFS.

Repeat:

1. S = all nodes in G that have no incoming edges
2. Add nodes in S to the topological ordering
3. Remove all edges adjacent to nodes in S
4. Remove nodes in S from the graph

O(V + E) time complexity

Strongly Connected Components

For every vertex v and w in the component:

1. There is a path from v to w.
2. There is a path from w to v.

A single node is trivially a strongly connected component.

Cycles are strongly connected components.

Graph of multiple strongly connected components is acyclic if connecting the strongly connected components in a non-cyclic way.

DAG has no cycles and hence there are no (u, v) in the same strongly connected component. Thus, the DAG will have n strongly connected components.

DAG: Directed Acyclic Graph

Bellman-Ford Algorithm

n = V.length;
for (i = 0; i < n; i++) {
  if during an iteration, all the relax does nothing, then terminate early
  for (Edge e : graph) {
    relax(e);
  }
}

If relax every edge in the graph (n - 1) times, will have correct final answer. Can terminate early if an entire sequence of relax has no effect. n - 1 times because the longest path is n - 1 edges (if no negative weight cycle)

If P is the shortest path from S to D, and if P goes through X, then P is also the shortest path from S to X (and from X to D). After i iteration of Bellman-Ford, i hop estimate (i hops) on shortest path is correct. After 1 iteration of Bellman-Ford, NOT ALL nodes 1 hop away from source is correct (only the one along the shortest path is guaranteed)!

Thus, by induction, after n iterations, shortest path reaches the destination.

Time complexity: O(E * V) in the worst case but can terminate early!

Dijkstra Algorithm

public Dijkstra {
  private Graph g;
  private IPriorityQueue pq = new PriorityQueue();
  private double[] distTo;

  void searchPath(int start) {
    pq.insert(start, 0.0);
    distTo = new double[G.size()];
    Arrays.fill(distTo, INFINITY);
    distTo[start] = 0;
    while (!pq.isEmpty()) {
      int w = pq.deleteMin();
      for (Edge e : G[w].neighbours) {
        // this loop is ran <= V times
        // but since each edge is relaxed only once
        relax(e);
      }
    }
  }

  // relax is O(log V)
  void relax(Edge e) {
    int v = e.from();
    int w = e.to();
    double weight = e.weight();
    if (distTo[w] > distTo[v] + weight) {
      distTo[w] = distTo[v] + weight;
      parent[w] = v;
      if (pq.contains(w)) {
        pq.decreaseKey(w, distTo[w]);
      } else {
        pq.insert(w, distTo[w]);
      }
    }
  }
}

Array Representation of Heap Tree

For minimum heap tree: For an array of indices [1, 2, ..., n]

• root: $i$
• left child at $2i$
• right child at $2i+1$
• parent at $\lfloor i/2\rfloor$

Full Binary Tree

1. Every level of the tree must be full.

In array representation: heap has array of $2^n$ items, every item in this array is filled (no spaces). Use resizeable array if heap is resizable too.

Every full binary tree is also a complete binary tree.

Complete Binary Tree

1. Every level of the tree must be full except possibly the leaves.
2. Leaf nodes are as far left as possible.

In array representation: heap has array of $x$ items, every item in this array is filled (no gaps in the array).

Maximum Heap Tree

1. Value at root node is greater than or equal to both its children (local property, does not apply to "nephews").
2. The heap tree is a complete binary tree.

Operations have to maintain the complete binary tree property.

Claim: For heap with unique values, second largest element must be a child of the root node. Proof: Suppose it is not, then there is a contradiction because that means there exists a node > second largest yet < largest.

Height is $\lfloor \log n\rfloor$ because complete binary tree

Minimum Heap Tree is the same except it is "lesser than or equal to" instead.

bubbleUp(Node u):
  // root = no parent = no violation
  while u is not the root:
    if (u.priority > u.parent.priority) {
      swap(u, u.parent)
    }
    u = u.parent

bubbleDown(Node u):
  // leaf = no children = no violation
  while u is not a leaf:
    maxP = max(u.left.priority, u.right.priority)
    if (maxP > u.priority) {
      // choose larger side to bubble down to
      if (maxP == u.left.priority) {
        swap(u, u.left)
        u = u.left
      } else if (maxP == u.right.priority) {
        swap(u, u.right)
        u = u.right
      }
    }

Shortest Path on DAG

1. Topological order
2. Relax edges in any order

Topological ordering because when reach any node, all nodes pointing into it definitely has the correct distance (because topologically before this node).

Time complexity (assuming adjacency list) Finding topological ordering: O(V + E) Relaxing E edges: O(E) Overall: O(V + E)

Longest Path on DAG

Negate all the edges to reduce this problem to be a Shortest Path on DAG problem

For a cyclic graph, CANNOT do this negation trick because it leads to negative weight cycles and everything breaks.

In general, finding longest path on a general graph is a NP-hard problem (no polynomial solution).

Logarithm Trick to Avoid Multiplication

In general, modifying graph/input is better than modifying the algorithm because modifying algorithms could easily introduce bugs or change time complexities.

$\log(a_1*a_2* \cdots *a_n)=\log a_1+\log a_2+\cdots +\log a_n$ $\log(\frac{1}{a_1*a_2* \cdots *a_n})=-\log(a_1*a_2* \cdots *a_n)=-\log a_1+-\log a_2+\cdots +-\log a_n$

Note that 0 < x < 1, then $-\log x$ > 0. So, can use Dijkstra.

Is Connected?

Naive Version (without wall breaking and static set) isConnected: return true if A and B are in the same connected component Preprocess: Identify connected components. Label each location with its component number

Dynamic Connectivity

Given a set of objects: union(): connect two objects find(): is there a path connecting 2 objects?

Quick-Find Algorithm

Optimised for quick finding

If objects are not integers, convert them to integers.

1. Hash function (if collision don't matter)

• UUID generator

2. Hash table + open addressing (if collisions matter)

Data Structure int[] componentId Two objects are connected if they have the same component identifier.

Essentially very flat trees (tree with height of max 2) Same component => in the same subtree Can model the above int array as a flat tree.

find(int p, int q):
  // O(1)
  return componentId[p] == componentId[q]

// O(n) because need to search through ALL objects
union(int p, int q):
  // choose either to be the new id
  updateComponent = componentId[q]
  for (int i = 0; i < componentId.length; i++) {
    if (componentId[i] == updateComponent) {
      componentId[i] = componentId[p];
    }
  }

Quick-Union Algorithm

int[] parent (parent pointers) Two objects are connected if they are part of the same tree

These non-binary trees will not be balanced.

find(int p, int q) {
  // O(n) if a very tall tree (all objects in same component)
  while (parent[p] != p) p = parent[p];
  while (parent[q] != q) q = parent[q];
  return root of p == root of q;
}

union(int p, int q) {
  // O(n) if a very tall tree (all objects in same component)
  while (parent[p] != p) p = parent[p];
  while (parent[q] != q) q = parent[q];
  // pick either node to be the parent
  parent[p] = parent[q];
}

This version is very bad because trees are tall (unbalanced).

Need to compress the tree to achieve fast union!

union(int p, int q) {
  while (parent[p] != p) p = parent[p];
  while (parent[q] != q) q = parent[q];
  // pick taller tree to be the root
  if (size[p] > size[q]) {
    // p is taller
    parent[q] = parent[p];
    size[p] = size[p] + size[q];
  } else {
    // q is taller
    parent[p] = parent[q];
    size[q] = size[p] + size[q];
  }
}

findRoot(int p) {
  root = p
  while (parent[root] != root) root = parent[root]
  while (parent[p] != p) {
    temp = parent[p]
    parent[p] = root
    p = temp
  }
  return root
}

// alternative: point each node to their grandparent instead
findRoot(int p) {
  root = p
  while (parent[root] != root) {
    // pointing everything to their grandparent achieves the same effect as directly pointing to the root
    root = parent[root]
    parent[root] = parent[parent[root]]
  }
  return root
}

Union-Find Summary

Weighted Union is faster:

1. Trees are flat: O(log n)
2. Union and find are both O(log n)

Weighted Union + Path Compression very fast:

1. Trees very flat
2. On average, almost linear performance per operation

Applications

1. Maze solving
2. Game states
3. Network connections
4. Lowest Common Ancestors (LCA)
5. Finite state automata
6. Image processing in Matlab
7. Physics

Union-Split-Find Insert and delete edges. Very difficult problem.

Applications for MST

• Network design problems
  • Telephone networks
  • Electrical networks
  • Computer networks
  • Road networks
  • etc

Minimum cost network to stream a movie to all the users.

Properties of MST

A cut of a graph G = (V, E) is a partition of the vertices V into two disjoint subsets. An edge crosses a cut if it has one vertex in each of the two sets.

1. MSTs have no cycles (it is a tree).
2. When cutting a MST into 2 pieces, they will become 2 MSTs for their connected components.
3. Cycle property

• for every cycle, the maximum weight edge is not in the MST.
• proof by contradiction:
  • if it is in the MST, add another edge in the cycle into the MST
  • then, there is a cycle
  • thus, we need to remove an edge
  • so we'll remove the heavier edge
  • thus, maximum weight edge is not in the MST
• BUT for every cycle, the minimum weight edge may or may not be in the MST because the lightest edge in one cycle can be the heaviest edge in another cycle.

4. Cut property

• For every cut/partition of the nodes, the minimum weight edge across the cut is in the MST.
• proof by contradiction
• if it is not, add minimum weight edge on cut
• then, there is a cycle
• thus, we need to remove the heaviest edge on cycle
• so the minimum weight edge on cut will be left

For every node, the minimum outgoing edge is always part of the MST. (this is because of the cut property, cut the one node away from the rest of the graph) For every node, the maximum outgoing edge can be part of the MST (if there is only 1 outgoing edge).

Generic MST Algorithm

Red rule (based on cycle property): If C is a cycle with no red arcs, then colour the max-weight edge in C red. Blue rule (based on cut property): If D is a cut with no blue arcs, then colour the minimum-weight edge in D blue.

Greedily apply red rule and blue rule to an arbitrary edges until no more edges can be coloured.

On termination: The blue edges are an MST.

1. Every cycle has a red edge. No blue cycles => forest of blue edges
2. Blue edges form a tree => spanning tree

• if not, there is a cut with no blue edge

3. Every edge is coloured
4. Every blue edge is in the MST (because of cut property)

This generic MST algorithm is the basis of ALL MST algorithms.

Note: If all edges have different costs, there is a unique MST. https://math.stackexchange.com/questions/352163/show-that-theres-a-unique-minimum-spanning-tree-if-all-edges-have-different-cos

A divide-and-conquer implementation of this does not work because converse of cut property is not true!

BUT divide-and-conquer along the median does work.

Prim's Algorithm

Basic Idea: Identify cuts and keep growing the set S. Fairly similar to Dijkstra's Algorithm's idea with some small changes that completely change the outcome!

S: set of nodes connected by blue edges, initially, some random starting node Next, add the minimum weight edge on cut from S to the rest of the nodes (cut property) and relax the edges. Repeat this until all nodes are added into S.

Use a priority queue to find the minimum weight edge on cut. In this case, priority queue is used to store nodes and not edges.

// pq stores nodes
pq = new PQ();
for (Node v : G.V()) {
  pq.insert(v, infinity);
}
pq.decreaseKey(start, 0);

HashSet<Node> S = new HashSet<Node>();
S.put(start);

HashMap<Node,Node> parent = new HashMap<Node, Node>();
parent.put(start, null);

while (!pq.isEmpty()) {
  Node src = pq.deleteMin();
  S.put(src);
  for (Edge e : v.edgeList()) {
    Node dest = e.otherNode(src);
    if (!S.contains(dest)) {
      // assume decreaseKey does nothing if weight is > original
      double weight = e.getWeight();
      pq.decreaseKey(dest, weight);
      if (weight < currentWeight of dest) {
        parent.put(dest, src);
      }
    }
  }
}

Proof:

1. Each added edge is the lightest on some cut.
2. Hence each edge is in the MST.

Time complexity of using a AVL Tree for PQ: O(E log V) because each vertex added/removed once from the priority queue -> O(V log V) each edge, <= 1 decreaseKey -> O(E log V) E >= V because connected -> O(E log V)

with fibonacci heap O(V) -> insert all nodes at the start (fibonacci heap is of size O(V)) O(E) -> decreaseKey called for each edge O(V log V) -> extractMin for each node O(V log V + E)

Kruskal's Algorithm

Basic Idea:

• Sort edges by weight from smallest to biggest
• consider edges in ascending order:
  • if both endpoints are in the same blue tree, then colour the edge red (must be the heaviest edge on the cycle, because doing this algorithm in sorted weight order)
  • otherwise, colour the edge blue

Can terminate early once V - 1 edges are obtained

Use Union-Find data structure. Connect two nodes if they are in the same blue-tree.

// sort edges
Edge[] sortedEdges = sort(G.E());
ArrayList<Edge> mstEdges = new ArrayList<Edge>();
UnionFind uf = new UnionFind(G.V());

for (int i = 0; i < sortedEdges.length; i++) {
  Edge e = sortedEdges[i];
  Node src = e.first();
  Node dest = e.second();
  if (!uf.find(src, dest)) {
    mstEdges.add(e);
    uf.union(src, dest);
  }
}

Proof:

1. Each added edge crosses a cut
2. Each edge is the lightest edge across the cut (all other lighter edges across the cut have already been considered because sorted)

Time complexity on a connected graph: O(E log E) or O(E log V) because sorting edges -> O(E log E) = O(E log V) because O(E) = O(V) for E edges: Find and (sometimes) Union -> O(E $\alpha$(E))

Boruvka's Algorithm

Basic Idea: Add all "obvious" blue edges Parallelisable MST algorithm.

For every node: add minimum adjacent edge (at least n/2 edges added, at most n/2 connected components)

Repeat: for every connected component, add minimum outgoing edge

Initially, n connected components, one for each node

Each iteration:

1. For each connected component, search for the minimum weight outgoing edge
2. Add selected edges
3. Merge connected components

At most O(log V) iterations. Each iteration costs O(E+ V) = O(E) Thus, overall O(E log V)

MST Variants

Directed MST

No root don't make sense. A rooted spanning tree: every node is reachable from the root.

Prim's, Kruskal's, Boruvka's do not work for minimum rooted spanning tree because cut property and cycle property do not work.

VERY hard problem (not covered in CS2040S)

Re-Weighing Edges

By adding/subtract all edges by some constant k, the MST does not change. Only relative weights of edges matter. Not the absolute edge weights.

Maximum Spanning Trees

MST with negative weights have no problem! So, just multiply each edge by -1 and run Minimum Spanning Tree algorithm and take the most negative.

OR run Kruskal's Algorithm in reverse (start from largest edge weight to smallest)

Smallest Maximum Edge

https://cs.stackexchange.com/questions/4942/finding-paths-with-smallest-maximum-edge-weight

1. Get MST
2. BFS/DFS from A to B to find a path (it will definitely have the smallest maximum edge)

Optimal Sub-Substructure

Optimal solution can be constructed from optimal solutions to smaller sub-problems.

It is a property of many problems. Greedy (Dijkstra's and MST) and divide-and-conquer (merge sort, Fast Fourier Transform).

Overlapping subproblems The same smaller problem is used to solve multiple different bigger problems. Divide and conquer problems do not have overlapping subproblems.

Basic Ideas

DP Problems

// assuming V is already topo sorted
LIS(V):
  // memo array
  int[] S = new int[V.length];
  for (i = 0; i < V.length; i++)
    S[i] = 0;
  S[n-1] = 1;
  for (int v = A.length - 2; v >= 0; v--) {
    // find maximum S for any outgoing edge
    int max = 0;
    for (Node w : v.neighbours) {
      if (S[w] > max) {
        max = S[w];
      }
    }
    S[v] = max + 1;
  }

static int lengthOfLIS (int[] nums) {
  int[] dp = new int[nums.length];
  dp[0] = 1;
  for (int i = 1; i < nums.length; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j ++) {
      if (nums[j] < nums[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  int res = 0;
  for (int x : dp) res = Math.max(res, x);
  return res;
}

int LazyPrizeCollecting(V, E, kMax) {
  int[][] P = new int[V.length][kMax+1];
  for (int i = 0; i < V.length; i++)
    for (int j = 0; j < kMax + 1; j++)
      P[i][j] = 0;
  for (int k = 1; k < kMax + 1; k++) {
    for (int v = 0; v < V.length; v++) {
      int max = -INFINITY;
      // find max prize in next step
      for (int w : V[v].neighbours) {
        if (P[w, k-1] + E[v, w] > max) {
          max = P[w, k-1] + E[v, w];
        }
      }
      P[v, k] = max;
    }
  }
  return maxEntry(P);
}

int treeVertexCover(V) {
  int[][] S = new int[V.length][2];
  for (int v = V.length - 1; v >= 0; --) {
    // start from leaves
    if (v.children.size() == 0) {
      // v is leaf
      S[v][0] = 0;
      S[v][1] = 1;
    } else {
      S[v][0] = 0;
      S[v][1] = 1;
      for (int w : V[v].children) {
        S[v][0] += S[w][1];
        S[v][1] += Math.min(S[w][0], S[w][1]);
      }
    }
  }
  // return min at root
  return Math.min(S[0][0], S[0][1]);
}

Naive Solution

For positive weights only Run Dijkstra's Algorithm on every query and memoize. Preprocessing: 0 Responding to q queries: O(VE * log V) sparse graph: $O(V^2logV)$

For identical weights, O(V(E + V)) + O(VE) in dense graph: $O(V^3)$ in sparse graph: $O(V^2)$

Preprocessing Solution

Preprocessing: all-pairs-shortest-path Responding to q queries: O(q)

There are also some versions that sacrifice some response time for faster preprocessing.

let S[v, w, P] be the shortest path from v to w that only uses intermediate nodes in the set P.

Floyd-Warshall

Limit ourselves to V+1 different sets P (out of $2^V$)

P0 = {} P1 = {1} P2 = {1, 2} ... $P_n$ = {1, 2, ..., n}

Either use or don't use a node S[v, w, $P_8$] = min(S[v, w, $P_7$], S[v, 8, $P_7$] + S[8, w, $P_7$]) S[v, w, $P_{i+1}$] = min(S[v, w, $P_i$], S[v, i+1, $P_i$] + S[i+1, w, $P_i$])

In the end, you find the path using with $P_n$ which allows you to use ALL intermediate nodes.

int[][] APSP(E) {
  // 3D matrix is unnecessary (only the previous set is used), thus only need a 2D matrix
  int[][] S = new int[V.length][V.length];
  for (int v = 0; v < V.length; v++) {
    for (int w = 0; w < V.length; w+) {
      // initialise with original weights
      S[v][w] = E[v][w];
    }
  }

  // for sets P0, P1, ...
  for (int k = 0; k < V.length; k++) {
    // for every pair of nodes
    for (int v = 0; v < V.length; v++) {
      for (int w = 0; w < V.length; w++) {
        // either use or don't use the node
        S[v][w] = Math.min(S[v][w], S[v][k] + S[k][w]);
      }
    }
  }
  return S;
}