Mini #1, 15451 Fall 2012
========================
This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 4.
Please use the subject line "15-451 MINI #1" in your email.
Problem 0: Sign into the piazza discussion board system, using your
andrew ID (so your TA can check off that you did it).
Problem 1: Suppose f(n) = O(g(n)) and g(n) = O(h(n)). Does that imply
that f(n) = O(h(n))? Explain why or give a counterexample.
Problem 2: For each pair of functions below, list which of the
following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) =
o(f(n)).
(a) f(n) = n*ln(n), g(n) = n*lg(n). ["ln" is base-e, "lg" is base-2]
(b) f(n) = n^2 / log(n), g(n) = n^{lg(3)}. ["^" is "to the power"]
(c) f(n) = 2^n, g(n) = 2^{2n}.
Problem 3: Consider the following algorithm for finding the largest
element in an array A of size n:
if (n==1) then return A[0].
else:
- recursively, find the maximum value v1 in the left half of A
- recursively, find the maximum value v2 in the right half of A
- compare v1 with v2 and output the one that is larger.
(a) Write a recurrence that describes the number of comparisons
made by this algorithm on an input of size n (assume n is a power of 2).
(b) Solve your recurrence from (a). Hint: try it for n = 1,2,4,8 and guess
an *exact* formula for T(n). Then prove this is correct by induction.
[Note: T(1)=0 since if n=1 the algorithm doesn't make any comparisons]