CS1: Design & Analysis of Algorithms Flashcards
Algorithm
Insertion Sort
for j = 1 to A.length - 1
key = A[j+1]
i = j
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = keyKnowledge
Insertion Sort Running Time
O(n²)
Knowledge
Divide and Conquer
4 points
- Divide a problem into a problems whose size is original size divided by b > 1
- Recursion stops when problems small enough to be solved by brute force
- Solutions combined to build a solution of original solution
- Work done in three places: dividing the problem, solving subproblems and combining their solutions
Theorem
The Master Theorem
Suppose T(n) ≤ aT(⌈n/b⌉) + O(nᵈ) for some constants a > 0, b > 1 and d ≥ 0
Then T(n) = O(nᵈ) if d > log_(b)a, T(n) = O(n^(log_(b)a)) if d < log_(b)a or T(n) = O(nᵈlog n) if d = log_(b)a
Proof
(The Master Theorem)
Suppose T(n) ≤ aT(⌈n/b⌉) + O(nᵈ) for some constants a > 0, b > 1 and d ≥ 0
Then T(n) = O(nᵈ) if d > log_(b)a, T(n) = O(n^(log_(b)a)) if d < log_(b)a or T(n) = O(nᵈlog n) if d = log_(b)a
3 points
- Recursion tree has branching factor a and depth log_b n
- Formulate expression for upper bound of T(n) containing a geometric series
- Consider different cases and the sum of the geometric series
Algorithm
Merge Sort
MERGE-SORT(A, p, r) if r > p + 1 q = ⌊(p + r)/2⌋ MERGE-SORT(A, p, q) MERGE-SORT(A, q, r) MERGE(A, p, q, r)
Proof
The running time of every comparison-based sorting algorithm is Ω(n log n)
6 points
- Every leaf of the decision tree is a permutation of {a₁, a₂, …, aₙ}
- The decision tree has n! leaves
- Every binary tree of depth d has at most 2ᵈ leaves
- In the worst case, the algorithm explores d nodes
- n! ≤ 2ᵈ
- Hence running time is Ω(log n!) = Ω(n log n)
Knowledge
The Selection Problem
2 points
- Input: A set of n (distinct) numbers and a number i, with 1 ≤ i ≤ n
- Output: The iᵗʰ-order statistic of the set
Knowledge
Selection Algorithm Running Time
O(n)
Algorithm
Integer Multiplication
3 points
- Split x = 2^(n/2) x₁ + x₂, y = 2^(n/2) y₁ + y₂
- x y = 2ⁿ x₁ y₁ + 2^(n/2)(x₁ y₂ + x₂ y₁) + x₂ y₂
- Computing x₁ y₁, x₂ y₂, (x₁ + x₂)(y₁ + y₂) suffice
Knowledge
Integer Multiplication Running Time
3 points
- Additions and 3 multiplications of (n/2)-bit numbers are required
- T(n) = 3 T(n/2) + O(n)
- T(n) = O(n^(log₂ 3))
Knowledge
Strassen’s Algorithm Running Time
4 points
- Split matrices X, Y into 8 (n/2)×(n/2) submatrices
- Calculate XY by making additions and 7 multiplications of submatrices
- T(n) = 7 T(n/2) + O(n²)
- T(n) = O(n^(log₂ 7) ≈ O(n^2.81)
Knowledge
MAX-HEAPIFY
2 points
- Input: Assume left and right subtrees of i are max-heaps
- Output: Subtree rooted at i is a max-heap
Algorithm
MAX-HEAPIFY
MAX-HEAPIFY(A, i) n = A.heap-size l = 2i r = 2i + 1 if l ≤ n and A[l] > A[i] largest = l else largest = i if r ≤ n and A[r] > A[largest] largest = r if largest ≠ i exchange A[i] with A[largest] MAX-HEAPIFY(A, largest)
Knowledge
MAX-HEAPIFY Running Time
4 points
- Θ(1) to find largest among A[i], A[2i] and A[2i + 1]
- Subtree rooted at a child of node i has size upper bounded by 2n/3
- T(n) ≤ T(2n/3) + Θ(1)
- T(n) = O(log n) by the Master Theorem
Knowledge
MAKE-MAX-HEAP
2 points
- Input: An (unsorted) integer array A of length n
- Output: A heap of size n
Algorithm
MAKE-MAX-HEAP
MAKE-MAX-HEAP(A)
A.heap-size = A.length
for i = ⌈(n + 1)/2⌉ - 1 downto 1
MAX-HEAPIFY(A, i)Knowledge
MAKE-MAX-HEAP Running Time
3 points
- Number of nodes of height h is upper bounded by n/2ʰ
- Running time of
MAX-HEAPIFYon a node of height h is O(h) - T(n) ≤ Σ (n/2ʰ)O(h) = O(n)
Algorithm
Heapsort
HEAPSORT(A)
MAKE-MAX-HEAP(A)
for i = A.heap-size downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)Knowledge
Heapsort Running Time
O(n log n)
Definition
Priority Queue
An abstract data structure for maintaining a set of elements, each with an associated value called a key, which either gives priority to elements with larger or smaller keys
Knowledge
Operations Supported by a Max-Priority Queue
4 points
INSERT(S, x, k)MAXIMUM(S)EXTRACT-MAX(S)INCREASE-KEY(S, x, k)
Algorithm
EXTRACT-MAX
Priority Queues
HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return maxKnowledge
EXTRACT-MAX Running Time
Priority Queues
O(log n)
Algorithm
HEAP-INCREASE-KEY
HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
error "new key is smaller than existing key"
A[i] = key
while i > 1 and A[Parent(i)] < A[i]
exchange A[i] with A[Parent(i)]
i = Parent(i)Knowledge
HEAP-INCREASE-KEY Running Time
O(log n)
Knowledge
Dynamic Programming
5 points
- Define a sequence of subproblems with the following properties:
1. The subproblems are ordered from smallest to largest
2. The largest problem is the original problem
3. The optimal solution of a subproblem can be constructed from the optimal solutions of smaller subproblems (Optimal Substructure property) - Solve the subproblems from smallest to largest, storing each solution
Knowledge
Divide-and-Conquer vs Dynamic Programming
5 points
- DP is an optimization technique whereas D&C is not normally used to solve optimization problems
- Both split the problem into parts, find solutions to the parts and combine them into a solution of the larger problem
- In D&C, the subproblems are significantly smaller than the original problem and do not overlap (share sub-subproblems)
- In DP, the subproblems are not significantly smaller and overlap
- In D&C, the dependency of the subproblems can be represented by a tree whereas in DP, it can be represented by a directed path from the smallest to largest subproblem
Knowledge
The Change-Making Problem
2 points
- Input: Positive integers 1 = x₁ < x₂ < … < xₙ and v
- Output: Given an unlimiteed supply of coins of denominations x₁, …, xₙ, find the minimum number of coins needed to sum up to n
Knowledge
The Knapsack Problem
3 points
- A knapsack holds a total weight of at most W kg
- There are n items, of weight w₁, …, wₙ ∈ ℕ and value v₁, …, vₙ ∈ ℕ
- Find the most valuable combination of items, which can fit into the knapsack without exceeding its weight
Knowledge
The Edit Distance Problem
4 points
- An edit is an insertion, deletion or character substitution
- The edit distance between two words is the minimum number of edits needed to transform one to the other
- Input: Two strings x[1..m] and y[1..n]
- Output: The edit distance between x and y
Knowledge
Depth-First Search
2 points
- Input: A graph G = (V, E)
- Output: A backpointer π[v], discovery time d[v] and finish time f[v] for each v ∈ V
Algorithm
Depth-First Search
DFS(V, E) for u ∈ V colour[u] = WHITE π[u] = NIL time = 0 for u ∈ V if colour[u] = WHITE DFS-VISIT(u)
Algorithm
DFS-VISIT
DFS-VISIT(u) time = time + 1 d[u] = time colour[u] = GREY for v ∈ Adj[u] if colour[v] = WHITE π[v] = u DFS-VISIT(v) time = time + 1 f[u] = time colour[u] = BLACK
Knowledge
Depth-First Search Running Time
3 points
-
DFS-VISITis called exactly once for each v ∈ V -
DFS-VISITtakes time O(|Adj(v)|) - ∑ |Adj(v)| = |E| so T = O(|V| + |E|)
Theorem
Parenthesis Theorem
For all u, v exactly one of the following holds
1. d[u] < f[u] < d[v] < f[v] or d[v] < f[v] < d[u] < f[u] and neither of u and v is a descendant of the other
2. d[u] < d[v] < f[v] < f[u] and v is a descendant of u
3. d[v] < d[u] < f[u] < f[v] and u is a descendant of v
Knowledge
Tree Edge
3 points
- Edges of the DFS forest
- If (u, v) is a tree edge then v is white when (u, v) is explored
- d[u] < d[v] < f[v] < f[u]
Knowledge
Back Edge
3 points
- Lead from a node to an ancestor in the DFS forest
- If (u, v) is a back edge, then v is grey when (u, v) is explored
- d[v] < d[u] < f[u] < df[v]
Knowledge
Forward Edge
3 points
- Lead from a node to a non-child descendant in the DFS forest
- If (u, v) is a forward edge then v is black when (u, v) is explored
- d[u] < d[v] < f[v] < f[u]
Knowledge
Cross Edge
3 points
- Lead neither to an ancestor nor a descendant
- If (u, v) is a cross edge then v is black when (u, v) is explored
- d[v] < f[v] < d[u] < f[u]
Lemma
Characterisation
A directed graph has a cycle if and only if its DFS forest has a back edge
Knowledge
Topological Sort
3 points
- A topological sort of a DAG G = (V, E) is a total ordering of vertices < ⊆ V×V such that if (u, v) ∈ E then u < v
- Input: A DAG (V, E)
- Output: Elements of V sorted in topological order
Algorithm
Topological-Sort
TOPOLOGICAL-SORT(V, E) Call DFS(V, E) to compute finish times f[v] for all v ∈ V Output vertices in orer of decreasing finish time
Knowledge
Topological Sort Running Time
O(|V| + |E|)
Knowledge
Strongly Connected Components
2 points
- Input: A directed graph G
- Output: Elements of each SCCs of G output in turn
Algorithm
Strongly Connected Components
SCC(G) Call DFS(G) to compute finishing times f[u] for all u Compute Gᵀ Call DFS(Gᵀ) visiting the vertices in order of decreasing f[u] Output the vertices in each tree of the DFS forest formed in second DFS as a separate SCC
Knowledge
Strongly Connected Components Running Time
O(|V| + |E|)
Knowledge
Breadth-First Search
3 points
- δ(u, v) is the minimum number of edges on a path from u to v, if such a path exists; otherwise δ(u, v) = ∞
- Input: A graph G = (V, E) and a source vertex s ∈ V
- Output: For each v ∈ V, an integer d[v] and a back pointer π[v] such that d[v] = δ(s, v) and π[v] = u is the predecessor of v on a shortest path from s to v if there is such a path; otherwise π[v] = NIL
Algorithm
Bread-First Search
BFS(V, E, s)
d[s] = 0
π[s] = NIL
for each u ∈ V - {s}
d[u] = ∞
π[u] = NIL
Q = ∅
ENQUEUE (Q, s)
while Q ≠ ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if d[v] = ∞
d[v] = d[u] + 1
π[v] = u
ENQUEUE(Q, v)Knowledge
BFS Running Time
3 points
- O(|V|) to initialise and enqueue / dequeue each vertex once
- O(|E|) as each edge (u, v) is examined only when u is dequeued
- So overall running time is O(|V| + |E|)
Knowledge
Dijkstra’s Algorithm
4 points
- d[v] is equal to the distance from s to v
- π[v] is the predecessor of v on a shortest path from s to v, if such a path exists or π[v] = NIL otherwise
- Input: A directed or undirected graph (V, E), s ∈ V, non-negative weight w: E → ℝ
- Output: For each v ∈ V, d[v] and π[v]
Algorithm
Dijkstra
DIJKSTRA(V, E, w, s)
for each v ∈ V
d[v] = ∞
π[v] = NIL
d[s] = 0
Q = MAKE-QUEUE(V) with d[v] as keys
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each vertex v ∈ Adj[u]
if d[u] + w(u, v) < d[v]
d[v] = d[u] + w(u, v)
π[v] = u
DECREASE-KEY(Q, v, d[v])Knowledge
Dijkstra’s Algorithm Running Time
O((|V| + |E|)log|V|)
Knowledge
Bellman-Ford Algorithm
2 points
- Input: A directed or undirected graph (V, E), s ∈ V, w: E → ℝ
- Output:
FALSEif there exists a negative-weight cycle reachable from s otherwiseTRUE, and for each v ∈ V, d[v] and π[v]
Algorithm
Bellman-Ford
BELLMAN-FORD(V, E, w, s)
for each v ∈ V
d[v] = ∞
π[v] = NIL
d[s] = 0
for i = 1 to |V| - 1
for each edge (u, v) ∈ E
if d[u] + w(u, v) < d[v]
d[v] = d[u] + w(u, v)
π[v] = u
for each edge (u, v) ∈ E
if d[u] + w(u, v) < d[v]
return FALSE
else
return TRUEKnowledge
Bellman-Ford Algorithm Running Time
O(|V||E|)
Knowledge
Shortest Path in DAGs
2 points
- Input: A DAG G = (V, E) with weight w: E → ℝ and a source vertex s
- Output: For each v ∈ V length d[v] of shortest path from s to v
Algorithm
Shortest Paths in DAGs
TOPOLOGICAL-SORT(V, E) for each v ∈ V d[v] = ∞ π[v] = NIL d[s] = 0 for each u ∈ V in topological order for each v ∈ Adj[u] if d[v] > d[u] + w(u, v) d[v] = d[u] + w(u, v) π[v] = u
Knowledge
Shortest Paths in DAGs Running Time
O(|V| + |E|)
Knowledge
Floyd-Warshall Algorithm
4 points
- Suppose the vertex set is {1, …, n}
- Let d[i, j; k] be the length of shortest path from i to j all of whose intermediate nodes are in the interval [1, k]
- d[i, j; 0] = w(i, j) if (i, j) ∈ E, otherwise d[i, j; 0] = ∞
- d[i, j; k+1] = min{d[i, j; k], d[i, k+1; k] + d[k+1, j; k]}
Algorithm
Floyd-Warshall
FLOYD-WARSHALL(V, E, w)
for i = 1 to |V|
for j = 1 to |V|
d[i, j; 0] = ∞
for each edge (i, j) ∈ E
d[i, j; 0] = w(i, j)
for k = 0 to |V| - 1
for i = 1 to |V|
for j = 1 to |V|
d[i, j; k+1] = min{d[i, j; k], d[i, k+1; k] + d[k+1, j; k]}Knowledge
Floyd-Warshall Algorithm Running Time
O(|V|³)
Definition
Greedy
At each step, the algorithm makes the choice that offers the greatest immediate benefit without reconsidering this choise at subsequent steps
Knowledge
Spanning Trees
5 points
- A spanning tree of a graph G = (V, E) is a subgraph with edge-set T ⊆ E
- T is a tree
- For each u ∈ V, there is some v ∈ V such that (u, v) or (v, u) is in T
- A spanning tree is a minimal connected subgraph
- A spanning tree is a maximal acyclic subgraph
Definition
Safe
Let A ⊆ E be a subset of a MST T.
We say that an edge (u, v) is safe for A iff A ∪ {(u, v)} is a subset of some MST.
Definition
Cut
A partition of the vertex-set into two subsets S and V\S
Definition
Edge Crosses a Cut
An edge (u, v) ∈ E crosses a cut (S, V\S) if one endpoint is in S and the other in V\S
Definition
Set of Edges Respects a Cut
A set of edges A ⊆ E respects a cut if no edge in A crosses the cut
Definition
Light Edge Crossing a Cut
An edge is a light edge crossing a cut if its weight is the minimum of all edges that cross the cut
Lemma
The Cut Lemma
Let A be a subset of some MST.
If (S, V\S) is a cut that respects A, and (u, v) is a light edge crossing the cut, then (u, v) is safe for A.
Proof
(The Cut Lemma)
Let A be a subset of some MST.
If (S, V\S) is a cut that respects A, and (u, v) is a light edge crossing the cut, then (u, v) is safe for A.
3 points
- Consider path between u and v
- T’ has edge crossing the cut replaced with (u, v)
- T’ is a tree with minimum weight that includes A
Knowledge
Disjoint-Set Data Structure
2 points
- Maintains a collection S = {S₁, …, Sₖ} of disjoint dynamic sets
- Each set is identified by a representative, a member of the set
Knowledge
Disjoint-Set Data Structure Operations
3 points
-
MAKE-SET(x)makes a new set {x} and adds it to S -
UNION(x, y)removes Sₓ and Sᵧ from S and adds the new set Sₓ ∪ Sᵧ to the collection S -
FIND-SET(u)returns the representative of the set containing u
Knowledge
Kruskal’s Algorithm
2 points
- Start from A = ∅
- At every step, pick edges with the smallest weight and add it to A if it does not create cycles
Algorithm
Kruskal
KRUSKAL(V, E, w)
A = ∅
for each v ∈ V
MAKE-SET(v)
Sort E into increasing order by weight w
for each edge (u, v) taken from the sorted list
if FIND-SET(u) ≠ FIND-SET(v)
A = A ∪ {(u, v)}
UNION(u, v)
return AKnowledge
Kruskal’s Algorithm Running Time
3 points
- O(|E|log|E| + |V|²) for linked-list implementation of disjoint-set data structure
- O(|E|log|E|) for weighted linked-list
- O(|E|log|E|) for disjoint-set forest
Knowledge
Prim’s Algorithm
3 points
- Set S = {r} and A = ∅
- At every step, find a light edge (u, v) connecting u ∈ S to v ∈ V \ S
- Update S to S ∪ {v} and A to A ∪ {(u, v)}
Algorithm
Prim
PRIM(V, E, w, r)
Q = ∅
for each u ∈ V
key[u] = ∞
π[u] = NIL
INSERT(Q, u)
DECREASE-KEY(Q, r, 0)
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each v ∈ Adj[u]
if v ∈ Q and w(u, v) < key[v]
π[v] = u
DECREASE-KEY(Q, v, w(u, v))Knowledge
Prim’s Algorithm Running Time
4 points
- Initialising key[v] and π[v] for every vertex takes O(|V|)
- Each
DECREASE-KEYoperation takes O(log|V|) - While loop takes |V|
EXTRACT-MINand at most |E|DECREASE-KEYoperations - Hence overall running time is O(|E|log|V|)
Knowledge
Activity Selection
2 points
- Given a set of activities (sᵢ, fᵢ), i = 1, …, n, select a maximum-size subset of activities that do not overlap
- Find the activity with minimum finish time, add it to the solution, remove all overlapping activites and repeat
Algorithm
Activity Selection
ACTIVITY-SELECTION(s, f)
Sort the activites in order of increasing f-values
A = {1}
k = 1
for j = 2 to n
if s[j] ≥ f[k]
A = A ∪ {j}
k = j
return AKnowledge
Activity Selection Running Time
3 points
- The greedy algorithm takes O(n log n) steps to sort the activites
- It takes O(n) steps to process the activities
- In total, it takes O(n log n) steps
