CIS-610 Data Structures and Algorithms

Home Work #3							Due:	10/07/1999


1. Write an iterative algorithm to evaluate a * b by using addition, where a and b are nonnegative integers.

2. Let a be an array of integers. Present recursive algorithm to compute:
a. The maximum element of the array.
b. The product of the elements of the array.
c. The average of the elements of the array.

3. Assume that an array of ten integers contains the elements
1, 3, 7, 15, 21, 22, 36, 78, 95, 106
       Use the recursive binary search to find each of the following items in the array.
a. 1
b. 98

4. The expression m % n yields the remainder of m upon division by n. Define the greatest common divisor (GCD) of two integers x and y by

gcd(x, y) = y			if (y <= x && x % y == 0)
gcd(x, y) = gcd(x, y)		if (x < y)
gcd(x, y) = gcd(y, x % y)		otherwise

       Write a recursive function to compute gcd(x, y). Find an iterative method for computing this function.

5. Let common(n, k) represent the number of different committees of k people that can be formed, given n people from whom to choose. For example, common(4, 3) = 4, since given four people A, B, C, and D there four possible three-person committees: ABC, ABD, ACD, and BCD. Prove the identity:

common(n, k) = common(n - 1, k) + common(n - 1, k - 1)

Write and test a recursive program to compute common(n, k) for n, k >= 1.
 
6. Write a recursive program to sort an array a as follow:
a. Sort the elements up to and including a[k]
b. Sort the elements past a[k]

7. Write a recursive routine to find the kth smallest element of an array a of numbers by choosing any element a[i] of a and partitioning a into those elements smaller than, equal to, and greater than a[i].

8. Develop a recursive method to compute the number of different ways in which an integer k can be written as a sum, each of whose opernad is less than n.

9. Write a nonrecursive routine of function find.