Java

Access Modifier

C: Class; P: Package; SC: Subclass; W: World

Modifier C P SC W
public Y Y Y Y
protected Y Y Y N
none Y Y N N
private Y N N N

Comparable

Implement Comparable<T>:

int compareTo(T o)

hashCode

int hashCode() {}
boolean equals(Object o) {}

Common Issues

Array out of bounds; divide by zero; infinite loop; exception thrown but not caught; access member variable in static method

Algorithmic Analysis

Amortized Cost
Algo has amortized cost \(T(n)\) if ∀ k ∈ \mathbb{Z}, cost of k operations is \(\leq kT(n)\)

Master’s Theorem

\(T(n) = aT(\frac{n}{b}) + f(n)\) where a ≥ 1, b > 1

Common Ones

Abstract Data Types

Bag
Insert(i); Draw()
Stack (LIFO)
empty(); peek(); pop(); push(i)
Queue (FIFO)
add(); offer(i); peek(); poll(); remove()
Dequeue
double-ended queue

Searching

int binarySearch(int[] arr, int key) {
    int start = 0, end = arr.length - 1;
    int found = -1;
    while(start <= end) {
        int mid = start + (end - start)/2;
        if(arr[mid] < key) {
            start = mid + 1;
        } else if(arr[mid] > key) {
            end = mid - 1;
        } else {
            found = mid;
            // if we want first instance
            end = mid - 1;
            // if we want last instance
            // start = mid + 1;
        }
    }
    return found;
}
One sided Binary Search
Suppose one side is bounded, eg [1, ∞). Use the sequence [1,2,4,8,16…, \(2^k\)…] If it works for \(2^k\), then search on [\(2^{k-1}, 2^k\)]
Peak Finding
A[j] in array A is peak if (i) A[j] > Aj-1 A[j] > A[j+1]. If only one item in array, vacously true
1D Peak Finding \(O(\log n)\)
D&C
if a[n/2] < a[n/2-1] look at 1..n/2-1
else if a[n/2] < a[n/2+1] look at n/2+1..n
else return a[n/2]
2D Peak Finding \(O(m + n)\)
D&C
find max in border + cross O(m+n)
if max is peak return
else go into quadrant with higher number

Sorting

Bubble Sort
Stable, In-place, W&A \(O(n^2)\), B \(O(n)\), S \(O(1)\); Invariant : At iteration i , the sub-array A[1 .. i] is sorted and any element in A[i + 1 .. A . size] is greater or equal to any element in A[1 .. i]
Selection Sort
In-Place, Unstable; find minimum element and swap. W,A,B \(O(n^2)\), S \(O(n/1)\); Invariant: a[0…i-1] is sorted all entries in a[i..n-1] are larger than or equal to the entries in a[0..i-1]
Insertion Sort
In-place, Stable; W \(O(n^2)\), B \(O(n \log n)\), S \(O(n)\); Invariant: The subarray a[i] consists of the original elements in sorted order.
Merge Sort
Stable, In Place; W/B \(O(n\log n)\), S \(O(n)\)
Quick Sort
In-place, Unstable; W \(O(n^2)\), A/B \(O(n\log n)\) S \(O(\log n)\)

Geometric Algorithms

Jarvis March \(O(hn)\)

  1. Find somewhere to start, e.g. y-min coordinate
  2. Add point with maximum angle from horizon \(O(n)\)
  3. Keep adding points with maximum angle from previous

Line Intersection Algorithm \(O(n\log n)\)

  1. Divide into two equal size sets (along vertical line)
  2. Recursively find convex hulls (base case 3 points)
  3. Merge convex hulls
    1. Find upper tangent lines
      1. while \((u,v,w)\) clockwise, decrement \(v\)
      2. while \((v,w,z)\) clockwise, increment \(w\)
    2. Find lower tangent lines
      1. while \((w,v,u)\) clockwise, increment \(v\)
      2. while \((z,v,u)\) clockwise, decrement \(w\)

Quick Hull \(O(n \log n)\)

  1. Choose pivot, construct two subproblems, delete interior points
  2. recurse on subproblems

