Starting from:

$25

EE4371-Assignment 2 Solved

1.     Order the following functions by asymptotic growth rate. 

                          4n logn + 2n   210      2logn                           3n + 100logn  4n       2n                           n2 + 10n          n3      nlogn       

2.     In each of the following situations, indicate whether f = O (g),or f = Ω (g),or both (in which case f = Θ(g)). Justify your answer.  

           

                                     f (n)                                 g (n) 

(a)    n − 100                            n − 200 

(b)    100n + logn                     n + (logn)2 

(c)     log2n                               log 3n 

(d)    n1.01                                  nlog2n 

           

3.     Describe an efficient algorithm for finding the ten largest elements in a sequence of size n​ ​. What is the running time of your algorithm?  

4.     Use the divide and conquer integer multiplication algorithm to multiply the two binary integers 10011011 and 10111010. 

5.     You are given a unimodal array of n​ ​ distinct elements, meaning that its entries are in increasing order up until its maximum elements, after which its elements are in decreasing order. Give an algorithm to compute the maximum element of a unimodal array that runs in O(log n) time. 

6.     You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in array. Show how to remove all duplicates from the array in time O(n log n). 

More products