Algorithms

Growth Rates and Dominance relations

• n! useless for n >= 20
• 2ⁿ impractical for n > 40
• n² usable up to n = 10k, useless for n > 1M
• n and nlogn practical 1B+
• lgn works for any value of n
• 1 < n log(n) < n < log(n) < n² < n³ < 2ⁿ < n!

Bubble sort

• Runtime: O(n²) average and worst case
• Memory: O(1)

Insertion sort

• Incremental approach
• In place
• Find element, insert it in its right position in the sorted array (swap with last if smaller, until position is correct)
• Runtime: O(n²) average and worst case
  • Faster than merge sort for small n (<20)
• Memory: O(1)

Selection sort

• Find smallest element and exchanging with A[1], find next and exchange with A[2]...
• Runtime: O(n²) average and worst case
• Memory: O(1)

Merge sort

• divide and conquer
• Divide: Divide sequence into two subsequences of n/2
• Conquer: Sort the two subsequences recursively using merge sort
• Combine: Merge the two sorted subsequences
  • Find smallest of the two sorted, add to array, when a sequence is done, add all the remaining ones from the other one.
• Runtime: O(n log n) average and worst case
• Memory: varies

Heapsort

• Sorts in place
• Heaps: length and heap-size
• Parent: ⌊k/2⌋
• Left: 2k
• Right: 2k + 1
• Leaves: ⌊n/2⌋ + 1, ⌊n/2⌋ + 2,... n
  • Non-leaves: 1..&lfoor;n2⌋
• height: ⌊lg n)⌋
• O(n lg n)

max-heap/min-heap: values in nodes obey heap property

• max-heap: A[parent(k)] ≥ A[i]; heapsort
• min-heap: A[parent(k)] ≤ A[i]; priority queues

height = number of edges in longest path (lg n)

• max-heapify (O(h))
  • floats value down from parent to children
  • start at top
  • compare to left/right children
  • swap with whichever of them if its larger
  • max-heapify the child that got swapped
• build-max-heap
  • heap-size = length(A)
  • call max-heapify on each non-leaf node, from the bottom up
• heapsort
  • build-max-heap
  • exchange A[n] with A[1]
  • decrease heap-size counter
  • max-heapify root

Quicksort

• In place

• Divide: partition into A[p..q-1] and A[q+1..r] such that all in first are less than q and all in second are more than q. Compute index of q as part of this

• Conquer: sort the two subarrays recursively with quicksort

• Combine: nothing to do here

• worst case on sorted input (O(n²))

• Randomizing input to obtain average-case performance

• Runtime: worst case O(n²), expected O(n log n)

• Memory: O(logn)

