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.

   

   a b c

   3 4 3

   d 6

   1. e f g

      h 10 3

   2. i j

      1 2

      1

      k

      (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.

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 Sr = (wr , pr ), . . . , (wr ′ , pr ′ ) of S such that

   1 1 |S | |S |

   w

   Σ

   i

   r ≤ C

   Σ

   1≤i≤|S′|

   p

   r

   i

   1≤i≤|S′|

   ≥ 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 Sr = (wr , pr ), . . . , (wr ′ , pr ′ ) of S with |Sr| ≤ m

   such that

   1 1 |S |

   |S |

   w

   p

   Σ

   i

   i

   r ≤ ci for i ∈ Sr r ≥ T .

   1≤i≤|S′|

   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 Sr = (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

   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 Sr 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 Sr 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 Sr is at least that of S, so Sr 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

    min(A[i − 1][j] + 1, A[i − 1][j − 1], A[i][j − 1] + 1)

   A[i][j] =  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.

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 Gr on nr = 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 Gr if

   1. we colour each copy of G according to C;

   2. in the second copy of G, we make all the red vertices green, all the green vertices yellow and all the yellow vertices red;

   3. 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 nr/3 = n vertices of each colour in Gr.

   Now suppose there is a fair 3-colouring Cr of Gr. Then each copy of G in Gr is 3-coloured by Cr.

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.

   0

   3

   3

   4

   2

   1

   2.4

   2

   2

   3

   4.8

   0.5

   0.8

   3

   1

   2.4

   2

   0.4 2

   7.2

   2

   4

   1

   4

   1.6

   1 0.8

   2

   1.6

   

   s

   (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.