CSCI 3110 Final 13.12.2019
Topics: Asymptotic notation, recurrence relations, divide-and-conquer algo-
rithms, greedy algorithms, dynamic programming, algorithms with data struc-
tures, minimum spanning trees, NP-completeness, graph algorithms
You should try all eight questions. Your best six answers will count towards
your mark. All questions are weighted equally. Good luck!
1. Which are true statements?
(a) 2lg
2 n = o((lg n)n)
(b) nn mod 2 = O(n(n+1) mod 2)
(c) n! = Θ(nn)
(d) nn/2 = Ω(nn
1/2
)
(e) 1−
∑n
i=1 1/2
i = ω(1/3n)
Solution: a, d, e
2. Suppose your friend tells about a problem of computing an binary operation ⊕ on
matrices that takes O(n3 log n) time to compute for two n× n matrices using current
algorithms. Your friend has come up with a way to split each matrix into nine n/3×n/3
matrices, perform ⊕ operations on a pairs of these little submatrices, and then spend
f(n) additional time gluing the results together into the result of the ⊕ operation on
the original matrices. Use the version of the Master Theorem given below to fill in
the following table, giving the complexity of your friend’s algorithm for each value of
a and f(n). Write logb a when a is not an integer power of b (so you do not need a
calculator). Underline the complexities that are strictly better than that of the current
algorithms.
a = 26 a = 27 a = 28
case 1 case 1 case 1
f(n) = Θ(n2) Θ(nlog3 26) Θ(n3) Θ(nlog3 28)
case 3 case 2 case 1
f(n) = Θ(n3) Θ(n3) Θ(n3 log n) Θ(nlog3 28)
case 3 case 3 case 3
f(n) = Θ(n4) Θ(n4) Θ(n4) Θ(n4)
(The case numbers are optional.)
3. According to the text, “a bottleneck spanning tree T of an undirected graph G is a
spanning tree of G [i.e., a tree containing every vertex] whose largest edge weight is
minimum over all spanning trees of G”.
(This might sound familiar because Problem D on the programming contest was really
about finding the largest edge weight in a bottleneck spanning tree of a graph; finding a
minimum spanning tree worked because all minimum spanning trees are also bottleneck
spanning trees, just not vice versa.)
Suppose G is a connected graph with n vertices and m edges and show how to find the
largest edge weight in a bottleneck spanning tree of G in O(m) time in the worst case.
Your algorithm does not have to build the actual tree and you do not have to give an
analysis.
We didn’t cover them in class but you can use two facts without proof:
• we can find the median of an unsorted set of t weights in O(t) time in the worst
case (covered in Chapter 9 in the text, in case you want some holiday reading)
• in O(m) time we can build a data structure that initially stores only the vertices
of G and supports the following operations in O(1) time:
insert(e) inserts edge e of G
undo() undoes the previous insertion (that has not yet been undone)
spanning() says whether the inserted edges include a spanning tree of G.
(Hint: Don’t sort the edges, since that takes too long. Instead, use binary search to
find the largest edge weight in a bottleneck spanning tree, thinking about how to make
all the steps in the search take a total of O(m) time.)
Solution: We find the median edge weight wmed in O(m) time and insert into the
data structure all the edges with weight at most wmed, then check in O(1) time if those
edges include a spanning tree of G.
If the edges in the data structure do include a spanning tree, then we know the largest
edge weight in a bottleneck spanning tree is at most wmed. We discard all the edges
with weight greater than wmed, undo the insertions we just made, and recurse on the
edges with weights at most wmed.
If the edges in the data structure do not include a spanning tree, then we know the
largest edge weight in a bottleneck spanning tree is more than wmed. We “lock in”
the insertions we just did — this just means we remember never to undo them — and
recurse on the edges with weights greater than wmed.
(The rest of this answer is optional.)
In the ith round, we do O(m/2i) insertions, one check, and possibly O(m/2i) undoes.
Therefore, we use O(
∑lgm
i=0 m/2
i) = O(m) time overall.
4. Given a connected edge-weighted graph G with no negative edge weights and a vertex
a, Dijkstra’s Algorithm can be used to build a spanning tree T of G — not necessarily
a minimum spanning tree — such that for every vertex v, the path from a to v in T
has the smallest distance (i.e., total edge weight) of any path from a to v in G.
We start by adding a to T and setting distance(a) = 0 and then repeat the following
procedure:
• for each vertex v not yet in T but adjacent to a vertex already in T , we assign to
v an estimate
min
u∈T
{distance(u) + weight(u, v)}
of its distance from a, where distance(u) is the distance from a to u and weight(u, v)
is the weight of the edge from u to v (or infinity if there is no such edge);
• we add the vertex v with the smallest estimate d to T , set distance(v) = d and
add the edge (u, v) to T , where u is a vertex already in T such that distance(u) +
weight(u, v) = d.
To do this efficiently, we can recalculate our estimates of nodes’ distances from a only
when we add their neighbours to T . The figure below shows the first few steps of
Dijkstra’s Algorithm on a graph and the final tree and distances it produces.
5
7
2
3
4
A 4
95
1
2 4
1
25
0
2
3
4
4
5
∞
∞
∞
5
7
2
3
4
A 4
95
1
2 4
1
25
0
2
3
4
4
5
∞
∞
∞
5
7
2
3
4
A 4
95
1
2 4
1
25
0
2
3
4
4
5
∞
∞
4
5
7
2
3
4
A 4
95
1
2 4
1
25
0
2
3
4
4 4
5
6
9
. . .
The idea behind the proof of correctness of Dijkstra’s Algorithm is that if
• we have correctly computed the tree T up to the start of some step
• in that step add vertex v to T , set v’s distance to d and add the edge (u, v) to T
then any path from a to v must contain an edge with exactly one endpoint in T and the
distance from a to the other endpoint must be at least d. Therefore, since G contains
no negative-weight edges, the distance from a to v is d.
Formalize this argument, using the following style and an exchange argument: “Before
we take any steps, our subsolution can be extended to an optimal solution. Assume
that after i steps. . . ”.
Solution: Before we take any steps, our subsolution can be extended to an optimal
solution. Assume that after i steps our subsolution can be extended to an optimal
solution S. Suppose that on the (i + 1)st step we connect v to T with distance d by
adding edge (u, v). If S includes the edge (u, v), then S extends our subsolution after
i + 1 steps.
Suppose S does not include the edge (u, v). Consider the path P from a to v in S.
Since a is in T when we finish the ith step and v is not in T when we finish the ith
step, P contains some edge (u′, v′) such that u′ is in T when we finish the ith step and
v′ is not in T when we finish the ith step. Since we add v to T in the (i + 1)st step
instead of adding v′, we know
distance(u) + weight(u, v) ≤ distance(u′) + weight(u′, v′) .
Since G contains no negative edge weights, the distance from a to v in S is at least
d. Therefore, if we remove from S the last edge in P , which ends at v, and replace
it with (u, v), then we obtain a new optimal solution S ′ that extends our subsolution
after i + 1 steps.
By induction on the number of steps, Dijkstra’s algorithm is correct.
5. For the problem of local alignment, we are given two strings P [1..m] and S[1..n] and
asked to find the smallest edit distance between P and any substring of S. Write an
O(mn)-time dynamic program that fills in an array A[0..m][0..n] such that A[i][j] is the
minimum edit distance between P [1..i] and any suffix of S[1..j]. How do you extract
the answer to local alignment from A?
Solution: Since the edit distance between the empty prefix P [1..0] of P and the
empty suffix of S[1..j] is 0 for 0 ≤ j ≤ n, we set A[0][0..n] = [0, . . . , 0]. Since the edit
distance between P [1..i] and the empty prefix S[1..0] of S is i for 0 ≤ i ≤ m, we set
A[0..m][0] = [0, 1, 2, . . . ,m].
We fill in the rest of A in O(mn) time using the same recurrence for edit distance,
A[i][j] = min{A[i− 1][j] + 1, A[i− 1][j − 1] + Xi,j, A[i][j − 1] + 1}
where Xi,j = 0 if P [i] = S[j] and Xi,j = 1 if P [i] 6= S[j].
Finally, we report the smallest value in A[m][0..n] (which is the minimum edit distance
between P and any suffix of any prefix of S, which means any substring of S).
6. Suppose you are given an n × n grid on which there are m ≤ n points “in general
position” (meaning no two points are in the same row or column). Give an O(m logm)-
time algorithm that finds the longest descending chain of points, where “descending”
means you can draw a line (not necessarily straight) through all the points in the chain
that always slopes down to the right. You need not prove your algorithm correct. The
figure below shows a 7×7 grid with 7 points and a longest descending chain (there are
several possibilities).
Solution: If we sort the points into decreasing order by their x-coordinates, then
finding the longest descending chain is equivalent to finding the longest increasing
subsequence of their y-coordinates (since we’re considering the points from right to
left). We’ve seen how to do that in class with dynamic programming and a range-max
data structure.
7. Recall that for the NP-complete problem 3-Colourability we are given a graph
G and asked if it is possible to assign each vertex one of three colours such that for
each edge (u, v) the colours of its endpoints u and v are different. The problem of k-
Colourability is defined the same way except that we are allowed to use k colours.
Show that for any constant k ≥ 3 the problem k-Colourability is NP-complete by
• showing it is in NP,
• reducing 3-Colourability to it.
The problem k-Colourability is in NP because, given an assignment of colours to
the vertices of G, in time polynomial in the size of G we can check that the assignment
uses at most k distinct colours and for every edge (u, v), it assigns u and v different
colours.
Consider any constant k ≥ 3. To reduce 3-Colourability to k-Colourability we
must show how, given a graph G, in polynomial time we can produce a graph G′ such
that G′ is k-colourable if and only if G is 3-colourable. To do this, we add k − 3 new
vertices to G, with edges between each new vertex and every other vertex (new or old).
(The rest of this answer is optional.)
Suppose G is 3-colourable: if we colour the old vertices with 3 colours and colour each
new vertex with a unique colour, then we use 3 + (k − 3) = k colours in total, so G′ is
k-colourable. Now suppose G′ is k-colourable: we must colour each of the new vertices
with a unique colour, so G must be 3-colourable.
8. Suppose you are given a dictionary of words and a pair of words w1 and w2 from that
dictionary and asked to find the shortest sequence of words from that dictionary that
starts with w1 and ends with w2 and in which each word (except the first, obviously)
can be obtained from the previous one by swapping one character. For example, if w1 =
hand and w2 = foot and the dictionary is the Ubuntu file /usr/share/dict/words,
then you could return hand, band, bond, fond, font, foot. Describe a clear and efficient
algorithm for finding such a sequence. You need not analyze your algorithm; it is ok
to use time proportional to the size of the dictionary.
We can view the dictionary as a graph whose vertices are the words, with an edge
between two words u and v iff it is possible to swap one character in u and get v. If
we perform a breadth-first search starting at w1, we’ll find the shortest path to w2.