Description
Question 1. (10 points) Consider the following simple algorithm for sorting an input array A[1 . . . n]
of n numbers. The algorithm first finds the smallest element of A and exchanges it with the element in A[1]. Then it finds the second-smallest element of A and exchanges it with A[2]. The
algorithm continues in this manner for the first n − 1 elements of A (i.e., continues for n − 1
iterations).
(i) Provide pseudocode for this algorithm. You do not need to prove correctness of this algorithm.
(ii) Give the worst case running time for this algorithm in Θ notation and justify your answer.
Question 2. (10 points) Suppose we want to compute the value x
y
, where x and y are positive
integers with m and n bits, respectively. One way to solve the problem is to perform y − 1 multiplications by x. Can you give a more efficient algorithm that uses only O(n) multiplication steps?
Question 3. (10 points) Given a positive real number c, show that the function g(n) = 1 + c +
c
2 + . . . + c
n
is (i) Θ(1) if c < 1, (ii) Θ(n) if c = 1, and (iii) Θ(c
n
) if c > 1.
Question 4. (10 points) Exercise 6 from Chapter 2, pages 68-69 of the textbook.