Tutorial #6 solutions – CPSC 320 2017W2

Please refer to the solutions to the week 5 tutorial questions.
- Change the weights of the edges on the example as follows: w(clk, a) = w(d,e) = w(d,f) = 2, and w(clk, d) = w(a, b) = w(a, c) = 1. The proposed algorithm increases every edge weight to 2, but there was no need to change any of the weights.
- Because there is a unique path from the root of the tree to a given node N, the requirements that the resulting tree have zero skew means the subtree rooted at every node N must also have zero skew. The algorithm can thus be summarized as follows:
  - We perform a post-order traversal of the tree to compute, for each node N, the length of the longest path L(N) from N to a leaf.
  - Once this computation has been performed, we adjust either the edge leading to the left child of N, or the edge leading to its right child, to eliminate the skew in N‘s subtree.
  Here is pseudo-code for the algorithm; let us denote by l(N1, N2) the length of the edge that connects two nodes N1, N2 of the tree. We can store the values L[?] in a dictionary, or as an additional field inside the nodes.
```
Algorithm adjustSkew(N)
    L[N] ← 0

    if N has a left child LN then
        adjustSkew(LN)
        L[N] ← L[LN] + l(N, LN)

    if N has a right child RN then
        adjustSkew(RN)
        L[N] ← max { L[N], L[RN] + l(N, RN) }

    if N has two children LN, RN then
        l(N, LN) ← L[N] - L[LN]
        l(N, RN) ← L[N] - L[RN]
```
The trick is to notice that people who know less than five other people can not be part of the subset Alice wants, nor can people who know at least n-5 other people. So the algorithm is the following:
```
Algorithm PickSubset(S)
    while an element x of S knows fewer than 5 or more than |S| - 5 people
        remove x from S
    endwhile

    return S
```
Note that when we write “knowing fewer than 5 or more than |S| – 5 people”, we mean with respect to the current set S, not the set the algorithm started with.

Proof of correctness (not required for the tutorial): Let S_i denote the set S at the end of the ith iteration of the while loop. We prove by induction on i that the optimal solution to Alice’s problem is a subset of S_i.

The base case is the case i = 0, before the first iteration of the while loop. At that point, S₀ contains every person Alice has to choose from, and hence contains every member of the optimal solution.

Let us now consider the induction step. Suppose the statement was true after the ith iteration of the loop, and consider now the set S_i+1. A person x removed from S_i to obtain S_i+1 either knows fewer than 5 other people in S_i, which means he/she does not know enough people in the optimal subset to be invited, or he/she knows more than |S_i| – 5 people in S_i, which means there are not enough people in the optimal subset that he/she does not know. In both cases x can not be part of the optimal solution, and hence the optimal solution must also be a subset of S_i+1.

This completes the induction step. Now, when the while loop finally exits after t iterations, every person in S_t knows at least 5 other people, and there are at least 5 other people that he/she does not know. Hence either S_t is empty, or it is a possible solution to Alice’s problem. Because we proved that the optimal solution is a subset of S_t, this means that S_t is the optimal solution we were looking for.