# Design and Analysis of Algorithms-COMP 3804,-Winter 2019-Assignment 1

Your paper should be submitted online on cuLearn as a single .pdf file. No late assignments will be accepted.

You can type your assignment or you can upload a scanned copy of it. Please, use a good image-capturing device.

Make sure that your upload is clearly readable. If it is difficult to read, it will not be graded!

Your proofs should be precise, concise and clear.

- (10 pts) List the following functions of n in increasing order of asymptotic growth, i.e., if f(n) appears before

(to the left of) g(n) in the list, then f(n) is O(g(n)). There is not require to show your work.

n3=2 (log n)3 2n log n n! log log n log n

log log n 2log n nn n2=3

- (6 pts) Prove that log(n!) = [1](nlogn).

(Hint: You will need to use the definition of n! as well as the rules for manipulating logarithms.)

- (4 pts) Prove by induction that

Pn

i=1 1=(i(i + 1)) = n=(n + 1).

- (10 pts) Prove or disprove the following:

(a) (2 pts) 2n2 ? 5n ? 12 = O(n3)

(b) (2 pts) 3n2 log n ? 2n log n =

(n2)

(c) (2 pts) 2n =

(2n+1)

(d) (2 pts) n log n = O(n2)

(e) (2 pts) n2 log n =

(n3)

- (20 pts) Evaluate the following recurrences. Use Master Theorem if applicable. If not - clearly state why and

solve the corresponding recurrence using the unfolding method we have seen in class. In each case, give the

final answer using Big-O notation.

(a) (5 pts) T(1) = 1, and for n 3: T(n) = 1 + 2T(n=3). You can assume that n is a power of 3.

(b) (5 pts) T(2) = 1, and for n 4: T(n) = 1 + T(

p

n). You may assume that n is a power of a power of 2, so

that log log n is an integer.

(c) (5 pts) T(1) = 1, and for n 2: T(n) = 5T(n=7) + n. You may assume that n = 7k for some k > 0.

(d) (5 pts) T(1) = 1, and for n 2, T(n) = T(n ? 1) + 2n.

1

**COMP 3804 ASSIGNMENT 1 2**

another of size 3n=4, recursively solving each of them, and then combining the solution in O(n) time.

What are the running times of each of these algorithms and which one you are going to choose?

- (10 pts) In class, we saw a deterministic O(n) time algorithm to compute the kth smallest element in an

unsorted array S of n numbers. The main idea to get the linear time algorithm was to find a good pivot

element. This was done by partitioning the array S into n=5 sets of size 5. Then computing the median of each

of these sets of size 5, resulting in a set of n=5 medians. The pivot element is the median of these n=5 medians

and is computed recursively. What if we partition the array S into n=3 elements of size 3, instead.

(a) (3 pts) How many elements are guaranteed to be smaller than the pivot and how many are guaranteed to

be larger than the pivot? Explain your reasoning (you do not need to give a formal proof).

(b) (3 pts) Give the recurrence for the new running time of the algorithm.

(c) (4 pts) Solve the recurrence using any method of your choice and state the running time of the algorithm

in terms of n using Big-Oh notation.

- (10 pts) Given an unsorted array of n numbers. Find the second smallest of them in n+dlog ne?2 comparisons.

Related Link:**Assignment Help**