cse310cheatsheet.md

• Graphs and graph traversal

  • BFS
    • Applying directed/undirected graph
    • Distances (number of hops from origin to node), predecessors, layers, and BFS tree
  • DFS
    • Applying to DFS to a directed/undirected graph
    • Time stamps (discovered, finished), predecessors, DFS tree
  • O(n + m) time for graph with n vertices and m edges for both DFS and BFS

• Strongly connected components

  • Means that every vertex can be reached (there is some directed path that exists) from every other vertex in the strongly connected group
  • Using DFS O(n + m)
    • Apply DFS to graph, build stack based on finish times.
    • Construct transpose
    • Apply DFS to transpose graph in order of stack (DECREASING finish time of first DFS)

• Dijkstra’s shortest path algorithm

  • Graph given by adjacency list
  • At each vertex: distance, predecessor (parent)
  • Initialization, build min heap O(n)
  • While heap is not empty, and t is not deleted -> Repeat O(n) times
    • extract min O(log n)
    • Relaxation on each adjacent vertex to extracted vertex -> m number of edges so O(m) * O(log n) (decrease key) = O(m log n)
  • Total O((m + n) log n) time with binary heap
  • Total O(m + (n log n)) time with Fibonacci heap

• Dynamic programming

  • Similar to divide and conquer but different
    • Divide into overlapping instances, do not redo work — check if we have solved an instance already before solving
  • Longest Common Subsequence
    • O(n * m) worst-case time complexity
    • Work in rows top to bottom
      • A[i] = B[j]? LCS[i,j] = Diagonal up left + 1
      • Else, LCS[i,j] = max(top or left square)
      • Arrow points to where the value came from
  • Matrix Chain Multiplication
    • O(n^3) worst-case time complexity
    • s = the k of the element right before the break

• Hash tables

  • Assume n elements and n slots
  • Collision Resolution
    • Open addressing: Next open slot, guaranteed n <= m
      • Insertion O(n)
      • Search O(m)
      • Deletion O(m)
    • Chaining -> linked list in each slot, n could be much larger than m possibly
      • Insertion O(1)
      • Search O(n)
      • Deletion O(n)
    • As long as your hash function is good, you can expect close to O(1) time for all operations since you should have minimal collisions
  • Hash functions
    • Division method
      • hash(k) = k mod m
      • m is a prime number not close to a power of 2 (for exapmle 97)
    • Multiplication method
      • A in (0,1), m is a power of 2
      • hash(k) = floor(m * ((k * A) mod 1))

• Various sorting algorithms and sorting lower bound -> Omega(n log(n))

  • Algorithm, best case, average case, worst case
  • Insertion O(n), O(n^2), O(n^2)
  • Quicksort O(n log n), O(n log n), O(n^2)
  • Mergesort O(n log n), O(n log n), O(n log n)
  • Heapsort O(n log n), O(n log n), O(n log n)
  • Applications
    • Finding smallest element
    • Finding k-th smallest element
    • Finding k smallest elements
    • Finding k-th largest element
    • Finding k largest elements

• Heap data structure

  • BuildHeap O(n)
  • Everything else O(log n)
  • Applications
    • Computing shortest paths
    • Can be used in sorting
    • Can be used in finding k-th smallest/largest
    • Can be used in finding k smallest/largest

• Linear time selection

  • Median of medians method
    • Divide into groups of m elements
    • Find median of each group using a sorting algorithm
    • Recursively use select to find median of medians
    • Partition original search based on median of medians
    • Recursively call select on the side of partitioning in which the desired element may lie
  • Divide and conquer approach
  • Partition element is median of medians
  • Running time O(n)
  • Applications
    • Make quick sort worst case O(n log n) instead of O(n^2)
    • Find k-th smallest/largest element
    • Find k smallest/largest element
    • Find weighted median

• Disjoint sets

  • Array object, tree view
  • Union by rank (attach smaller rank to larger rank), find with path compression (set parent up tree when finding)
  • Worst case running time of m operations with n elements is O(m * alpha(m, n)) where alpha = inv Ackermann function, in practice is ~= 4 for any reasonable number of operations

• Binary search trees

  • Insertion, search, deletion
  • Predecessor, successor, min, max
  • O(n) worst-case time complexity because not balanced
  • Can be used for sorting, possibly (in-order traversal)

• Red-black trees

  • Same operations
  • O(log n) worst-case time complexity because balance is guaranteed