CS 4470 - Theory of Algorithms P.

CS 4470 - Theory of Algorithms Midterm, Spring 1991

Work carefully. Show your work, and be sure that I can tell where your answers came from. Don't get stuck on any one problem - go on and come back ...

1. (15) Describe the general form of the divide and conquer method, and show the general recurrence relation for the expected running time of the algorithm.

2. (15) Describe the general form of the greedy method, and explain the typical approach toward proving that the result is optimal.

3. (15) Describe the method of dynamic programming. Explain what the principle of optimality is, and how it relates to dynamic programming. Give several examples to clarify what you say

4. (21) Solve the recurrence relations:
   1. T(n) = 3(T(n - 1)) + 1, T(1) = 1

   2. T(n) = 2(T(n / 3)),

   3. T(n) = 3(T(n / 3)) + n,

5. (16) Sort according to Big-Oh:

   

6. (10) Pascal does not include the operation of raising to a power. Therefore, if you want to raise integers to whole number powers, you need to write your own function. As a first attempt, one might write the function:

       function pow (x, n : integer) : integer;
   
            var i, temp : integer;
   
            begin
                 temp := 1;
                 for i := 1 to n do
                      temp := temp * x;
                 pow := temp
            end

   What is the approximate runtime of this function?

7. (15) Fortunately, there is a divide and conquer algorithm for calculating pow(x, n) which runs in O(log(n)) time. Develop the algorithm, write pseudo-code for it, and show that its run-time is log(n). (Assume n is always greater than or equal to zero and that is `small enough' with respect to the wordsize of your machine.)

• About this document ...