CSCI 3110 Midterm 2 Solutions 8.11.2019
Topics: algorithms with data structures, minimum spanning trees, NP-completeness
1. (2 marks) In 1976 Jan van Leeuwen proved the following:
Suppose we have one queue Q1 containing the elements
{x1, . . . , xn} of a multiset X in sorted order, with the smallest at Q1’s head
and the largest at its tail, and another queue Q2 that is initially empty. If
we repeatedly dequeue the two smallest elements in either queue and then
enqueue their sum in Q2, then at all times the contents of both Q1 and Q2
are sorted.
(If you’re curious why this is true, notice we never enqueue in Q1, so we don’t disrupt
its sortedness. Suppose we enqueue in Q2 an element xj that is the sum of two elements
xc and xd, after we enqueue in Q2 an element xi that is the sum of two elements xa
and xb. Since we dequeued xa and xb earlier than xc and xd, we know xa, xb < xc, xd,
so xi = xa + xb < xj = xc + xd.)
Use Van Leeuwen’s result to rewrite Huffman’s algorithm such that it runs in linear
time when given a sorted list of weights.
Solution: For each weight, make a vertex with that weight. Enqueue each vertex in
Q1, from lightest to heaviest. Until there is only one vertex left in either queue, do the
following:
(a) dequeue the lightest vertex u (which is at the head of one of the queues),
(b) dequeue the second lightest vertex v (which at the head of one of the queues after
u is dequeued),
(c) make u and v the children of a new vertex w whose weight is the sum of their
weights,
(d) enqueue w in Q2.
Return the sole remaining vertex as the root of the Huffman tree.
1
2. (2 marks) List the edges in a minimum spanning tree of the graph in Figure 1 in the
order Prim’s algorithm would select them, starting at vertex a.
a
b c d
e
fgh
i
4
8
1
11
7
2
8
6
4 14
7
2
10
9
Figure 1: An edge-weighted graph.
Solution: There are several ways Prim’s algorithm could build a minimum spanning
tree, depending on how it breaks ties. For example, it could run as shown in the
textbook:
2
3. (2 marks) Modify Kruskal’s algorithm such that it still runs in O(m logm) time, where
m is the number of edges, but if any edge in the graph is later deleted — say that road
is washed away or something — then you can fix the minimum spanning tree in O(m)
time.
Solution: When you first build the minimum spanning tree T , keep the sorted list L
of all the edges and mark in L which edges are in T . Later, when you have to delete
an edge e, run through L until your find it and, if it is not marked, just delete it from
L. If e is marked, delete it from L and T , breaking T into to subtrees, T1 and T2.
Colour all the vertices in T1 red and all the vertices in T2 blue. Run through L from
the lightest to the heaviest edges until you find an edge e′ with one red endpoint and
one blue endpoint, then add e′ to T and mark it in L.
4. (2 marks) Recall that for the NP-complete problem HamPath we are given a graph
G and asked if there is a path in G that visits each vertex exactly once. Now consider
the problem Longest Path, for which we are given a graph G and an integer k and
asked if there is a non-self-crossing path of length at least k in G. Show that Longest
Path is NP-complete by
(a) showing it is in NP;
(b) showing that HamPath reduces to it in polynomial time.
(After the midterm, you can relax by listening to the song “Find the Longest Path”
https://www.youtube.com/watch?v=a3ww0gwEszo
sung to the tune of Billy Joel’s “For the Longest Time”. I think the line “is of poly-
nomial degree” is mistaken, though.)
Solution: To see that Longest Path is in NP, consider that if someone gives you a
list of k edges (i.e., pairs of vertices in G), in polynomial time you can check that
• each edge is in G,
• the edges form a path (i.e., the second endpoint in each edge is the first endpoint
in the next edge),
• the path is non-self-crossing (i.e., after it visits a vertex, it never returns to that
vertex).
We can reduce HamPath to Longest Path as follows: given a graph G on n vertices
as an instance of HamPath, we turn it into an instance (G, n−1) of Longest Path.
If G has a Hamiltonian path P then P is a non-self-crossing path of length n− 1; if G
has a non-self-crossing path P ′ of length n− 1 then P ′ visits every vertex and thus is
Hamiltonian.
3
5. (2 marks) For the problem Integer Linear Programming (ILP) we are given a
set of numeric variables and a set of linear equalities and inequalities and asked if it
is possible to choose integer values for the variables such that all those equalities and
inequalities are satisfied. (You may have heard that Linear Programming is in
P, but that doesn’t require the values of the variables to be integers.) For example,
the following set of inequalities has solutions — e.g., x = y = 1.5 — but none in the
integers: y ≤ x + 0.9 y ≤ −x + 3.9
y ≥ x− 0.9 y ≥ −x + 2.1
We can reduce 3-Sat to ILP in polynomial time as follows: given a Boolean formula
in 3-CNF with variables x1, . . . , xn, for each variable xi we create two variables pi and
ni (for “positive” and “negative”) and write constraints ensuring exactly one is 0 and
the other is 1; for each clause we write a constraint ensuring that at least one of its
literals is true. For example,
(x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x3)
becomes
0 ≤ p1 p1 ≤ 1 0 ≤ n1 n1 ≤ 1 p1 + n1 = 1
0 ≤ p2 p2 ≤ 1 0 ≤ n2 n2 ≤ 1 p2 + n2 = 1
0 ≤ p3 p3 ≤ 1 0 ≤ n3 n3 ≤ 1 p3 + n3 = 1
p1 + n2 + p3 ≥ 1
n1 + p2 + p3 ≥ 1 .
The set of constraints has the integer solution p1 = 0, n1 = 1, p2 = 0, n2 = 1, p3 =
1, n3 = 0, for example, because setting x1 and x2 to false and x3 to true satisfies the
formula.
Give a polynomial-time reduction from Vertex Cover to ILP.
Solution: There are at least two ways to do this, direct and indirect.
Suppose we are given an instance of Vertext Cover consisting of a graph G on
vertices v1, . . . , vn and an integer k. For each vertex vi in G, we add the inequalities
0 ≤ xi and xi ≤ 1. For each edge (vi, vj) in G, we add the inequality xi + xj ≥ 1.
Finally, we add the inequality x1 + · · ·+ xn ≤ k.
If there is a vertex cover of G of size at most k, then our integer linear program has
a solution in which xi = 1 if and only if vi is in that cover. Conversely, if our integer
linear program has a solution then G has a vertex cover of size at most k which includes
vi if and only if xi = 1 in that solution.
You can also just say that we can reduce Vertex Cover to 3-Sat in polynomial time
by Cook’s Theorem, I just gave you a polynomial-time reduction from 3-Sat to ILP,
and the composition of those reductions is a polynomial-time reduction from Vertex
Cover to ILP.
4
(Originally for this question I just defined ILP and told you to reduce some NP-
complete problem we’ve seen in class to it. Norbert said no one would get that, so I
added the example reduction from 3-Sat. Yes, I knew that opened up the loophole
allowing the indirect answer, but I figured anyone who caught that deserved the marks.)
5