Algorithms Problem Set 2

Advice 1: For every problem in this class, you must justify your answer: show how you arrived at it
and why it is correct. If there are assumptions you need to make along the way, state those clearly.
Advice 2: Purely verbal or purely mathematical reasoning is typically insufficient for full credit.
Instead, use mathematics to make your argument more precise and logical, and use language to
explain your mathematical reasoning more clearly.
Advice 3: You will receive an extra 5 points on your assignment grade if you submit a nicely
formatted typeset file instead of a hand-written file. Refer to the Latex template files on Moodle
and the Latex tutorial for information on how to use Latex. For documents with equations and
algorithms, Latex is easier to work with than Word, once you get used to it.
1. (20 pts total) Solve the following recurrence relations using any of the following methods: unrolling, tail recursion, recurrence tree (include tree diagram), or expansion.
Each each case, show your work.
(a) T (n) = T (n − 1) + 2n if n 1, and T (1) = 2
(b) T (n) = T (pn) + 1 if n 2 , and T (n) = 0 otherwise
2. (10 pts) Consider the following function:
def foo(n) {
if (n 1) {
print( ’’hello’’ )
foo(n/4)
foo(n/4)
}}
In terms of the input n, determine how many times is \hello" printed. Write down a
recurrence and solve using the Master method.
3. (30 pts) Professor McGonagall asks you to help her with some arrays that are spiked.
A spiked array has the property that the subarray A[1::i] has the property that A[j] <
A[j + 1] for 1 ≤ j < i, and the subarray A[i::n] has the property that A[j] A[j + 1]
for i ≤ j < n. Using her wand, McGonagall writes the following spiked array on the
board A = [7; 8; 10; 15; 16; 23; 19; 17; 4; 1], as an example.
1(a) Write a recursive algorithm that takes asymptotically sub-linear time to find the
maximum element of A.
(b) Prove that your algorithm is correct. (Hint: prove that your algorithm’s correctness follows from the correctness of another correct algorithm we already know.)
(c) Now consider the multi-spiked generalization, in which the array contains k spikes,
i.e., it contains k subarrays, each of which is itself a spiked array. Let k = 2 and
prove that your algorithm can fail on such an input.
(d) Suppose that k = 2 and we can guarantee that neither spike is closer than n=4
positions to the middle of the array, and that the \joining point" of the two singlyspiked subarrays lays in the middle half of the array. Now write an algorithm that
returns the maximum element of A in sublinear time. Prove that your algorithm is
correct, give a recurrence relation for its running time, and solve for its asymptotic
behavior.
4. (15 pts extra credit)
Asymptotic relations like O, Ω, and Θ represent relationships between functions, and
these relationships are transitive. That is, if some f(n) = Ω(g(n)), and g(n) = Ω(h(n)),
then it is also true that f(n) = Ω(h(n)). This means that we can sort functions by
their asymptotic growth.1
Sort the following functions by order of asymptotic growth such that the final arrangement of functions g1; g2; : : : ; g12 satisfies the ordering constraint g1 = Ω(g2), g2 = Ω(g3),
: : : , g11 = Ω(g12).
n n2 (p2)lg n 2lg∗ n n! (lg n)! 32?n n1= lg n n lg n lg(n!) en 1
Give the final sorted list and identify which pair(s) functions f(n); g(n), if any, are in
the same equivalence class, i.e., f(n) = Θ(g(n)).
1The notion of sorting is entirely general: so long as you can define a pairwise comparison operator for
a set of objects S that is transitive, then you can sort the things in S. For instance, for strings, we use a
comparison based on lexical ordering to sort them. Furthermore, we can use any sorting algorithm to sort S,
by simply changing the comparison operators , <, etc. to have a meaning appropriate for S. For instance,
using Ω, O, and Θ, you could apply QuickSort or MergeSort to the functions here to obtain the sorted list.
2