Trees

Binary Trees (height h)

\(h(v) = max\left(h(v.left), h(v.right)\right) + 1\)

AVL Trees (height \(h = \log n\))

Augmented Trees

Rank Tree (Order Statistics)

rank = left.weight + 1;
  if (k == rank)
    return v
  else if (k < rank)
    return left.select(k)
  else return right.select(k-rank)
rank = v.left.weight + 1
  while (v != null) do
    if v is left child do nothing
    if v is right child,
       rank += v.parent.left.weight + 1
    v = v.parent

Interval Trees

if x in c
  return c
else if c has no left child
  search in right subtree
else if x > max endpoint in c.left
  search in right subtree
else search in left subtree
search(x)
store it somewhere else
remove interval
repeat until no intervals found

Orthogonal Range Searching

Custom Augmentations

Hash Tables

Hash Functions

Division

Multiplication

Rolling Hash

Chaining

Open Addressing

Cuckoo Hashing

Table resizing

Fingerprint Hash Table (FHT)

Bloom Filter

Graphs

Type Space v,w any all
List \(O(V+E)\) slow fast fast
Mat \(O(V^2)\) fast slow slow

BFS \(O(V+E)\)

bfs(root)
  Q.enqueue(root)

  while Q is not empty:
    current = Q.dequeue()
    visit(current)
    for each node n adj to current
      if n not visited
        n.parent = current
        Q.enqueue(n)

DFS \(O(V+E)\)

Topological Sort (DAG)

SSSP

Bellman-Ford \(O(EV)\)

do V number of times
  for (Edge e : graph)
    relax(e)

Dijkstra \(O(E\log V)\)

Interesting article on how Dijkstra’s algorithm is everywhere

add start to PQ
dist[i] = INF for all i
dist[start] = 0
while PQ not empty
  w = pq.dequeue()
  for each edge e connected to w
    if edge is improvement
      update pq[w] O(logn)
      update dist[w]

DAG

Heap

Heap Sort

  1. Heapify (insert n items) O(n log n)
  2. Extract from heap n times (O(n log n))

  3. Improvement: recursively join 2 heaps and bubble root down (base case single node) O(n)

  4. O(n log n) worst case, deterministic, in-place

UFDS (weighted)

MST

Properties

  1. Cutting edge in MST results in 2 MSTs
  2. Cycle Poperty: \(\forall\) cycle, max weight edge is not in MST
  3. Cut Property: \(\forall\) partitions, min weight edge across cut is in MST

Prim’s \(O(E \log V)\)

T = {start}
enqueue start's edges in PQ
while PQ not empty
  e = PQ.dequeue()
  if (vertex v linked with e not in T)
    T = T U {v, e}
  else
    ignore edge
MST = T

Kruskal’s \(O(E\log V)\)

Sort E edges by increasing weight
T = {}
for (i = 0; i < edgeList.length; i++)
  if adding e = edgelist[i] does
  not form a cycle
    add e to T
    else ignore e
MST = T

Boruvka’s \(O(E\log V)\)

T = { one-vertex trees }
While T has more than one component:
 For each component C of T:
   Begin with an empty set of edges S
   For each vertex v in C:
     Find the cheapest edge from v
     to a vertex outside of C, and
     add it to S
   Add the cheapest edge in S to T
 Combine trees connected by edges
MST = T

Variants

  1. Same weight: BFS/DFS \(O(E)\)
  2. Edges have weight \(1..k\):
    • Kruskal’s
      • Bucket sort Edges \(O(E)\)
      • Union/check \(O(\alpha (V))\)
      • Total cost: \(O(\alpha(V)E)\)
    • Prim’s
      • Use array of size k as PQ, each slot holds linked list of nodes
    • insert/remove nodes \(O(V)\)
    • decreaseKey \(O(E)\)
  3. Directed MST
    • \(\forall\) node except root, add minimum incoming edge \(O(E)\)
  4. MaxST
    • negate all weights, run MST algo

MST Problems

Floyd-Warshall (APSP)

