CSCI 3110 Final Exam posted: 7 am ADT 31.07.2020
Instructor: Travis Gagie due: midnight ADT 31.07.2020
1. Describe a polynomial-time divide-and-conquer algorithm that, given a tree T with a
weight assigned to each vertex, returns a vertex cover with minimum total weight. For
example, in the tree shown below, the vertex cover with the minimum total weight is
d, f, g, h, i, k — even though the smallest vertex cover is e, g, i. You need not prove
your algorithm correct.
3
6
3 4 3
1
a b c
d
e
f g
h
i j
10
2
k
1
2
3
(Hint: Because (e, f) is an edge in the example, any vertex cover includes either e
or f or both. Removing (e, f) splits the tree into two pieces, Te including e and Tf
including f . If you can work out the weight w1 = 6 of the lightest vertex cover of
Te, and the weight w2 = 10 of the lightest vertex cover of Te that includes e, and the
weight w3 = 7 of the lightest vertex cover of Tf , and the weight w4 = 10 of the lightest
vertex cover of Tf that includes f , then the weight of the lightest vertex cover of T is
min(w1 + w4, w2 + w3) = 16. How do you work out w1 and w3? More interestingly,
how do you work out w2 and w4?)
Idea: If T is a single vertex, return the empty set. Otherwise, pick an edge (u, v) and
remove it. Let Tu be the remaining component containing u, let Tv be the remaining
component containing v, let Fu be the forest that results from deleting u and all its
incident edges from Tu, and let Fv be the forest that results from deleting v and all its
incident edges from Tv.
Recursively find the lightest vertex covers C(Tu), C(Tv), C(Fu) and C(Fv) of Tu, Tv,
Fu and Fv, respectively. (To find C(Fu) and C(Fv), recurse on all the trees in Fu and
union the results and on all the trees in Fv and union the results.) Return whichever
of C(Tu) ∪ {v} ∪ C(Fv) and C(Fu) ∪ {u} ∪ C(Tv) is lighter.
1
2. Recall that for the NP-complete problem Knapsack we are given a sequence S =
(w1, p1), . . . , (wn, pn) of weight-profit pairs, a target T and a capacity C, and asked if
there exists a subsequence S ′ = (w′1, p
′
1), . . . , (w
′
|S′|, p
′
|S′|) of S such that∑
1≤i≤|S′|
w′i ≤ C
∑
1≤i≤|S′|
p′i ≥ T .
For the problem Pockets we are again given a sequence S = (w1, p1), . . . , (wn, pn) of
weight-profit pairs and a target T but now, instead of a single capacity C, we are given
a sequence C = c1, . . . , cm of capacities. Assume w1 ≥ · · · ≥ wn and c1 ≥ · · · ≥ cm. We
are asked if there exists a subsequence S ′ = (w′1, p
′
1), . . . , (w
′
|S′|, p
′
|S′|) of S with |S
′| ≤ m
such that
w′i ≤ ci for i ∈ S ′∑
1≤i≤|S′|
p′i ≥ T .
In other words, we have n items and m pockets, each pocket has a capacity, and we
want to put at most one item in each pocket so as to obtain total profit at least T
without overfilling any pocket.
Describe a polynomial-time greedy algorithm for Pockets. For example, if
S = (7, 8), (5, 5), (5, 6), (5, 2), (4, 1), (4, 4)
T = 13
C = 6, 5, 5
then your algorithm should return “yes”, since with S ′ = (5, 5), (5, 6), (4, 4) we obtain
profit 5 + 6 + 4 = 15 without overfilling any pocket (since 5 ≤ 6, 5 ≤ 5 and 4 ≤ 5).
You need not prove your algorithm correct (although looking for a proof is a good way
to catch mistakes anyway).
(Hint: Assuming the pockets are sorted in decreasing order by capacity made it easier
to state the problem, but it’s not the best order for solving it. What should you put
in the smallest pocket?)
Idea: We consider the pockets in increasing order by capacity and, in each pocket,
put the most profitable remaining item that fits. This is all the students have to say
but it’s pretty easy to see why it’s correct, so some of them may give a proof anyway.
Before we fill any pocket, our empty subsolution can be extended to an optimal solution.
Assume our subsolution after i steps — i.e., after we’ve filled i pockets — can be
extended to an optimal solution S. If S also puts in the (i + 1)st pocket the most
2
profitable remaining item x that fits, then our subsolution after i + 1 steps can also
be extended to S. Suppose S doesn’t put x in the (i + 1)st pocket. If S puts x in a
later pocket then we can change S by swapping the contents of the (i + 1)st pocket
and of that later pocket (i.e., x), to obtain an optimal solution S ′ that extends our
subsolution after i+ 1 steps. If S doesn’t put x in a later pocket then we can change S
by replacing the contents of of the (i+1)st pocket, to obtain a solution S ′ that extends
our subsolution after i+ 1 steps; since x is the most profitable remaining item that fits
in the (i + 1)st pocket, the total profit of S ′ is at least that of S, so S ′ is also optimal.
By induction, we find an optimal solution.
3. A semi-wildcard in a string is special character representing a non-empty subset of
the normal alphabet, and a string containing a mix of normal characters and semi-
wildcards represents the set of all normal strings that can be obtained by replacing
each semi-wildcard by a character from the subset it represents. For example, if the
normal alphabet is {A, B, C, D} and S = BA?C!AD with ? representing {B, D} and !
representing {A, D}, then S represents the set {BABCAAD, BABCDAD, BADCAAD, BADCDAD}.
Describe a polynomial-time dynamic-programming algorithm that, given a string S[1..n]
containing a mix of normal characters and semi-wildcards and a normal string T [1..m],
computes
min{ED(S, T ) : S ∈ S}
where ED(S, T ) denotes the edit distance between S and T . For example, given S =
BA?C!AD as described above and T = BADCAD, your algorithm should return 1, since the
edit distance from either BADCAAD or BADCDAD and BADCAD is 1. Notice that in general
the set of strings represented by S can contain exponentially many strings, so trying
them one by one is not feasible! You need not prove your algorithm correct.
(Hint: This questions isn’t as hard as it sounds at first. Start with the “grid with
diagonal arrows” idea we saw in class and add some more arrows in some rows.)
Idea: Following the “grid with diagonal arrows” approach, we draw an (m+1)×(n+1)
grid with rows and columns numbered 0 to m and 0 to n. We draw an arrow from
cell (i, j) to cell (i + 1, j + 1) if S[i] is a normal character equal to T [j], or if S[i] is
a semi-wildcard representing a set that contains T [j]. We then compute the distance
from the top left corner to the bottom right corner when moving down or right costs
1, and moving diagonally down and right costs 1 if there is no arrow or 0 if there is.
Formally, we fill in a matrix A[0..m][0..n] by setting A[0][0] = 0, A[i][0] = i for i > 0
and A[0][j] = j for j > 0, and then using the recurrence
A[i][j] =
min(A[i− 1][j] + 1, A[i− 1][j − 1], A[i][j − 1] + 1)
if T [j] = S[i] or T [j] ∈ S[i],
min(A[i− 1][j] + 1, A[i− 1][j − 1] + 1, A[i][j − 1] + 1)
otherwise.
3
4. For the problem Fair 3-Colourability we are given a graph G on n vertices and
asked if it is possible to colour exactly n/3 vertices red, exactly n/3 vertices green and
exactly n/3 vertices yellow such that no vertex shares an edge with a vertex of the
same colour. Show that Fair 3-Colorability is NP-complete by both showing it is
in NP and reducing a known NP-complete problem to it.
(Hint: Don’t reduce from 3-Sat again; it’s easier than that.)
Idea: Fair 3-Colourability is in NP because, given a colouring of G we can check
in polynomial time that exactly n/3 vertices are red, exactly n/3 vertices are green,
exactly n/3 vertices are yellow and no vertex shares an edge with a vertex of the same
colour.
We reduce 3-Colourability to Fair 3-Colourability. Suppose we are given
a graph G on n vertices as an instance of 3-Colourability. We make a graph
G′ on n′ = 3n vertices that consists of 3 copies of G, as an instance of Fair 3-
Colourability.
Suppose there is a 3-colouring C of G. Then we can obtain a fair 3-colouring of G′ if
(a) we colour each copy of G according to C;
(b) in the second copy of G, we make all the red vertices green, all the green vertices
yellow and all the yellow vertices red;
(c) in the third copy of G, we make all the red vertices yellow, all the green vertices
red, and all the yellow vertices green.
Since each vertex in G is red in one copy, green in another and yellow in the third,
there are exactly n′/3 = n vertices of each colour in G′.
Now suppose there is a fair 3-colouring C ′ of G′. Then each copy of G in G′ is 3-coloured
by C ′.
5. Describe a polynomial-time algorithm that, given a directed acyclic graph G with a
positive weight assigned to each edge, finds the minimum distance from s to each other
vertex when the length of a path is defined to be the product of the weights along that
path, instead of their sum. Can you find a faster algorithm if all the edge weights are
at least 1? For example, the distances from s to the other vertices are shown in the
graph below. You need not prove your algorithm(s) correct.
2
3
1
4
2
4
3
0.4 2
1
1
2
2
2
3
4
0.5
1
30
2
0.8
1.6
0.8
2.4
7.2
4.8
2.4
1.6
s
4
(Hint: You can solve this either by modifying algorithms you already know or by
reducing to the problems they solve.)
Idea: The two ways to do this with positive weights are either to change the Bellman-
Ford algorithm to use products instead of sums, which isn’t hard but is a mess, or to
replace each edge weight by its logarithm, run Bellman-Ford, and then replace each
distance by c to that distance, where c is the base of the logarithm (which the students
can choose however they like). Similarly, to get a faster algorithm when all the weight
are at least 1, they can either modify Dijkstra’s algorithm to use products instead of
sums, or do the same reduction but using Dikstra’s algorithm instead of Bellman-Ford.
6. Suppose that due to various catastrophes, next semester your professor ends up teach-
ing both 3110 and 3136 with exactly the same n students in each one; the 2-hour final
exams are scheduled back to back; both exams are in the same room with exactly n
immovable, arbitrarily placed desks; and that room is available only for those 4 hours.
The pandemic is over, so at least your professor doesn’t have to worry about social
distancing, but he still doesn’t want students writing the same exam to be sitting
within two meters of each other. Some of the desks are too close together, so he can’t
have all the students write the same exam at the same time, but he decides to have
some students start with the 3110 exam and others start with the 3136 exam, and
then switch halfway through. However, even this won’t work if, for example, there’s
a triangle of three desks with each one within 2 meters of the other two. Describe
a polynomial-time algorithm that lets your professor check if his idea works with the
room’s seating arrangement.
Bonus (1 mark): What if in the winter semester your poor professor is in the same
situation but with three exams in six hours? What about four exams in eight hours
(perish the thought)?
(Hint: You should be able to find the algorithm for two exams by yourself, but for
three or more, Google “unit disk graph ???”, where ??? is the standard name for this
problem.)
Idea: This is just graph colouring, where the number of colours is the number of
exams. For two exams it’s easy, via BFS, but for three or more colours it’s NP-
complete, according to https://doi.org/10.1007/PL00009196.
5
https://doi.org/10.1007/PL00009196