• partition(A, p, r)

  • pivot is A[r]
  • i = p-1
  • loop j from p to r-1
    • if A[j] ≤ pivot, i++, swap(A[i], A[j])
  • swap(A[r], A[i+1]
  • return i+1

• _quicksort(A, p, r)

  • if p < r
    • q = partition(A, p, r)
    • quicksort(A, p, q-1)
    • quicksort(A, q+1, r)

Counting sort

• stable
• O(n)
• Assumes integers in a small range
• second array (C) of length equal to highest value + 1 (from 0 to k) in original array
• Loop over A and increment the value of C[A[j]] to get a total number of elements equal to i at C[i]
• Increment C[i] by C[i-1] (to get number of elements less than or equal to i at C[i]
• Loop from the end down to 1, and copy into B at the position indicated by the value of --C[A[j]]

Radix sort

• uses counting sort (or some other stable sorting) to sort each of the digits
• Sort by least significant digit, then second, then third, etc.
• Might make fewer passes than quicksort over the n keys, but each pass may be longer
• Which one is preferable depends on implementations, underlying machine (quicksort uses hardware caches more effectively) and the input data.
• Not in place, so if primary memory is scarce, an in place algo may be preferable
• Runtime O(kn)

Bucket sort

• Assumes input is uniformly distributed over [0,1]
• Divide interval into n equal sized buckets
• Distribute elements into corresponding bucket
• Sort bucket (with insertion sort, given that small number is expected)
• Join items from the buckets
• Runtime: O(n)
• Memory: O(n)?, Requires additional n-sized array of linked lists

Dynamic Programming

• Applicable to optimization problems where there is an optimal substructure and overlapping subproblems.

• Steps

  1. Formulate answer as recurrence relation or recursive algorithm
  2. Show that the number of parameters values taken by the recurrence is bounded by a small polynomial
  3. Specify an order of evaluation for the recurrence so that the partial results you need are always available when you need them

Optimal substructure

• if an optimal solution to the problem contains within it optimal solutions to subproblems. This could also mean that a Greedy strategy applies.
• must ensure that the range of subproblems considered includes those used in an optimal solution
• Pattern:
  1. you show that a solution consists of making a choice. Making choice leaves one or more subproblems to solve
  2. you suppose that for a given problem you are given the choice that leads to an optimal solution
  3. given this choice, determine which subproblems ensue and how to characterize the resulting space of subproblems
  4. show that the solutions to the subproblems used within the optima solution must themselves be optimal by using a cut-and-paste technique
• uses optimal substructure in a bottom-up fashion (as opposed to greedy which is top-down)
• subproblems must be independent (the solution to one subproblem does not affect the solution to another subproblem). They do not share resources

Overlapping subproblems

• the space of subproblems must be "small" so that a recursive algorithm solves the same subproblems over and over rather than generating new subproblems
• they're the same subproblem that occurs as a subproblem of different problems
• a problem where divide and conquer is more suitable is that where each a new problem arises at each step of the recursion
• we often store which choice we made in each subproblem so that we don't need to reconstruct this information from the costs that we stored.

Memoization

• memoize the natural, but inefficient, recursive algorithm
• maintain a table with subproblem solutions but the control structure for filling the table is more like the recursive algorithm
• each entry in table has initial special value to indicate it has not been filled yet
• first time a subproblem is encountered, its solution is stored in the table
• each subsequent time, the value from the table is looked up and returned
• presupposes that the set of subproblem parameters is known and that the relation between table positions and subproblems is established. Alternatively, memoize by hashing the subproblem parameters as keys
• if all subproblems must be solved at least once, bottom-up DP algorith usually outperforms a top-down memoized by a constant factor.
• if some subproblems in the space need not be solved, the memoized solution only solves the ones that are definitely required.

Combinatorial Search

Backtracking

# Pseudocode
backtrack-DFS =  (A, k) ->
  if A = (a1, a2, a3, ... ak) is a solution then report it
  else
    k++
    compute Sk
    until Sk.empty?
      ak = an element in Sk
      Sk = Sk - ak
      backtrack-DFS(A, k) # DFS uses less space (proportional to height)

backtrack = (a, k, input) ->
  if isSolution(a, k, input)
    processSolution(a, k, input) 
  else
    k++
    candidates = constructCandidates(a, k, input)
    for candidate in candidates
      a[k] = candidate
      makeMove(a, k, input)
      backtrack(a, k, input)
      unmakeMove(a, k, input)
      return if finished

All subsets

• 2ⁿ solutions

isSolution = (a, k, n) ->
  k == n

constructCandidates = (a, k, input) ->
  [true, false] # With and without the element in the subset

processSolution = (a, k, input) ->
  for i in [0..k]
    print i if a[i] == true

generateSubsets = (n) ->
  solutions = []
  backtrack(solutions, 0, n)

All Permutations

• n! solutions

constructCandidates = (a, k, input) ->
  inPerm = for in in [0..NMAX]
    inPerm[i] = false
  for in in [0..k]
    inPerm[a[i]] = true

  candidates = for i in [0..n] when inPerm[i] == false # return all items not yet in the permutation

# processSolution and isSolution same as subsets
generatePermutations = (n) ->
  solutions = []
  backtrack(solution, 0, n )

All paths in a graph

• Paths from s to t - no explicit formula for solution count, given that depends on the graph
• Starting point is always s (S₁ = {s})
• Second candidate are such that (s,v) is an edge in the graph
• S_{k + 1} consists of the vertices adjacent to a_k that haven't been used in the partial solution A

constructCandidates = (a, k, n) ->
  inSol = for in in [0..NMAX]
    inSol[i] = false
  for in in [0..k]
    inSol[a[i]] = true

  candidates = []

  if k == 1
    candidates.push(1)
  else
    last = a[k -1]
    edge = g.edges[last)]
    while edge != null
      if !inSol(edge.vertex)
        candidates.push(edge.vertex)
      edge = edge.next
  candidates

isSolution = (a, k, t) ->
  return a[k] == t

processSolution = (a, k) ->
  solutionCount++

Search pruning

• Enumerating all n! permutations of n vertices of the graph and selecting the best one yield the correct algorithm for optimal solution to TSP
  • For each permutation see if edges exist, and if so, add weights together
  • Wasteful to calculate all permutations first (if edge (v1, v2) is not in graph, no need to calculate the (n-2)! permutations starting with (v1, v2))
  • Better to prune the search after v1, v2 and continue to v1, v3. Restricting the search greatly reduces complexity
• Pruning consists of cutting off the search as soon as we know the partial solution cannot be extended to a full solution
  • In TSP, we search for tour with lowest cost. If during the search we encounter a tour with cost C_t and later find a partial solution with cost C_a > C_t, there's no point in continuing down this route

Combinatorial searches, when combined with pruning, can find the optimal solution for small optimization problems. How small depends on the problem, but typical sizes are betwen 15 and 50 items

Heuristic Search methods

Random Sampling (Monte Carlo method)

• Repeatedly construct random solutions, evaluate them (cost-wise) and stop whenever a "good enough" solution is found. Generally good enough means we're tired of waiting. Report best solution found in the course of sampling
• Requires that we're able to select elements uniformly at random
• Works when
  • there's a high number of acceptable solutions
  • there's no coherence in the solution space; no sense of "getting closer" to a solution (TSP is not such a problem, it is highly coherent)

Local Search

• Uses a local neighbourhood around every element in the solution space
• Proceeds to the most promising candidate in X's nhood
• Want to find a general transition mechanism by chaning the current solution slightly rather than generating the nhood graph. Typical transitions:
  • Swapping random pair of items
  • Inserting/deleting a single item in the solution
• Works when
  • there is great coherence in the solution space
  • whenever the cost of incremental evaluation is cheaper than the cost of global evaluation
• Primary drawback is that once we find a local optimum, nothing more to do other than try a new random point

Simulated annealing

• Allows transitions to more expensive (inferior) solutions
• Prevents getting stuck in local optima
• Every loop does a random "cooling schedule", which governs if we accept a bad solution as a function of time
• At the beginning of the search we are eager to use randomness to explore widely. As search progresses, we seek to limit transitions to local improvements and optimizations
• Temperature decrementing function is usually of the form t_k - a*t_k-1, to produce exponential decay instead of linear
• Acceptance criteria, when C(s_i) < C(s_{i + 1}) or transition probability is greater than some random number (allowing negative transitions)
  • At starting temperatures, most transitions are accepted and as tme goes by, this chance gets reduced (Probability is inversely proportional to (k-t))
• Stop when current solution has not changed or improved with the last iteration

String Matching

• For short patterns, trivial O(mn) algorithm suffices (hard to beat for m < 5 ). Usually runs in linear time
  • On a mismatch, we don't need to go back to the spot where the pattern match began, we can continue from where the mismatch happened

Linked List

• Recursive solutions are common
• Slow Runner/Fast runner

Recursion

• Bottom-up - build a solution for one case off of the previous case
• Top-down - divide the problem for case N into subproblems
• Can be space inefficient (each call adds a layer to the stack)

Graph search

• Mark each vertex during exploration as: undiscovered -> discovered -> processed
• Ignore edges that go to discovered/processed nodes
• Graph could have separate connected components

Breadth-first Search

BFS = (G, start) ->
  for u in G.vertices (except start)
    u.state = 'undiscovered'
    u.parent = nil
  start.state = 'discovered'
  s.parent = nil
  queue = new Q()
  queue.enqueue(s)
  until queue.isEmpty
    u = queue.dequeue
    processVertexEarly(u.vertex)
    for edgenode in u.edges
      v = edgenode.vertex
      if v.state == 'processed' || g.isDirected
        processEdge(u, v)
      if v.state == 'undiscovered'
        v.state = 'discovered'
        v.parent = u
        queue.enqueue(v)
     u.state = 'processed'
     processVertexLate(u)

• Useful to find interesting paths
• Unique path from root to node x is the shortest path on onweighted graphs. Can reconstruct path following ancestor chain up from x.parent (can be done with a stack or recursively
• Find number of connected components
• Two-coloring bipartite graphs

Depth-First search

• Uses a stack instead of a queue
• Keeping track of traversal time (tick every time we enter or exit a vertex) allows certain features
• DFS has recursive implementation which eliminates need for stack

time = 0
finished = false
DFS = (graph, u) ->
  return if(finished) # allow for search termination
  u.state = 'discovered'
  processVertexEarly(u)
  u.entry = time
  time++
  for edgenode in u.edges
    v = edgenode.vertex
    if v.isUndiscovered()
      v.parent = u
      processEdge(u, v) # treeEdge
      DFS(graph, v)
    else if !v.isProcessed() || g.isDirected
      processEdge(v, y) # backEdge
      return if finished
    processVertexLate(v)
    u.state = 'processed'
    u.exit = time
    time++

processEdge = (x, y) ->
  if y.parent == x
    # Tree edge
  if y.isDiscovered() && !y.isProcessed()
    # Back edge
  # On directed graphs
  if y.isProcessed()
    if y.entry > x.entry
      # Forward edge
    else
      # Cross edge

  if isBackEdge && x.parent != y && y.entry < x.reachableAncestor # reachableAncestor initialized to itself
    x.reachableAncestor = y

• Time intervals allow
  • identification of ancestry (time interval of y must be properly nested within ancestor x)
  • number of descendants - (exit - entry)/2
  • useful in topological sorting and biconnected/strongly-connected components
• Partitions edges of undirected graph into:
  • tree edges: discover new vertices, encoded in parent relation
  • back edges: those whose other endpoint is an ancestor of the vertex being expanded (point back into the tree)
• Applications
  • Finding cycles - back edges indicate cycles in an undirected graph. If no back edges exist, there are no cycles (set finished = true in processEdge to finish early)
  • Articulation vertices (cut-nodes) - removal of which disconnects a connected component. Graphs without an articulation vertex are called biconnected
    • If root has more than one child, it's an articulation vertex (root cut-node)
    • if x.reachableAncestor == x, deleting the edge (x.parent, x) disconnects the graph, so v.parent must be articulation vertex (bridge cut-node). x is also an articulation vertex unless it's a leaf (leaves are never articulation vertices).
    • if x.reachableAncestor == x.parent, deleting x.parent must sever x, and therefore is a parent cut-node
    • Calculate and update reachableAncestor in processVertexLate

    processVertexLate = (v) ->
      timeV = v.reachableAncestor.entry
      timeParent = v.parent.reachableAncestor.entry
      if timeV < timeParent
        v.parent.reachableAncestor = v.reachableAncestor

  • Find Bridge edges - edge (x,y) is a bridge if a) it's a tree edge and b) there are no back edges from y or below to x or above

DFS on Directed graphs

• Topological sorting - on Directed Acyclic Graphs (DAG) orders vertices on a line such that all directed edges go left to right. Not possible if graph contains a directed cycle. Each DAG has at least one topological sort.
  • Applications
    • Allows an ordering to process each vertex before any of its successors.
    • Seeking for shortest (or longest path) from x to y, no vertex appearing after y in topological order can be part of the path
  • A directed graph is a DAG only if no back edges are found.
  • Labeling vertices in the reverse order that they are marked as processed find a topological sort for a DAG

  processVertexLate = (v) ->
    stack.push(v)
  
  topologicalSort = (graph) ->
    stack = Stack.new
    for vertex in g.vertices
      if !vertex.isDiscovered()
        DFS(g, vertex)
    printStack(stack)

• Strongly Connected Components - when there is a directed path between any two vertices
  • Do a BFS or DFS from an arbitrary vertex. Unless every vertex is reachable from v, it can't be strongly connected
  • Repeat same search reversing all edges
  • Graph is strongly connected if all vertices are reachable from v and v is reachable from all vertices
  • Non-strongly connected graphs can be broken down into strongly connected components.
    • Find directed cycles with DFS (any back edge plus down path is a cycle, all vertices of which form a strongly connected component. Reduce to single vertex and repeat. Terminate when no directed cycle remains and each vertex represents a strongly connected component

Shortest path on weighted graphs

Dijkstra's Alorthm

• Proceeds in a number of rounds finding the shortest path from s to some new vertex x, where the new vertex is that which minimizes the total distance so far (dist(s, v_i)plus the distance to the new vertex (w(v_i, x))
• Once we find the shortest path to x, we check all outgoing edges of x to see whether there's a better path from s so some unknown vertex through x
• Only works correctly on graphs with non-negative edges

# Pseudocode
dijkstra = (G, s, t) ->
  known = [s]
  dist = Infinity for i in [0..n]
  for each edge (s,v)
    dist[v] = w(s, v)
  last = s
  while s!= t
    vnext = unknown vertex minimizing dist[v]
    for each edge (vnext, x)
      dist[x] = min(dist[x], dist[vnext] + w(vnext, x))
    last = vnext
    known.push(vnext)

dijkstra = (G, start) -> # Finds shortest path to ALL vertices
  inTree = [], distance = [], parent =[]
  for i in [0..g.numVertices]
    inTree.push(false)
    distance.push(Math.Infinity)
    parent.push(-1)

  distance[s] = 0
  v = start
  while inTree[v] == false
    inTree[v] = true
    p = g.edges[v]
    while p != nil
      w = p.y
      weight = p.weight
      if distance[w] > distance[v] + weight
        distance[w] = distance[v] + weight
        parent[w] = v
      p = p.next

    v = 1
    dist = Math.Infinity
    for i in [0..g.numVertices]
      if inTree[i] == false && (dist > distance[i])
        dist = distance[i]
        v = i

A* Alorthm

• When choosing next node x, take into account the estimated cost to the goal using heuristics. A common one is linear distance
• Choose node that minimzes dist(s,v) + weight(v,x) + estimatedCostToGoal(x)
• Dijsktra is a special case of this where the estimated cost is always 0.