Computer Science 3650
Spring 2015
Practice Questions for Quiz 2

1. To within a constant factor, what is a solution to recurrence T(n) = 2T(n/2) + √n?

   Answer

2. Suppose that A = [a_{i, j}] and B = [b_{i, j}] are two n×n matrices. (Notation A = [a_{i, j}] is just a way of saying that the entry in row i and column j of A is a_{i, j}.) The matrix product C = AB is an n×n matrix defined by C = [c_{i, j}] where c_{i, j} = ∑ⁿ_k=1a_{i, k}b_{k, j}.

   Notice that there are n² entries of matrix C to compute. Each involves computing a sum of n products of numbers.

   Can we argue that computing the product of two n×n matrices requires time Θ(n³) time based on this?

   Answer

3. What is the worst case time for quicksort, to within a constant factor, in terms of n, the number of items to be sorted?

   Answer

4. What is the best case time for quicksort, to within a constant factor?

   Answer

5. Larry has developed an algorithm that sorts an array, and his analysis concludes that it takes O(n^0.95log²(n)) time to sort an array of n numbers. Show that either Larry's algorithm does not work or that his analysis is wrong.

   Answer

6. Suppose that an algorithm performs f(n) steps, and each step takes g(n) time. How long does the algorithm take?

   Answer

7. A particular divide-and-conquer algorithm, when run on an input of size n, works by spending O(n) time splitting the problem in half, then does a recursive call on each half, then spends O(n²) time combining the solutions to the recursive calls. On small inputs, the algorithm takes a constant amount of time. To within a constant factor, how long does this algorithm take, in terms of n?

   Answer

8. Describe an algorithm that takes a list of n different numbers and an integer k. It yields a list of the k smallest members of the list. It must take O(n) time.

   Answer