Consider common recurrence types in algorithm analysis: Decrease-by-One, Decrease-by-a-Constant Factor, and Divide-by-Conquer.

1. A decrease-by-one algorithm solves a problem by exploiting a relationship between a given instance of size n and a smaller instance of size n - 1. Specific examples include recursive evaluation of n! and insertion sort. The recurrence equation for finding the time efficiency of such algorithms has the following form:

T(n)= T(n - 1) + f(n),

Where function f(n) accounts for the time needed to reduce an instance to a smaller one and to extend the solution of the smaller instance to a solution of the larger instance.

Show     (a) T(n) = T(0) + ∑_j=1ⁿ f(j)

For a specific function f(x), the sum + ∑_j=1ⁿ f(j) can usually be either computed exactly or its order of growth ascertained.

(b)          if fin) =1,              ∑_j=1ⁿ f(j) = n.

(c)           if f(n) = log n,     ∑_j=1ⁿ f(j) εΘ(nlogn).

(d)          if f(n)= n^k             ∑_j=1ⁿ f(j) εΘ(n^k+1).

2. A decrease-by-a-constant-factor algorithm solves a problem by reducing its instance of size n to an instance of size nib (b = 2 for most but not all such algorithms), solving the smaller instance recursively, and then, if necessary, extending the solution of the smaller instance to a solution of the given instance. Examples include binary search, exponentiation by squaring, Russian peasant multiplication, and the fake-coin-problem. The recurrence equation for finding the time efficiency of such algorithms has the following form:

T(n) = T(n/b) + f(n),

where b > 1 and function f(n) accounts for the time needed to reduce an instance to a smaller one and to extend the solution of the smaller instance to a solution of the larger instance. Strictly speaking, this recurrence equation is valid only for n = b^k, k= 0, 1, 2,.....  For values of n that are not powers of b, there is typically some round-off, usually involving the floor and/or ceiling functions.

Show

(a) By considering n = b^k k= 0, 1, 2,..... , and applying backward substitutions to this recurrence equation,

T(n) = T(1) + ∑_j=1^k f(b^j)

For a specific function f(x), the sum ∑_j=1^k f(b^j)  can usually be either computed exactly or its order of growth ascertained.

(b)          if f(n)= 1, ∑_j=1^k f(b^j)  = log_bn.

(c)           If f(n)= n, ∑_j=1^k f(b^j)  = b(n-1)/b-1

3. A divide-and-conquer algorithm solves a problem by dividing its given instance into several smaller instances, solving each of them recursively, and then, if necessary, combining the solutions to the smaller instances into a solution to the given instance. Assuming that all smaller instances have the same size nib, with a of them being actually solved, we get the following recurrence valid for n = b^k, k = 0, 1, 2, .....

T(n) = aT(n/b) + f(n),

where a ≥ 1, b ≥ 2, and f(n) is a function that accounts for the time spent on dividing the problem into smaller ones and combining their solutions.

Show that the following formula is the solution to this recurrence for n = b^k,

T(n) = n^logba [ T(1) + ∑_j=1^logbn f(b^j)/a^j],

The order of growth of solution T(n) depends on the values of the constants a and b and the order of growth of the function f(n).

4. Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers 10011011 and 10111010.

5. Using backward substitution, find the solutions for the following relations

(a)          T(n) = 3T(n/2) + Θ(n), and

(b)          T(n) = T(n -I) + Θ(1).

6. You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time 0(n log n),

7. Here we look at an alternative algorithm based on divide-and-conquer.

(a)                                      - 2 gcd(a/2, b/2)      if a, b are even

                gcd (a, b) =          gcd(a, b/2)             if a is odd, b is even

                                          gcd((a - b)/2, b)      if a, b are odd

Show this rule is true.

(b) Give an efficient divide-and-conquer algorithm for finding greatest common divisor.

(c) How does the efficiency of your algorithm compare to Euclid's algorithm if a and b are n-bit integers? (in particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.)