Final Note Sheet

Basic Math

Order Notation

Let . We define the following relations

Furthermore, we can define stronger relations

Big-O Identities

Master Theorem

Given a recurrence relation with constants , , and

Arithmetic Algorithms

Modular Exponentiation

Input: Two -bit integers and , an integer exponent Output: Runtime:

def modexp(x, y, N):
	if y == 0: return 1
	z = modexp(x, y // 2, N)
	if y % 2 == 0:
		return (z ** 2) % N
	else:
		return (x * (z ** 2)) % N

Extended Euclid

Input: Two positive integers and with Output: Integers such that and Runtime: . There are iterations, each with cost (division)

def extended_euclid(a, b):
	if b == 0: return (1, 0, a)
	(xp, yp, d) = extended_euclid(b, a % b)
	return (yp, xp - floor(a / b) * yp, d)

For integers , if , then we can compute by running the extended gcd algorithm. Equivalently

Fermat’s Little Theorem

If is prime, then for every ,

RSA

Pick primes and , then let . For any relatively prime to ,

is a bijection on
Let . Then

Fast Fourier Transform

Input: An array , for a power of . A primitive th root of unity, Output: Runtime:

def fft(a, omega):
	if omega == 1: return a
	(s[0],s[1],...,s[n/2-1]) = FFT((a[0], a[2],..., a[n-2]), omega ** 2)
	(t[0],t[1],...,t[n/2-1]) = FFT((a[1], a[3],..., a[n-1]), omega ** 2)
	for j in range(0, n/2):
		r[j] = s[j] + omega ** j * t[j]
		r[j + n/2] = s[j] - omega ** j * t[j]
	return r

Divide and Conquer

Multiplication

Input: Positive integers and , in binary Output: Their product Runtime: ;

def multiply(x, y):
	n = max(len(x), len(y))
	if n == 1: return x * y
	xl, xr = x[:len(x)//2], x[len(x)//2:]
	yl, yr = y[:len(y)//2], y[len(y)//2:]
	p1 = multiply(xl, yl)
	p2 = multiply(xr, yr)
	p3 = multiply(xl + xr, yl + yr)
	return p1*(2**n) + (p3-p1-p2) * (2**(n//2)) + p2

Mergesort

Input: Array of numbers Output: A sorted version of the array Runtime: ;

def mergesort(a):
	if len(a) > 1:
		return merge(
			mergesort(a[:n//2]),
			mergesort(a[n//2:]))
	else:
		return a
		
def merge(x, y):
	if len(x) == 0: return y
	if len(y) == 0: return x
	if x[0] <= y[0]:
		return [x[0]] + merge(x[1:], y)
	else:
		return [y[0]] + merge(x, y[1:])

Selection

Input: A list of numbers ; an integer Output: The th smallest element of

For some , define , , to be elements of less than, equal to, or greater than .

With some expectations, we have , so runtime

Graphs

DFS

Input: is a graph; Output: is true if reachable from Runtime:

def explore(V, E, v):
	visited(v) = true
	previsit(v)
	for (v,u) in E:
		if not visited[u]: dfs(G, u)
	postvisit(v)
 
def dfs(V, E)
	for v in V:
		visited v = false
	for v in V:
		if not visited(v):
			explore(v)

We can identify connected components with the following previsit

def explore(V, E, v):
	...
	id += 1
	
def previsit(v):
	component_id[v] = id
 
def dfs(V, E):
	id = 0
	...

Topological Ordering

def previsit(v):
	pre[v] = clock
	clock += 1
 
def postvisit(v):
	post[v] = clock
	clock += 1

For a DAG, vertices with descending postvisit orderings will be sorted in topological order. We have the following types of edges

tree edge - an edge used in the DFS forest
forward edge - node to nonchild descendant
back edge - lead to ancestor node
cross edge - lead to postvisited node

Strongly Connected Components (Kosaraju’s)

Let be a DAG, and define a relation where if there is a path from to and vice versa. This relation partitions into strongly connected components. To compute the strongly connected components of a graph, we can run Kosaraju’s algorithm. This algorithm runs in linear time;

Run DFS on (the reverse graph)
Run the connected components algorithm, exploring vertices in topological order from the previous DFS.

BFS

Input: Graph ; vertex Output: For reachable from , is the distance Runtime:

def bfs(V, E, s):
	for u in V:
		dist(u) = inf
	dist(s) = 0
	q = [s]
	while not len(q) == 0:
		u = q.pop()
		for edges (u,v) in E:
			if dist(v) = inf:
				q.append(v)
				dist(v) = dist(u) + 1

Dijkstra’s Algorithm

Input: Graph , directed or undirected; positive edge lengths ; vertex Output: For all vertices reachable from , is shortest distance Runtime:

impl	deletemin	io key	runtime
Array
Binary Heap
-ary Heap
Fibonacci Heap		amortized

Operations:

Insert Add element to set
Decrease-key Accommodate the decrease in key value of a particular element
Delete-min Return element with least key and remove from set
Make-queue Build pqueue out of given elements, with given key values.

def dijkstra(V, E, l, s):
	for u in V:
		dist(u) = inf
		prev(u) = None
	dist(s) = 0
	H = makequeue(V)
	while H is not empty:
		u = deletemin(H)
		for all edges (u,v) in E:
			if dist(v) > dist(u) + l(u,v):
				dist(v) = dist(u) + l(u,v)
				prev(v) = u
				decreasekey(H, v)

Alternate Implementation

R = {}
while R != V
	pick node v not in R with smallest dist
	add v to R
	for all edges (v,z) in E:
		if dist(z) > dist(v) + l(v,z):
			dist(z) = dist(v) + l(v,z)

Bellman-Ford

Input: Directed graph ; edge lengths with no negative cycles; vertex Output: For all reachable from , is minimum distance from Runtime:

If another iteration yields updates to the distances, there is a negative cycle.

def bellman_ford(V, E, l, s):
	for u in V:
		dist(u) = inf
		prev(u) = None
	dist(s) = 0
 
	for i in range(0, |V| - 1):
		for (u,v) in E:
			dist(v) = min(dist(v), dist(u), l(u,v))

Cut Property

Suppose edges are part of a minimum spanning tree of . For any subset of nodes where does not cross and , let be the lightest edge across the partition. Then is part of some MST.

Kruskal’s Algorithm

Input: A connected undirected graph with edge weights Output: A minimum spanning tree defined by edges Runtime:

def makeset(x)
	p[x] = x
	rank[x] = 0
 
def find(x)
	while x != p[x]:
		x = p[x]
 
def union(x, y):
	rx = find(x)
	ry = find(y)
	if rx == ry: return
	if rank[rx] > rank[ry]:
		p[ry] = p[rx]
	else:
		p[rx] = p[ry]
		if rank[rx] == rank[ry]:
			rank[ry] = rank[ry] + 1
 
def kruskal(V, E, w):
	for u in V:
		makeset(u)
	X = {}
	sort E by weight
	for (u,v) in E:
		if find(u) != find (v):
			add edge (u,v) to X
			union(u,v)

Prim’s Algorithm

Input: A connected undirected graph with edge weights Output: A minimum spanning tree defined by the array prev Runtime:

def prim(V, E, w):
	for u in V:
		cost[u] = inf
		prev[u] = None
	cost[V[0]] = 0
	
	H = makequeue(V)
	while not H is empty:
		v = deletemin(H)
		for {v,z} in E:
			if cost[z] > w(v,z):
				cost[z] = w(v,z)
				prev(z) = v
				decreasekey(H, z)

Greedy

Huffman Encoding

Input: An array of frequencies Output: An encoding tree with leaves Runtime:

Intuitively, this algorithm merges the smallest 2 nodes at each step, so that the largest nodes are at the top of the tree. This means that the most common occurrences are assigned the shortest character.

def huffman(f):
	H = pqueue of integers, ordered by f
	for i in range(0, n): insert(H, i)
	for k in range(n, 2n):
		i = deletemin(H), j = deletemin(H)
		create node k with children i, j
		f[k] = f[i] + f[j]
		insert(H, k)

Horn Formula

A Horn Formula is comprised of the two types of components

implications conjunction of positive literals implying positive literal
negative clause disjunction of negative literals

Input: Horn Formula Output: a satisfying assignment, if one exists

set all variables false
while there is unsatisfied implication:
	set RHS variable to be true
	
if all pure negative clauses satisfied: return assignment
else: return 'formula unsatisfiable'

Set Cover

Input: A set of elements ; sets Output: A selection of whose union is Cost: Number of sets picked

A greedy algorithm would continuously pick the set containing the largest amount of uncovered elements. This will always perform at most times as worse as the optimal solution, where .

Dynamic Programming

Longest Increasing Subsequence

Problem We have an array of numbers . We want to find the longest increasing subsequence such that .

Solution Compute the following recursive relation. Runs in

Edit Distance

Problem Given two strings and , what are the minimum number of substitutions, deletions, and insertions needed to turn to .

Solution Define as the edit distance of to . We want to compute . Runs in

Knapsack

Problem Given a set of items , we want to pick up items , where is the weight of the item and is the value of the item. We can only carry weight, and we want to maximize the value of the items we pick up.