Algorithms Review Cheat Sheet

Basic Concepts

Complexity

An algorithm is efficient if it runs in polynomial time or better.

Big-O

Denotes worst case running time, a bound on the largest possible run time given input of size N. Theta is lower and upper bound

1 < log n < n < n log n < n^2 < n^3 < a^n < n!

Amortized

Average running time per operation over a worst-case sequence of operation

• Ex. Size-doubling array: 2^n operation every 2^ith step, but constant step otherwise. Hence, O(n) with constant amortized time

  Stable Matching

  Given a set of preferences among hospitals and medical school students, design a self-reinforcing admissions process

• Unstable paier: x and y are unstable if

  • x prefers y and y prefers x to their assigned groupign
• Stable Assignment: Assignment with no unstable pairs

• Perfect matching: Everyone has a single unique match

  Propose-and-reject algorithm

• Gale-Shapely
• Guarantees a stable matching for any problem

• Gives a proposing-optimal assignment

  while some man is free and hasn't proposed to every woman
  choose such a man m
  w = first woman on m's list he has not proposed to
  if w is free
  	assign m and w together
  else if w prefers m to her fiance m'
  	assign m and w to be engaged, m' is free
  else
  	w rejects m

  Data Structures

  Linked List

• Each data node is linked to the next
• Access: O(n)
• Insert: O(1)
• head - first node in list

• tail - last node in list

  Stack

• Last in, First out
• Access: O(1)
• Insert: O(1)
• push(), pop()

• Implement with linked list

  Queue

• First in, First out
• Access: O(1)

• Insert: O(1) if doubly linked list

  Searching

• A linear search can be performed on a sorted sequence O(n)

• Binary Search: Divide-and-conquer on sorted sequence O(log n)

  Sorting

• Bubble Sort: Arranges items by iterating over the sequence, putting larger values on the top piece by piece, swap if left > right adjacent. O(n^2)
• Selection Sort: Repeatedly select the next smallest item from unsorted items O(n^2)
• Insertion Sort: Iterates over sorted sequence, inserts the next unsorted item into its proper place O(n^2)

• Heap Sort: Build heap and extract keys in sorted sequence O(n log n)

  Heap Trees

  A heap is a complete binary tree in which the nodes are organied based on their data values

• Max heap: The value is greater than its two children
• Min heap: The value is smaller than its two children
• Can only remove from the root node
• Inserts in next available left/top location, and sift upwards

• can be stored in a dynamic array

  • parent = i // 2
  • left = 2 * i
  • right = 2 * i + 1
• Insertion: O(log n)
• Extraction: O(log n)

• Building

  • Top down: Heaps constructed by inserting into an empty heap O(n log n)

  • Bottom up: Put everything in array and then fix O(n)

    BST

    Tree such that all keys less than current key is in the left subtree and all keys greater than the key are stored in the right subtree

• Searching is trivial
• Can be built recursively or iteratively

• Removing

  • Remove interior node ->
  • Successor: Minimum key in right subtree

• Search, insert, delete: O(n)

  AVL Trees

  Developed by Adel’son-Velskhii and Landis to guarantee that the tree is height balanced

  Master Theorem

Algorithm Subcategories

Divide and Conquer

• Break up problem into several parts
• solve each part recursively
• combine solutions to sub-problems into overall solution

• n^2 -> n log n

  Mergesort

• Divide array into two halves
• recursively sort each half

• merge two halves to make a sorted whole

  Convex Hull

  Given a set of points, find the smallest convex polygon containing all the points

Graham-scan

start at bottom-left point
sort points by relative polar angle
begin
	add point to stack
	pop off if it creates a left turn

Counting Inversion

Find number of inversions made to match two lists

if list L has one element
	return 0 and list L
Divide L into two halves A and B
(ra, A) = function(A)
(rb, B) = function(B)
(r, L)  = merge-and-count(A,B)
return r = ra + rb + r and sorted list L

Greedy Algorithms

• Build up solutions in small steps
• Make local decisions

• Previous decisions do not factor into the next consideration

  Coin changing

  Given currency denominations, devise a method to pay amount to customer using fewest number of coins

• At each iteration, add coin of largest value that does not take us past the amount to be paid

  • Optimal for US coinage

  • Suboptimal for other situations (1, 10, 21, 34, 70, 100):(140)

    Interval Scheduling

    Find the maximal subset of mutually compatible jobs

