CS 601 Exam 2 Solution

CS 601 Exam 2 Solution

CS 601 Exam 2 Solution

Fall 2004

Solve any 5 of these 6 problems, or try all 6 for extra credit if you have time.

  1. Suppose you must take n specified courses to earn a college degree, and each course has a set of required prerequisite courses.Design an efficient greedy algorithm that determines the fewest number of semesters that would be needed to take all n courses, assuming that there is no limit to the number of courses you can take simultaneously.

S  {all n courses};

semester0;

while (S  empty set) {

semester++;

T  {courses in S that have no prerequisites in S};

take all courses in T simultaneously;

S  S - T;

}

return semester;

  1. You are given an array Athat contains n numbers, and you are also given a target value T. Design a (nlgn)-time greedy algorithm that determineswhether or not the array A contains any two elements A[i] and A[j]such thatA[i]+A[j]=T.

sort array A[1...n] into ascending order using merge sort;

// after sorting, the remainder of the algorithm takes only(nlgn)time:

i1;

j  n;

while (i < j) {

if (A[i]+A[j] < T)

i++;

else if (A[i]+A[j] > T)

j--;

else // (A[i]+A[j] == T)

return true;

}

return false;

Several peopletried to solve this problem using a non-greedy algorithm. If I could have anticipated this, then I would have re-stated the problem as follows to enforce that only a greedy approach could meet the specified time bound:

You are given an array A that contains n numbers which are arranged in ascending order, and you are also given a target value T. Design a (n)-time greedy algorithm that determines whether or not the array A contains any two elements A[i] and A[j] such that A[i]+A[j]=T.

  1. A sequence of n operations is performed on a data structure. The kth operation has a cost of k when k is an exact power of 2, and otherwise it has a cost of 1. Analyze the amortized cost per operation using any twoof these methods: (a) aggregate, (b) accounting, (c) potential. Specify whichtwomethods you choose.

This problem has same analysis as the dynamic table data structure, with expansion due to overflow on insertion, but without contraction due to underflow on deletion.

a)Aggregate method: Total cost ≤ 1≤ k ≤ n1 + 1 ≤ j ≤ lg n 2j≤n + (2lg n)/(1-1/2)≤n + 2n=3n. So amortized cost ≤ 3n/ n = 3 = (1).

b)Accounting method: Charge $3 per operation. When k is not a power of 2, use $1 to pay for the operation, and place the extra $2 in an account. The account balance will always be at least $2 times the number of operations since the most recent power of 2. When k is a power of 2, the most recent power of 2 was k/2, so the balance is at least $2 * ((k-1) - (k/2)). This amount plus the $3 charge is more than enough to pay for the operation. So amortized cost ≤ 3 = (1).

c)Potential method: Define 0 = 1 = 0 and k = 2* (k – 2  lg k  ) for k ≥ 2. Intuitively, the potential is 2 times the number of operations since the most recent power of 2. Note that k ≥ 0 for all k. When k is not a power of 2, amortized cost = 1 + k-k-1 = 1 + 2*(k – 2  lg k  ) - 2*((k-1) – 2  lg (k-1) ) = 2*(k – 2  lg k  ) - 2*((k-1) – 2  lg k ) = 3. When k is a power of 2, amortized cost = k + k-k-1 = k + 2*(k – 2  lg k  ) - 2*((k-1) – 2  lg (k-1) ) = k + 2*(k – 2lg k) - 2*((k-1) – 2 lg (k/2)) = k + 0 –2*(k-1 - k/2)=2. So amortized cost ≤ 3 = (1).

  1. First determine the worst-case running time of algorithm A as a  function of n. Next determine the total running time of algorithm B as a  function of n. Justify each answer.

A(n)
if (n mod 2 == 1) return n;
else returnA(n/2); / B(n)
for k  1 to n do
print A(k);

Consider algorithm A. Suppose there are j calls to A before the recursion stops. This can only happen if n/2j 1, so we knowj ≤ lg n, and hence TA(n) = (lg n). The worst case occurs when n is a power of 2.

Consider algorithm B. For n/2 values of k (the odd values), A is only called 1 time before the recursionstops. For n/4 values of k, A is called exactly 2 times. For 1 ≤ j ≤ lg n, there are n/2j values of k for which A is called exactly j times. Therefore TB(n) ≤ 1 ≤ j ≤ lg n n/2j* j≤ 1 ≤ j ≤ 1 ≤ i ≤jn/2j=1 ≤ i ≤i ≤ j ≤  n/2j=1 ≤ i ≤ 2n/2i= 2n = (n).

  1. Trace the sequence of operations below, using a disjoint set forest with union by rank and path compression. Assume there are initially 16 sets {1},{2},…,{16}. Draw the data structure both immediately before and after the Find_Set operation.

for (i=1; i<=16; i+=2)Union(i+1,i); //ibecomes thenew root
for (i=1; i<=16; i+=4)Union(i+2,i);
for (i=1; i<=16; i+=8)Union(i+4,i);
Union(9,1); // draw the forestdata structure after allUnions
Find_Set(16); // draw the forestdata structure after Find_Set

Everybody got this one mostly correct, so it’s not necessary to draw the trees here.

  1. Here is a recursive version of Find_Set with path compressionas given in the textbook. Write an equivalent algorithm that is non-recursive.

Find_Set(x)
if x  parent[x] then
parent[x]  Find_Set(parent[x]);
return parent[x];

Find_Set(x)

r  x;

whiler parent[r] do

r parent[r];

// nowr is the root node

whiler parent[x] do {

pparent[x];

parent[x]  r;

x p;

}

return r;