COMP3711 - Design and Analysis of Algorithms - Assignment 1 - Solved

Problem 1: [25 pts]
In class, we “solved” the Mergesort recurrence

                                                   and       T(1) = 1        (1)

by simplifying and assuming that n was a non-negative integral power of two. This permitted replacing Equation (1) with

                                                                           T(n) ≤ 2T(n/2) + n      and     T(1) = 1.

We were then able to use the expansion method (with implicit induction) to derive the exact solution

                                                                                                  T(2k) ≤ 2k + k2k.                                              (2)

If n = 2k this becomes T(n) ≤ n + nlog2 n.

We then jumped to say that Equation (2) implies T(n) = O(nlogn).

It doesn’t, formally. The expansion method only really solved it for n being a power of 2.

The solution to this homework problem will show, at least for two recurrences, why such simplifications are “legal” and why Equation (1) implies T(n) = O(nlogn) for all n ≥ 1.

Before attempting this homework, you should first read the “Practice Homework” on the class tutorial page and understand the solution given for that.

That will not only provide some starting intuition for how to solve this problem, it will also illustrate how to formally write solutions.

(a)     Let c > 0 be constant. Let T(n) be a function satisfying

                                                             and       T(1) = T(2) = 1.        (3)

(i)          Prove using the expansion method that T(3k) = O(k).

(ii)        Let S(n) be some nondecreasing function of n.

You are told that S(n) also satisfies S(3k) = O(k). Prove that this implies S(n) = O(log3 n).

(iii)      For all n ≥ 1, set R(n) = max1≤i≤n T(i). Prove that

 

(iv)      Prove that if T(n) satisfies Equation (3) then T(n) = O(logn). You can either do this by using the facts proven in parts (i), (ii) and (iii) (recommended) or directly (much longer).

(b)    We learned in class that if T(n) satisfies Equation (1) then it satisfies Equation (2) so

                                                                                                          T(2k) = O(k2k).                                          (4)

(v)         Let S(n) be some nondecreasing function of n that also satisfies Equation (4). Prove that this implies S(n) = O(nlog2 n).

(vi)      For all n ≥ 1, set R(n) = max1≤i≤n T(i).

Prove that if T(n) satisfies Equation (1) then

 

(vii)    Assuming the correctness of Equation (4), prove that T(n) defined by Equation (1) satisfies T(n) = O(nlog2 n).

You can either do this by using the facts proven in parts (v) and (vi) (recommended) or directly (much longer).

Requirements, Hints and Comments:

 

•     Prove each of parts (i) - (vii) separately in order. Make sure that you clearly label each part.

Leave a few empty lines between each part.

Solutions not following this format will have points deducted.

•     You should assume the correctness of earlier parts when solving later ones. For example, when solving part (iv), you should assume the correctness of parts (i), (ii) and (iii).

•     k and n will always denote non-negative integers.

•     F(n) being a non-decreasing function means ∀n, F(n) ≤ F(n + 1).

•     f(n) = O(g(n)) means that there exists c > 0 and n0 such that ∀n > n0, f(n) ≤ cg(n).

Your proofs in parts (i), (ii) (iv), (v) and (vii) should explicitly identify the values of c and n0 used.

•     T(3k) = O(k) and T(2k) = O(k2k) mean, respectively, that

there exists c > 0 andk0 such that ∀k > k0, T(3k) ≤ ck. there exists c0 > 0 and  such that  .

•     In part (ii) you only know that S(n) is a non-decreasing function satisfying S(3k) = O(k). Your proof may not use any other assumptions about S(n).

Hint: Use the fact that for x ≥ 3, log3 3x = 1 + log3 x ≤ 2log3 x.

•     Similarly, in part (v), you may only use the facts that S(n) is a nondecreasing function satisfying S(2k) = O(k2k).

•     Write full, formal solutions.

Problem 2 [14 pts]
For each pair of expressions (A,B) below, indicate whether A is O, Ω, or Θ of B. Note that zero, one, or more of these relations may hold for a given pair. List the most appropriate relation.

It often happens that some students will get the directions wrong, so please write out the relation in full, i.e., you should write exactly one of the terms or write that none of the relations is satisfied.

More explicitly, if any of the relationships are satisfied, you should write the appropriate

                                                                       A = O(B),        A = Ω(B),      or     A = Θ(B)

and not just O(B), Ω(B) or Θ(B), omitting the A.

If no relationship is satisfied write none of the relations is satisfied.

(a)     A = n3 − n2 logn, B = 30n2 − 7n3 + 2n4;

(b)    A = log100((n + 2)!), B = log2 nn;

 ;  ;

(e) A = n62n(log2 n)3, B = n8 + 202120202019;

 ;

(g) A = n(1 + (−1)n), B = n(1 + (−1)n+1).

Write one solution per line.

Hints and Comments:

•    If only one relationship holds, then the most appropriate relationship is just that relationship. If A = Θ(B) then you should write A = Θ(B) (even though both A = O(B) and A = Ω(B) are both also valid). As examples,

–    If A1 = 10n and B1 = n2 then the answer should be “A1 = O(B1)”.

–    If A2 = 10n2 and B2 = n2 − 20n then the answer should be “A2 =

Θ(B2)”.

•    It is NOT necessary to provide justifications for your answer. But if you do not provide any justifications and you are wrong, we cannot award you partial credit.

Problem 3 [20 pts]
Give asymptotic upper bounds for T(n) satisfying the recurrences in parts (a) and (b). Make your bounds as tight as possible.

Note that “tight upper bound” means the best possible Big-O answer. So, T(n) = O(n5) would not be considered a fully correct answer if T(n) = O(n4) as well.

You must prove your results from scratch using either the expansion or tree method shown in class. Show all of your work.

For (a) you may assume that n is a power of 3; for (b) you may assume that it is a power of 4.

(a)     T(1) = 1; T(n) = 10T(n/3) + n2 for n > 1.

(b)    T(1) = 1; T(n) = 16T(n/4) + n2 for n > 1.


Problem 4: [21 pts] Tutorial question DC8 asks you to solve the “stock-profit” problem using divide-and-conquer techniques in O(nlogn) time. The bottom of the first page of the solution slides states:

Note: This problem can be solved using similar ideas that are used for the maximum contiguous subarray problem. Similar to that problem, there is also an O(n) time linear scan solution. That is not what is being requested here, but it is a good exercise to see if you can find it.

You now need to find an O(n) time algorithm for solving the stock-profit problem.

(a)     Write your algorithm down in clear documented pseudocode.

Separately, below the algorithm, provide an understandable explanation in words as to what the algorithm is doing.

(b)    Prove (explain) why your algorithm is correct.

(c)     Prove (explain) that your algorithm runs in O(n) time.


Problem 5: [20 pts] Searching
The input to the problem is an n element array A[0,...,n − 1]. Element A[i] is locally minimal in array A if A[i] is not larger than all of its neighbors (either the neighbors to both sides, or the neighbor to one side if it’s the first or last item). For example, 7, 6 and both 8’s are the locally minimal items in the array below

7
13
15
12
6
9
11
14
16
23
25
24
8
8
Finding an absolute globally minimal item requires O(n) time to inspect every item. Finding a locally minimal one can be done faster.

You now need to find an O(logn) time algorithm for finding a locally minimal element in the array. If there are many such items, you only need to return one of them.

(a)     Write your algorithm down in clear documented pseudocode.

(b)    Prove (explain) why your algorithm is correct.

(c)     Prove (explain) that your algorithm runs in O(logn) time.