• Consider ordering

  • Earliest Start time
  • Earliest finish time
  • Shortest interval
  • fewest conflicts
  • Typically Finish Time is Optimal
• Unweighted solution: Take the next valid job based on finish time and no conflicts

• O(n log(n))

  Interval Partitioning

  Find minimum number of classrooms to schedule all lectures so that no two occur at the same time

• number of classrooms needed >= depth
• Sort by start time
• Assign lecture to any compatible classroom
• O(n log(n))

Dynamic Programming

Develop a solution as a solution to several subproblems, and get benefits in performance as a result of the division of computation.

Weighted Interval Scheduling

Knapsack

Given:

• A collection of n items
• Each item has a weight w
• each item has a value c
• The knapsack has a total weight W

Task:

• Determine set S of items of max value that can be contained in knapsack

Divisible:

• Items do not have to be included in entirety

  sort items in decresing order of c/w
  i = 1
  currentW = 0
  while currentW + w_i < W
  take item of weight w_i and cost c_i
  currentW += w_i
  i++
  take W-currentW portion of item i

  Indivisible:

  function(n,c,w,W)
  if n <= 0
  return 0
  if W < w_n
  withLastItem = -1
  else
  withLastItem = c_n + function(n-1,c,w,W-w_n)
  withoutLastItem = function(n-1,c,w,W)
  return max{withLast,withoutLast}

• Create knapsack with subproblems

• let S[k][v] := the solution with first k items and available weight v

  init S[0][v] = 0
  init S[k][0] = 0
  for v from 1 to W
  for k from 1 to n
  	S[k][v] = S[k-1][v]
  	if w_k <= v and S[k-1][v-w_k] + c_k > S[k][v]
  		S[k][v] = S[k-1][v-w_k] + c_k
  return S[n][W]

  Longest Increasing Subsequence

  Graph Algorithms

  A graph is usually defined as having a number of vertices V and a number of edges E with or without weights.

  Prim’s Algorithm

• Finds Min-Span Tree
• Greedy

• O(V^2)

• Choose an arbitrary starting vertex
• Of edges that connect to the tree, add the minimum-weight one

• Repeat until all vertices are accounted for

  #### Dijkstra's Algorithm

• Shortest path between nodes with non-negative edges

• O(V^2)

• Choose starting vertex
• Assign each node dist: 0 for starting, inf otherwise
• For current, consider all neighbors and calc tentative dists. Compare with previous value and assign smaller
• Mark the current node as visited and remove from unvisited set

• if destination has been reached, terminate else take ‘shortest’ unvisited node path, set as new current, and 3)

  #### Floyd Warshall

• Compares all possible paths through the graph between each pair of vertices

• O(V^3)

  let dist be a |V| x |V| array of minimum dists at infinity
  for each vertex v
  dist[v][v] = 0
  for each edge (u,v)
  dist[u][v] = w(u,v) // the weight of the edge (u,v)
  for k from 1 to |V|
  for i from 1 to |V|
  	for j from 1 to |V|
  		if dist[i]][j] > dist[i][k] + dist[k][j]
  			dist[i][j] = dist[i][k] + dist[k][j]
  		end if

  Bellman-Ford

• Computes shortest path from source vertex to all other vertices
• Slower than Dijkstras
• but can handle negative values
• Runs in O(|V||E|)

for each vertex v in vertices:
	dist[v]    = inf
	predecessor[v] = null;
dist[source] = 0

for i from 1 to size(vertices)-1:
	for each edge (u,v) with weight w in edges:
		if dist[u] + w < dist[v]:
			dist[v] = dist[u] + w
			predecessor[v] = u

for each edge (u,v) with weight w in edges:
	if dist[u] + w < dist[v]:
		error "Graph contains a negative-weight cycle"
return dist,predecessor

Kruskal

Ford-Fulkerson

• Greedy Algorithm
• Computes maximum flow in a flow network
• Complexity: O(Ef); E edges, f maximum flow

given G = (V,E) with flow capacity c, source s, and sink t
f(u,v) = 0 for all edges(u,v)
while there is a path from s to t in G_f, with c_f(u,v) > 0 for all edges:
	find c_f(p) = min(c_f(u,v):(u,v))
	for each edge (u,v)
		f(u,v) += c_f(p)
		f(v,u) -= c_f(p)