// precondition: A[i][j] contains weight
//  of edge (i,j) or inf if no edge
int[][] APSP(A) {
  // len = # vertices
  // clone A into S
  for(int k = 0; k < len; k++)
      for(int i = 0; i < len; i++)
          for(int j = 0; j < len; j++)
              S[i][j] =
                  Math.min(S[i][j],
                           S[i][k] + S[k][j]);
  return S;
}

Network Flow

k-edge connected
Source and target are k-edge connected if there are k edge disjoint paths(don’t share edges) from source to target.
Max flow
st-cut property with minimum capacity(outgoing from s, ignore incoming to s)
Min cut
Let \(S\) be the nodes reachable from the source in the residual graph. \(T\) = all other nodes, S → T is minimum cut
Augmenting Path
path in residual graph from s to t that has no 0 weight edges

Ford-Fulkerson

  1. Start with 0 flow
  2. While there exists augmenting path:
    • find an augmenting path
    • compute bottleneck (min edge)
    • increase flow on the path by bottleneck capacity

Time Complexity:

Graph Algorithms on Trees

Check if connected graph is tree

Run DFS, stop when after traversing \(V-1\) edges, return true if all nodes connected and no other used edge. False otherwise. \(O(V)\)

Min Vertex Cover

int MVC(int v, int flag) {
    int ans = 0;
    if (memo[v][flag] != -1)
        return memo[v][flag];
    else if (leaf[v]) //if v is leaf
        ans = flag;
    else if (flag == 0) {
        ans = 0;
        for(child : adjList[v]) {
            ans+= MVC(child, 1);
        }
    }
    else if (flag == 1) {
        for (child : adjList[v]) {
            ans += min(MVC(child,1),
                       MVC(child,0));
        }
    }
}

SSSP

ASSP

Diameter

Graph Modelling Techniques

  1. minimum shortest path from many source to one destination: run SSSP treating destination as source.
  2. multiple sources to multiple destinations: consider super source and super sink, with edge weight 0, and run Dijkstra (if no negative edge weights), BF otherwise.
  3. Attempt to convert graph into a DAG and use DP techniques. Example: attaching a variable to a vertex that is monotonically decreasing
  4. Shortest path between X and Y that passes through node \(A\): Compute two shortest paths; X to A, A to Y, and join the paths.

Parallel Algorithms

Parallel Fibonacci

parallelFib(n) {
  if(n < 2) then
  return n;
  x = spawn parallelFib(n - 1);
  y = spawn parallelFib(n - 2);
  sync;
  return x + y;
}

Matrix Addition

Before: • Work analysis: \(T_1(n) = O(n^2)\) • critical path analysis: \(T_\infty(n) = O(n^2)\) After:

pMatAdd(A,B,C,i,j,n)
  if(n == 1)
    C[i,j] = A[i,j] + B[i,j];
  else:
    spawn pMatAdd(A,B,C,i,j,n/2);
    spawn pMatAdd(A,B,C,i,j + n/2,n/2);
    spawn pMatAdd(A,B,C,i + n/2,j,n/2);
    spawn pMatAdd(A,B,C,i + n/2,j + n/2,n/2);
    sync;

Parallelized Merge Sort \(O(\log^3n)\)

pMerge(A[1..k], B[1..m], C[1..n])
  if (m > k) then pMerge(B, A, C);
  else if (n==1) then C[1] = A[1];
  else if (k==1) and (m==1) then
    if (A[1] <= B[1]) then
      C[1] = A[1]; C[2] = B[1];
    else
      C[1] = B[1]; C[2] = A[1];
  else
    // binary search for j where
    // B[j] <= A[k/2] <= B[j+1]
    spawn pMerge(A[1..k/2],
                 B[1..j],
                 C[1..k/2+j])
    spawn pMerge(A[k/2+1..l],
                 B[j+1..m],
                 C[k/2+j+1..n])
    synch;

pMergeSort(A, n)
  if (n=1) then return;
  else
    X = spawn pMergeSort(A[1..n/2], n/2)
    Y = spawn pMergeSort(A[n/2+1, n], n/2)
    synch;
    A = spawn pMerge(X, Y);