Algorithm

In this section, ∃ c_1,c2,n0 means there exists positive constants c₁, c₂, and n₀.

• \(\Theta (g(n))\): "big-theta" of g of n, both lower bound and upper bound, asymptotically tight bound
• O: big-o (most often used), upper bound, asymptotic upper bound
• \(\Omega\): big omega, lower bound, asymptotic lower bound
• o: little-o, not tight upper bound
• \(\omega\): little omega, not tight lower bound

Formally:

• \(\Theta(g(n)) = {f(n) : \exists c_1, c_2, n_0 \text{ such that } 0 \le c_1 g(n) \le f(n) \le c_2 g(n) \text{ for all } n \ge n_0}\)
• O(g(n)) = {f(n): ∃ c and n₀ such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n₀}
• Ω(g(n)) = {f(n): ∃ c and n₀ such that 0 ≤ c g(n) ≤ f(n) for all n ≥ n₀}
• o(g(n)) = {f(n): ∃ c and n₀ such that 0 ≤ f(n) < c g(n) for all n ≥ n₀}
• ω(g(n)) = {f(n): ∃ c and n₀ such that 0 ≤ c g(n) < f(n) for all n ≥ n₀}

Go through the array n items. Each time, swap two adjacent items a and b if a>b. Each loop, the largest one go to the end, the smaller ones bubbles up.

for i in range(n):
  for j in range(n-i):
    if A[j] > A[j+1]:
      swap(A[j], A[j+1])

Each loop, make sure the first i items are sorted. In the i-th loop, insert the i-th item into the correct position.

for i in 1 to A.length:
  key = A[i]
  j = i-1
  while A[j] > key:
    A[j+1] = A[j]
    j--
  A[j]=key

Uses divide-and-conquer, recursively solve the left and right subarray, and merge the two sorted arrays (in linear time).

def sort(A, p, r):
  if p < r:
    q = (p + r) / 2
    sort(A, p, q)
    sort(A, q, r)
    merge(A, p, q, r)

def merge(A, p, q, r):
  n = q-r+1
  L = A[p:q]
  R = A[q:r]
  l = r = 0
  for i in range(n):
    if L[l] < R[r]:
      A[i] = L[l]
      l++
    else:
      A[i] = R[r]
      r++

Binary heap is a nearly complete binary tree, i.e. completely filled on all levels except possibly the lowest, which is filled from left up to a point. It can be either max-heap or min-heap, with the max and min on top of heap respectively.

Some helper routines:

def parent(i):
  return floor(i/2)
def left(i):
  return 2*i
def right(i):
  return 2*i+1

Assuming the trees rooted at left(i) and right(i) are max-heaps, but A[i] is not. Float down A[i] so that the tree rooted at i is max-heap.

def max_heapify(A, i):
  l = left(i)
  r = right(i)
  # TODO check l,r < A.heap_size
  value, index = max(A[i], A[l], A[r])
  if index != i:
    swap(A[i], A[index])
    max_heapify(A, index)

Build a heap from an array:

def build_max_heap(A):
  for i in range(len(A), 1, -1):
    max_heapify(A, i)

Finally heap sort: in each loop, remove the top (current max item), replace it with the last element in the heap, and do heapify.

def heapsort(A):
  build_max_heap(A)
  for i in range(len(A), 2, -1):
    swap(A[1], A[i])
    A.heap_size--
    max_heapify(A, 1)

The worst running time is \(\Theta(n^2)\), but it is often the best practical choice for sorting, because it has average running time of \(\Theta(n log n)\), with a small constant factor.

It is an divide-n-conquer algorithm.

1. First find a pivot value \(x\), which is typically the last element in the array.
2. Then partition the array into two parts, less than \(x\) and larger than \(x\).
3. recursively do this for the two partitions

def sort(A):
  quicksort(A, 1, len(A))
def quicksort(A, p, r):
  q = partition(A, p, r)
  quicksort(A, p, q-1)
  quicksort(A, q+1, r)

The partition function:

def partition(A, p, r):
  x = A[r]
  i = p-1
  for j in range(p, r):
    if A[j] <= x:
      i = i+1
      # values less than x swapped to left part
      swap(A[i], A[j])
  # put the pivot value in place
  swap(A[i+1], A[r])
  return i+1

Or I prefer a functional way, in which case we don't even need to specify the implementation of partition function, as it is obvious:

def quicksort(A):
  x = A[-1]
  Al, Ar = partition(A, x)
  return [quicksort(Al), x, quicksort(Ar)]

All sorting algorithms above are comparison sorts, which can be proved to take at least \(n log n\) running time. The algorithms in this section makes certain assumptions to the array.

• linked list
  • head
  • tail
  • next
• doubly linked list
  • next
  • prev

• push
• pop
• enqueue
• dequeue

Using binary tree as example. &

BFS:

