CS1: Design & Analysis of Algorithms Flashcards
1
Q
Algorithm
Insertion Sort
A
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] = key
2
Q
Knowledge
Insertion Sort Running Time
A
O(n²)
3
Q
Knowledge
Divide and Conquer
4 points
A
- 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
4
Q
Theorem
The Master Theorem
A
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
5
Q
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
A
- 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
6
Q
Algorithm
Merge Sort
A
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)
7
Q
Proof
The running time of every comparison-based sorting algorithm is Ω(n log n)
6 points
A
- 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)
8
Q
Knowledge
The Selection Problem
2 points
A
- Input: A set of n (distinct) numbers and a number i, with 1 ≤ i ≤ n
- Output: The iᵗʰ-order statistic of the set
9
Q
Knowledge
Selection Algorithm Running Time
A
O(n)
10
Q
Algorithm
Integer Multiplication
3 points
A
- 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
11
Q
Knowledge
Integer Multiplication Running Time
3 points
A
- 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))
12
Q
Knowledge
Strassen’s Algorithm Running Time
4 points
A
- 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)
13
Q
Knowledge
MAX-HEAPIFY
2 points
A
- Input: Assume left and right subtrees of i are max-heaps
- Output: Subtree rooted at i is a max-heap
14
Q
Algorithm
MAX-HEAPIFY
A
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)
15
Q
Knowledge
MAX-HEAPIFY Running Time
4 points
A
- Θ(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
16
Q
Knowledge
MAKE-MAX-HEAP
2 points
A
- Input: An (unsorted) integer array A of length n
- Output: A heap of size n
17
Q
Algorithm
MAKE-MAX-HEAP
A
MAKE-MAX-HEAP(A)
A.heap-size = A.length
for i = ⌈(n + 1)/2⌉ - 1 downto 1
MAX-HEAPIFY(A, i)
18
Q
Knowledge
MAKE-MAX-HEAP Running Time
3 points
A
- 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)
19
Q
Algorithm
Heapsort
A
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)
20
Q
Knowledge
Heapsort Running Time
A
O(n log n)
21
Q
Definition
Priority Queue
A
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
22
Q
Knowledge
Operations Supported by a Max-Priority Queue
4 points
A
INSERT(S, x, k)MAXIMUM(S)EXTRACT-MAX(S)INCREASE-KEY(S, x, k)
23
Q
Algorithm
EXTRACT-MAX
Priority Queues
A
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 max
24
Q
Knowledge
EXTRACT-MAX Running Time
Priority Queues
A
O(log n)
25
# 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)
```
26
# Knowledge
`HEAP-INCREASE-KEY` Running Time
O(log n)
27
# 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
28
# 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
29
# 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
30
# 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
31
# 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
32
# 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
33
# 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)
```
34
# 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
```
35
# Knowledge
Depth-First Search Running Time
| 3 points
* `DFS-VISIT` is called exactly once for each v ∈ V
* `DFS-VISIT` takes time O(|Adj(v)|)
* ∑ |Adj(v)| = |E| so T = O(|V| + |E|)
36
# 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
37
# 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]
38
# 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]
39
# 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]
40
# 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]
41
# Lemma
Characterisation
A directed graph has a cycle if and only if its DFS forest has a back edge
42
# 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
43
# 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
```
44
# Knowledge
Topological Sort Running Time
O(|V| + |E|)
45
# Knowledge
Strongly Connected Components
| 2 points
* Input: A directed graph G
* Output: Elements of each SCCs of G output in turn
46
# 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
```
47
# Knowledge
Strongly Connected Components Running Time
O(|V| + |E|)
48
# 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
49
# 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)
```
50
# 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|)
51
# 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]
52
# 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])
```
53
# Knowledge
Dijkstra's Algorithm Running Time
O((|V| + |E|)log|V|)
54
# Knowledge
Bellman-Ford Algorithm
| 2 points
* Input: A directed or undirected graph (V, E), s ∈ V, w: E → ℝ
* Output: `FALSE` if there exists a negative-weight cycle reachable from s otherwise `TRUE`, and for each v ∈ V, d[v] and π[v]
55
# 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 TRUE
```
56
# Knowledge
Bellman-Ford Algorithm Running Time
O(|V||E|)
57
# 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
58
# 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
```
59
# Knowledge
Shortest Paths in DAGs Running Time
O(|V| + |E|)
60
# 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]}
61
# 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]}
```
62
# Knowledge
Floyd-Warshall Algorithm Running Time
O(|V|³)
63
# Definition
Greedy
At each step, the algorithm makes the choice that offers the greatest immediate benefit without reconsidering this choise at subsequent steps
64
# 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
65
# 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.
66
# Definition
Cut
A partition of the vertex-set into two subsets S and V\S
67
# 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
68
# Definition
Set of Edges Respects a Cut
A set of edges A ⊆ E respects a cut if no edge in A crosses the cut
69
# 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
70
# 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.
71
# 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
72
# 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
73
# 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
74
# 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
75
# 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 A
```
76
# Knowledge
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
77
# 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)}
78
# 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))
```
79
# Knowledge
Prim's Algorithm Running Time
| 4 points
* Initialising key[v] and π[v] for every vertex takes O(|V|)
* Each `DECREASE-KEY` operation takes O(log|V|)
* While loop takes |V| `EXTRACT-MIN` and at most |E| `DECREASE-KEY` operations
* Hence overall running time is O(|E|log|V|)
80
# 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
81
# 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 A
```
82
# Knowledge
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
