Algorithms Mid-term Exam        April 19, 1999

1. Define the following terms:
    1) Randomized algorithm  (3%)
    2) Las Vegas algorithm   (3%)
    3) Monte Carlo algorithm (3%)
    4) ~O(g(n))              (6%)  p.s. '~' is on the top of 'O'

2. T(n) <= 2T(n/2) + cn log(n)
   Prove: T(n) = O(n(log(n))^2)         (10%)

3. The closest-pair problem is to find the two points that are closest
   together among a set of points in the plane. Informally describe a
   divide-and-conquer algorithm to solve this problem.
   The time complexity of your algorithm may satisfy the recurrence
   relation in problem 2.               (15%)

4. Sketch the process of a greedy algorithm in solving the job sequencing
   problem below.
   (p1, p2, p3, p4, p5, p6, p7) = (3, 5, 20, 18, 1, 6, 30)
   (d1, d2, d3, d4, d5, d6, d7) = (1, 3,  4,  2, 2, 1,  2)      (10%)


5. Here is a resource allocation problem:
        3 projects, 3 units of resource,
        N(i, j) = profit resulting from allocating j units of resource
                  to project i.
        N(1, 1) = 1, N(1, 2) = 2, N(1, 3) = 3
        N(2, 1) = 2, N(2, 2) = 2, N(2, 3) = 3
        N(3, 1) = 2, N(3, 2) = 3, N(3, 3) = 3
   1) Represent the problem as a multistage graph.      (10%)
   2) Write the recurrence relation for the multistage graph problem and
      solve the problem in part 1) step by step.        (10%)

6. Show how you use set approach dynamic programming to solve the following
   0/1 knapsack problem step by step and give your answer to the problem.
        m = 20
        (u1, u2, u3, u4) = (10, 15, 6, 9)
        (p1, p2, p3, p4) = ( 2,  5, 8, 1)               (10%)

7, Let A and B be matrices of dimension m*n and n*p respectively. The
   product C = A*B an m*p matrix, can be computed using mnp multiplications.
   Let M1*M2*...*Mr be a chain of matrix products, where Mi, 1 <= i <= r,
   has dimension D(i-1)*D(i) (i.e. D(i-1) rows and D(i) columns). Let Mij
   denote the product Mi*Mi+1*...*Mj and C(i, j) be the cost of obtaining
   an optimal product sequence for Mij. Observe that C(i, i) = 0,
   1 <= i <= r, and that C(i, i+1) = D(i-1)D(i)D(i+1), 1 <= i < r.
   1) Give the recurrence relation for C(i, j), i < j   (10%)
   2) Sketch (or describe) how to solve the recurrence relation for C(1, r).
      Your algorithm should be of complexity O(r^3).    (10%)