q = queue()
def traverse(root):
  q.insert(root)
  while (x = q.pop()):
    q.insert(x.children)
    visit(x)

DFS:

traverse(root)

def traverse(node):
  traverse(node.left)
  traverse(node.right)

Only defined for DFS.

Pre-order:

def traverse(node):
  visit(node)
  traverse(node.left)
  traverse(node.right)

In-order (only defined for binary tree):

def traverse(node):
  traverse(node.left)
  visit(node)
  traverse(node.right)

Post-order:

def traverse(node):
  traverse(node.left)
  traverse(node.right)
  visit(node)

Same as trees, except checking for repeat (by coloring).

Run DFS (or BFS) and print out the nodes.

Given a graph (V,E), and each edge has a weight. Find the subset of edges \(E' \subset E\) such that (V,E') is a tree. This tree is called spanning tree. The spanning tree with minimum sum of edge weights is called the minimum spanning tree.

General idea: We grow a set of edges A, from \(\emptyset\), and maintain the invariant that is a subset of some minimum spanning tree. If we can add an edge to A, and don't violate this invariant, we call it safe edge to A.

A = {}
while A is not a spanning tree:
  find (u,v) that is safe for A
  A = A union {(u,v)}

Theorem 23.1:

\(A\) is a subset of \(E\), and \(A\) is in some minimum spanning tree of G. Cut \(c\) respects A. Then the light edge of \(c\) is safe to \(A\).

Corollary 23.2

A is a subset of E and A is included in some minimum spanning tree of G. We have a forest F=(V,A). In the forest, there will be many connected components \(C_i\).

Then the light edge connecting \(C_i\) to \(C_j\) is safe to A.

Given a weighted, directed graph, the shortest path from u to v is the path that has minimum weight. We talk mainly about single-source, single-destination shortest path.

We add to attributes to vertices of the graph:

• v.d: the upper bound of shortest path from s to v. Initialize to infinite.
• v.pred: the predecessor for that upper bound. Initialize to nil.

First a helper function, relax of an edge (u,v), by checking whether setting v.pred to u improve v.d:

def relax(u,v):
  if v.d > u.d + w(u,v):
    v.d = u.d + w(u,v)
    v.pred = u

The constraints of a flow network:

1. capacity constraint: 0 ≤ f(u,v) ≤ c(u,v)
2. flow conservation: ∑_{v∈ V} f(v,u) = ∑_{v ∈ V} f(u,v). I.e. the ingoing and outgoing flow of a node shall equal.

We are interested in two equivalent problems:

• maximum flow
• minimum cut

Residual network:

• Residual network: given capacity c and flow f, the capacity of residual network \(c_f\) is simply \(c(u,v)-f(u,v)\).
• augmenting path: given a flow network G and a flow f, the augmenting path p is a simple path from s to t in the residual network \(G_f\)

The cut of a flow is (S,T) where S + T = V. The flow f(S,T) across the cut is defined as:

\[f(S,T) = \sum_{u\in S} \sum_{v \in T} f(u,v) - \sum_{u\in S} \sum_{v \in T} f(v,u)\]

The capacity of the cut is:

\[c(S,T) = \sum_{u\in S} \sum_{v \in T} c(u,v)\].

The minimum cut is the one whose capacity is minimum. The max-flow min-cut theorem states that the minimum cut equals to the max-flow. Specifically, the following conditions are equivalent:

1. f is maximum flow in G
2. The residual network \(G_f\) contains no augmenting paths
3. |f|=c(S,T) for some cut (S,T) of G.
   • This should be further written as |f| equal to the capacity of minimum cut of G.

Given a rod of length n, and a price table mapping from lengths to prices. Determine the maximum revenue obtainable by cutting and selling the rod.

def cutrod(price_table, n):
  r[0] = 0
  for i in range(1, n):
    q=0
    for j in range(1, i):
      q = max(q, p[i]+r[i-j])
    r[i] = q
return r[n]

It is used to judge whether an item is in a set or not.

If bloom() return false, it is false. But if bloom() return true, it may not be true.

The basic idea is, hash(item), map it in a vector of m size. The vector is 0 initially. v[hash(item)] is set to 1. To reduce fault rate, use k hash functions.

To verify, only if all k hash functions has 1 in the vector will it return true. Otherwise return false.

A barrel shifter is a digital circuit that can shift a data word by a specified number of bits in one clock cycle.

In the above image, x is input and y is output.

For shift 1, all the erjiguan on the green line exist, while others not.

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers.

pseudorandom number generator algorithms(PRNG).

\(X_{n+1} = (aX_n+c) mod m\)

X array is the pseudorandom.

• \(X_0\): seed
• m: modulus
• a: multiplier
• c: increment

If c = 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer RNG. If c ≠ 0, the method is called a mixed congruential generator.

Solve problem by breaking down into simpler sub-problems.