Exam 3, Sample 1

70 Minutes

Solutions

(a)
For each i, in the order 1, 2, ..., n, set x[i] to be the store from which item i can be bought at the least cost from among the stores from which no item has been bought so far. Ties are broken arbitrarily.
(b)
The procedure does not guarantee optimal solutions. Consider the case when both n and m are 2 and the cost matrix is
```
3 6
4 20
```
The greedy algorithm purchases item 1 from store 1 and item 2 from store 2 at a cost of 23. If we purchase item 1 from store 2 and item 2 from store 1, the cost is only 10.
(a)
If n < 1, there is no maximum element. If n = 1, the single element is the maximum. If n > 1, divide the elements into two groups; one group has ceil(n/2) elements and the other has the remaining elements. Find the maximum of each group recursively. Then compare the two maximums and return the larger element. Break ties arbitrarily.
(b)
To make the analysis easy, assume that n is a power of 2. Let c(n) denote the number of element comparisons. We see that c(n) is 0 when n < 2 and is 2c(n/2)+1 when n >= 2. Using repeated substitution, we get
c(n) = 2c(n/2)+1 = 4c(n/4) + 2 + 1 = ... = nc(0) + n/2 + n/4 + ... + 1 = n - 1

The number of comparisons made by the divide-and-conquer algorithm is the same as that made by the simple algorithm. However, the overhead is higher because of the splitting into two parts at each level of recursion and the recursive function calls. Therefore, we do not expect the divide-and-conquer algorithm to outperform the simple algorithm.
(a)
Observe the longest path starts at some vertex and ends at some vertex. If for each vertex i, we know the length, L[i], of the longest path that starts at this vertex, we can compute the length of the longest path in the graph by computing the maximum of the L[i]s. For L[i], we obtain the following recurrence
L[i] = 0 if S(i) is empty; otherwise L[i] is max{length[i][j] + L[j] | j is in S(i)}.

Using this recurrence and the fact that the graph is acyclic and the vertices are numbered as stated, we arrive at the following algorithm:
```
MaxLength = 0;
for (int i = n; i > 0; i--) {
   L[i] = 0;
   for (each vertex j in S(i))
      L[i] = max(L[i], length[i][j] + L[i]);
   MaxLength = max(MaxLength, L[i]);
   }
```
(b)
The total time spent in the inner loop is Theta(n+e). The rest of the algorithm takes Theta(n) time. So the overall complexity is Theta(n+e).
(a)
The solution space is a subset space. We are looking for a subset of the vertices whose removal from the graph causes the graph to become acyclic. A solution may be described by the array x[] where x[i] is 1 if vertex i is in the subset of deleted vertices and 0 if it is not in this subset.
(b)
The solution space members are {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}
(c)
The tree organization is given in Figure 16.2 of the text.
(d)
Assume that left children are moved to before right ones. Using the vertex labels given in Figure 16.2, the nodes are reached in the order A, B, D, H, I, E, J, K, C, F, L, M, G, N, O.