College of Computer & Information Science Spring 2005 Northeastern University Handout 2 CSU690: Algorithms and Data 10 January 2005

Problem Set 1 (due Wednesday, January 19)

1. (6 points) Twenty questions

A friend challenges you to find out a positive integer number n that she has on her mind. For any guess you make, she is willing to tell you which of the following three possibilities is true: n is less than, greater than, or equal to your guess. You have no clue as to how large n is and would like to determine n with the smallest number of guesses.

Describe a guessing procedure for determining n. What is the number of guesses your procedure makes, as a function of n? You must aim at keeping this function as small as possible.

2. (1 + 5 + 5 + 3 = 14 points) Bubblesort

Problem 2-2, page 38.

3. (1 + 3 + 6 = 10 points) Inversions and insertion sort

Parts (a) through (c), Problem 2-4, pages 39-40.

Hint for part (c): If T (A) is the running time of insertion sort on input A and I(A) is the number of inversions in A, then prove that T (A) is Θ(I(A) + n).

4. (10 points) Ordering functions

Arrange the following functions in order from the slowest growing function to the fastest growing function. Briefly justify your answers. (Hint: It may help to plot the functions and obtain an estimate of their relative growth rates. It may also help to express each function as a power of 2 and then compare.)

n^{1/2} n^{2} + lg n n(lg n)^{5} (lg lg n)^{2} lg n

5. (3 + 3 + 4 = 10 points) Properties of asymptotic notation

Let f(n), g(n), and h(n) be asymptotically positive and monotonically increasing functions. Prove or disprove each of the following conjectures.

(a) f(n) + g(n) = Θ(min{f(n), g(n)}).

(b) If f(n) = O(h(n)) and g(n) = Ω(h(n)), then f(n) = O(g(n)).

(c) f(n^{2}) = Ω((f(n))^{2}).