Archive for March, 2014

Question-62

Question-62

Give a big-O estimate for each of the following function. For the function g in the estimate f (x) is O (g(x)) , use a simple function g of smallest order.

a)     (n^{6} + n^{5}log n) (log n + 3) + (14 log n + 16) (n^{6} + 9)

g (n) = ?

b)    (3^{n} + n^{3}) (n^{4} + 4^{n})

g(n) = ?

c)     (n^{n} + n.5^{n} + 9^{n}) (n! + 9^{n})

g(n) = ?

 

Solution

 

a)  n^{6}log n

b)  12^{n}

c) n^{n}\times n!

 

Question-61

Question-61

Let k be a positive integer. Which of the following mathematical equations correctly shows that

1k + 2k + ………….  + nk  is O (n^{k+1}) ?

 

Solution

1^{k} +  2^{k} + .... n^{k} \leq  n^{k} + n^{k}+....+ n^{k} = n.n^{k} = n^{k+1}

 

Question-60

Question-60

To establish a big-O relationship, find witnesses C and k such that

\left | f(x)\right |\leq C \left | f(x) \right | whenever x > k.

Find the least integer n such that f (x) is  O (x^{n})  for each of the functions.

a)  f(x) = 5x^{5} + x^{7}log x

n = ?

 

b)  f (x) = 4x^{7} + (log x)^{4}

n = ?

 

c)  f (x) =\frac{ x^{5} + x^{4} + 1 }{ x^{5} + 1 }

n = ?

 

d)  f (x) =  \frac{x^{5} +7 log x}{x^{6}+1}

n = ?

 

Solution

a) 8

b) 7

c) 0

d) -1

 

 

Question-59

Question-59

To establish a big-O relationship, find witnesses C and k such that

\left | f(x)\right |\leq C \left | f(x) \right | whenever x > k.

Determine whether each of these functions is O (x^{2})

a) f (x) = 11x + 11

b) f (x) = x^{2} + 700

c) f (x) = x log x

d) f (x) = \frac{(x^{4})}{2}

e) f (x) = 2^{x}

f) f (x) = \left \lfloor x \right \rfloor\cdot \left \lceil x \right \rceil

 

Solution

a) Yes

b) Yes

c) Yes

d) No

e) No

f) Yes

 

Question-58

Question-58

What of the following is an algorithm that locates the first occurrence of the largest element in a finite list of integers? The integers in the list are not necessarily distinct.

 

Solution

procedure first largest ( a1 , a2 , ……… , an : integers)

max = a1

location = 1

for  i = 2 to n

   if max < ai then

      max = ai

      location = i

return location

 

Question-57

Question-57

Consider an algorithm that used only assignment statements that replaces the quadruple (w, x, y, z) with (x, y, z, w). What is the minimum number of assignment statements needed?

 

Solution

5 assignment statements

 

 

Question-56

Question-56

Which statement best describes an algorithm that takes as input a list of  n  integers and produces as output the smallest difference obtained by subtracting an integer in the list from the one following it

 

Solution

Set the answer to be \infty . For  i going from 1 through   n – 1 , complete the value of the ( i + 1)st  element in the list minus the ith element in the list. If this is smaller then the answer, reset the answer to be this value.

 

Question-55

Question-55

Which of the following algorithms can be used to find the sum of all the integers   in a list?

 

Solution

Procedure AddUp (a1,……….. , an : integers)

sum = a1

for i = 2 to n

sum = sum + ai

return sum

 

Question-54

Question-54

Determine which characteristics of an algorithm described in the text (after Algorithm 1) the following procedures have and which they lack. Select characteristics that the procedures have and leave characteristics unselected that the procedures lack.

a) procedure double (n : positive integer

while  n > 0

n  – 10n

 

b)  procedure divide  ( n : positive integer)

while  n  \geq 0

m =  \frac{1}{n}

n = n – 1

 

c)  procedure sum  ( n : positive interger)

sum = 0

while i < 7

sum = sum + i

 

d) procedure chose ( a , b : integers)

x = either a or b

 

Solution

a) 

Input

Output

Definiteness

Correctness

Effectiveness

Generality

 

b) 

Input

Output

Definiteness

Correctness

Finiteness

Generality

 

c)

Input

Output

Correctness

Finiteness

Effectiveness

Generality

 

d)

Input

Output

Correctness

Finiteness

Effectiveness

Generality

 

 

Question-53

Question -53

List all the steps used by Algorithm 1 to find the maximum of the list

5, 9, 13, 9, 11, 2, 16, 2, 14, 4

 

Solution

max = 5 ,  i = 2 ,

max = 9 , i = 3 ,

max = 13 , i = 4 , i = 5 , i = 6 , i = 7 ,

max = 16 , i = 8 , i = 9 , i= 10 , i = 11