Jérôme Waldispühl • Course Webpage • Online Forum • Algorithm Sorting Practice Questions
Sorting  Typical  Θ(log n)  Heap sort, Merge sort, Bubble sort, etc 
Hasing  Insertion  O(1)  Add to beginning 
Deletion  Seach time + O(1)  Using doubly linked list  
Search  Worst: O(n) Expected: Θ(1 + α) 
worst if all keys are in one slot α = n/m = #keys/#slots 

Heaps  Typical  O(log n)  
buildMaxHeap  O(n)  
Red Black Trees  Typical  O(log n)  Balanced height is at most log n 
Find/Union  Quick Find  O(1)  
Union  O(log n) 
Adjacency Representation
List  Search  Worst: Θ(V)  
Storage  Θ(V + E)  
Matrix  Storage Space  Θ(V^{2})  
BFS, DFS, SCC  Total Runtime  Θ(V + E)  V = vertex set, E = edge set 
Kruskal’s Algorithm  Total  O(E logV) → O(logV)  Notice E ≤ V^{2} 
Prim’s Algorithm  Total  O(E logV)  with binary heaps O(E + V logV) with Fibonacci heaps 
Dijkstra’s Algorithm  Total  O(E logV)  with binary heaps O(E + V logV) with Fibonacci heaps 
Gale Shapley  Total  O(n^{2})  Best case Ω(n) 
Bipartite Matching  Runtime  O(nm)  
Weighted Interval Scheduling  Memoization  O(n logn)  O(n) if presorted 
Dynamic Programming  Backtracking  O(n)  Usually, given each backtrack has constant time. 
NeedlemanWunsch  Total  Θ(mn)  m, n are sequence lengths 
Space  Θ(mn)  
Optimal Value Space  Θ(m + n)  Still with Θ(mn) runtime, but we cannot recover optimal alignment  
BellmanFord  Total  O(VE)  
Knapsack Problem  Possible  Θ(nW)  W is integer weight 
Space  Θ(nW) 
f(n)
is O(g(n))
iff there exists a point n0 beyond which f(n)
is less than some fixed constant times g(n)
→ for all n ≥ n0
, f(n) ≤ c * g(n)
(for some c > 0
)T1(n) = O(f(n))
& T2(n) = O(f(n))
T1(n) + T2(n) = O(f(n))
T1(n) / T2(n)
is not necessarily O(1)
; big O is not necessarily the tightest upper bound.
T1(n) = 3n & T2(n) = 2n
is an example.key(n) ≥ key(parent(n))
h – 1
levels are fullh(k) = kmod d
h(k) = (A kmod2^{w}) >> (w – r)
1/(1  α)
1/α * log(1/(1  α))
h(k, i) = (h’(k) + c_{1}i + c_{2}i^{2})mod m
h(k, i) = (h_{1}(k) + i * h_{2}(k)) mod m
h_{2}(k)
should be “relatively” prime to m to guarantee full permutationroot = A[1], left[i] = A[2i], right[i] = A[2i + 1], parent[i] = A[i/2]
h(x)/2 ≤ bh(x) ≤ h(x) ≤ 2bh(x)
≥ 2^{bh(x)} – 1
internal nodes≤ 2lg(n+1)
(proof by previous point)∀ a ∈ S, (a, a) ∈ R
u ∈ V
, there is a path of length 0 from u to u∀ a, b ∈ S, (a, b) ∈ R ⇒ (b, a) ∈ R
u, v ∈ V
, there is a path from u to v iff there is a path from v to u∀ a, b, c ∈ S, (a, b) ∈ R ∩ (b, c) ∈ R ⇒ (a, c) ∈ R
u, v, w ∈ V
, if there is a path from u to v and a path from v to w, there is a path from u to wS_{ij} = { a_{k} ∈ S: ∀ i, j f_{i} ≤ s_{k} < f_{k}, ≤ s_{j} }
A_{ij} =
optimal solution = A_{ik} ∪ {a_{k}} ∪ A_{kj}
S_{ij} ≠ ∅
S_{ij}
where f_{m} = min{ f_{k}: a_{k} ∈ S_{ij} }
Time Complexity  

Initialization  Θ(V) 
Enqueue/Dequeue  O(1) 
Total Runtime  O(V + E) 
Time Complexity  

Loops  Θ(V) 
Total Runtime  Θ(V + E) 
d[u] < f[u] < d[v] < f[v] or d[v] < f[v] < d[u] < f[u]
d[u] < d[v] < f[v] < f[u]
d[v] < d[u] < f[u] < f[v]
d[u] < d[v] < f[u] < f[v]
cannot happenClassification of Edges  

Tree Edge  In depthfirst forest (paths taken in DFS); found by exploring (u, v) white 
Back Edge  (u, v), where u is descendant of v (in depthfirst tree); forms cycles w/ tree edges; self loops are back edges grey 
Forward Edge  (u, v), where v is descendant of u, but not tree edge black 
Cross Edge  Any other edge; can go between vertices in same or different depthfirst tree(s) black 
a > b & b > c ⇒ a > c
Time Complexity  

Initialize A  O(1) 
First for loop  V MAKESETs 
Sort E  O(E logE) 
Second for loop  O(E) FINDSETs and UNIONs 
Total  O(E logV) 
Example        —————— activity  1  2  3  4  5 predecessor  0  0  2  2  3 Best weight M  2  3  4  9  9 V_{j} + M[p(j)]  2  3  4  9  8 M[j  1]  0  2  3  4  9
Cases  

i = s & j = 0  0 
i ≠ s & j = 0  ∞ 
j > 0  min(d(k, j – 1) + w(k, i): i ∈ Adj(k), d(i, j – 1)) Either a valid predecessor’s weight + current weight, or no change (achieved with fewer hops) 
x * y = 2^{n}x_{L}y_{L} + 2^{n/2}(x_{L}y_{R} + x_{R}y_{L}) + x_{R}y_{R}
One might assume that incrementing takes O(nk) time, since there are n calls at up to k bits may be flipped, but that is an overshoot. All numbers ending with a 0, for example, only require one bit flip on the rightmost digit. We may find the following trend for the counters:
Bit  Flips how often 

0  Every time 
1  1/2 of the time 
2  1/4 of the time 
…  … 
i  1/2^{i} of the time 
…  … 
i ≥ k  Never 