Archive for March, 2014

Question-72

Question-72

Prove that if A1 , A2 , …. , An and B1 , B2 … Bn are sets such that Aj \subseteq Bj for j = 1, 2 ,…, n, then

\bigcup_{j=1}^{n}A_{j}\subseteq \bigcup_{j=1}^{n}B_{j}.

Complete the basis step.

 

Solution

A1 \subseteqB1 imploes that \bigcup_{j=1}^{k+1}A_{j}\subseteq \bigcup_{j=1}^{k+1}B_{j} .  because the union of one set is itself.

 

Question-71

Question-71

Use mathematical induction to prove that 3 divides n^{3} + 2 n whenever n is a positive integer.

 

solution

 

The statement is true for the base case, n = 1 , since 3 \mid (1^{3} + 2.1). Suppose that 3 \mid (k^{3} + 2k). We must show

that 3 \mid ((k +1)^{3} + 2(k + 1)) . If we expand the expression in question, we obtain (k^{3} + 2 k) + 3 (k^{2} + k +1 ) . By

the inductive

 

Question-70

Question-70

Prove that 3n < n! if n is an integer greater than 6.

The basis step is n = ?. The basis step is true since ?  <  ? .

Assume the statement foe n = k . Then

3k + 1 = 3.?   <  ?  =  ? ,

the  statement for n = ?.

 

Solution

n = 7.

Then basis step is true sincs 2187 < 5040.

3k+1 = 3.3^{k}  < k+1.k! = k+1!,

n = k + 1.

 

 

 

Question-69

Question-69

a) Find a formula for  \frac{5}{1.2} + \frac{5}{2.3} + ….+ \frac{5}{n(n+1)}

By examining the values of this expression for small values of n.

The formula for the sum is ?

 

b)  Prove the formula you conjectured in part (a).

 

Solution

a) \frac{5n}{n+1}

 

b) We prove this by induction. It is clear that \frac{5n}{n+1} = \frac{5}{2} for n = 1. We want to show that

[\frac{5}{1.2} + \frac{5}{2.3} + .... + \frac{5}{k(k + 1)}]+\frac{5}{(k+1)(k+2)}= \frac{5(k+1)}{k+2}, Starting from the left , we replace the quantity in brackets  \frac{5k}{k+1}   (by the inductive hypothesis), and then do the algebra \frac{5k}{k+1}+\frac{5}{(k+1)(k+2)} = \frac{5k^{2}+10k+5}{(k+1)(k+2)} = \frac{5(k+1)}{k+2} , yielding the desired expression.

 

 

Question-68

Question-68

Let P(n) be the statement that 13  + 23  + …. + n3 = (\frac{n(n+1)}{2})^{2} for the positive integer n.

a)     What is the statement P(1) ?

P(1) is the statement

 

b)    Show that  P (1) is true, completing the basis step of the proof.

The left-hand side of the basis step is ?

The right- hand side of the basis step is ?

 

c)  What is the inductive hypothesis?

The inductive hypothesis is the statement that 13 + 23 + ….+ k3 = ?

 

d) What do you need to prove in the inductive step?

You need to prove that 1 + 2 +….. + k + (k+1)^{3} = ?

 

e) Complete the inductive step, identifying where you use the inductive hypothesis.

 

Solution

a) 1^{3} = [\frac{1.(1+1)}{2}]^{2}.

 

b)

The left-hand side of the basis step is = 1.

The right- hand side of the basis step is = 1.

 

c)(k\frac{(k+1)}{2})^2.

 

d) (k + 1 \frac{(k+2)}{2})^2.

For all k  \geq 1.

 

e) Ans The inductive hypotheis replaces the quantity 13 + 23 + …. + k3  from the left-hand side of part (d) , which shows that [13 + 23 + … + k3 ] + (k + 1)3.

           = (\frac{(k +1) (k + 2)}{2})^{2}

 

 

Question-67

Question-67

What is the largest n for which one can solve within one second using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^{-8}seconds, with these functions f(n) ?

For questions (a) to (c) , enter the exact answers. Enter brackets around exponents. Round your answers down to the nearest integer for all other parts. Note that log n = log2 n.

a)     log n

n = ?

 

b)    n

n = ?

 

c)     n. log n

n^{n} = ?

 

d)    n^{2}

n = ?

 

e)     2^{n}

n =?

 

Solution

a)log n = 10^{8}

n = 2^{10^{8}}

 

b) n = 10^{8}

 

c) n.log n = 10^{8}

Log(n^{n}) =10^{8}

n^{n} = 2^{10^{8}}

 

d) n^{2} = 10^{8}

n = \sqrt{10^{8}}

~ 10000

 

e) 2^{n} = 10^{8}

Log 2^{n} = log 10^{8}

n = 8. Log 10

~ 26

 

Question-66

Question-66

How much time dose an algorithm take to solve a problem of size n if this algorithm uses 2n^{2} + 2^{n} operations, each requiring 10^{-7}second, with the following values of n ?

Round your answers to three significant digits. Enter very large or very small numbers using scientific notation.

a)  n = 10

b) n = 20

c) n = 50

d) n = 100

 

Solution

a) 1.224E-4 seconds

b) 0.105 seconds

c) 1.126E8 seconds

d) 1.268E23 Seconds

 

 

 

Question-65

Question-65

What is the largest n for which one can solve within one second a problem using an algorithm that requires f (n) bit operations, where each bit operations, where each bit operation is carried out in 10^{-4}  second , with these functions f (n) ?

For question (a ) to (c) , enter the exact answers. Enter brockets around exponents. Round your answers down to the nearest integer for all other parts. Note that log n = log2 n.

a)     log n

n = ?

 

b)     n

n = ?

 

c)    n . log n

n^{n} = ?

 

d)    n^{2}

n = ?

 

 

e)     n!

n = ?

 

Solution

a) 2^{10^{4}}

b)  10000

c) 2^{10^{4}}

d) 100

e) 13

f) 7

 

 

 

 

Question-64

Question-64

 There is a more efficient algorithm (in terms of the number of multiplications and additions used) for evaluating polynomials than the conventional algorithm. It is called Horner’s method. This pseudocode shows how to use this method to find the value of anxn+an−1xn−1+⋅⋅⋅+a1x+a0 at x=c.

procedure Horner(c,a0,a1,a2,…,an: real numbers)

yan
fori≔1ton
yyc+ani
returny{y=ancn+an−1cn−1+⋅⋅⋅+a1c+a0}

 

a) Evaluate 9x2+2x+3 at x=2 by working through each step of the algorithm showing the values assigned at each assignment step.

y = ?

i = ?

y = ?

i = ?

y = ?


b)
Exactly how many multiplications and additions are used to evaluate a polynomial of degree n at x=c? (Do not count additions used to increment the loop variable.)

There are   = ?

There are  = ?

 

Solution

a) 

y = 9

i = 1

y = 20

i = 2

y =43

 

b)

There are  =  n  multiplications.

There are  =  n  additions.

 

Question-63

Question-63

Give a  big-O estimate for the number of comparisons used by the algorithm that determines the number of 1 s in a bit string n by examining each bit of the string to determine whether it is a 1 bit.

 

Solution

The number of comparisons is O(n) , where is the number or bits in the string. Each bit must be examined to see if it is a 1 bit, therefore there must be least n comparisons to check bit.