## Archive for March, 2014

## Question-72

**Question-72**

Prove that if A_{1} , A_{2} , …. , A_{n} and B_{1} , B_{2} … B_{n} are sets such that A_{j} B_{j} for j = 1, 2 ,…, n, then

.

Complete the basis step.

**Solution**

A_{1 }B_{1 }imploes that . because the union of one set is itself.

## Question-71

**Question-71**

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

**solution**

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

that 3 + 2(k + 1)) . If we expand the expression in question, we obtain + k +1 ) . By

the inductive

## Question-70

**Question-70**

Prove that 3^{n }< 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

3^{k + 1} = 3.? < ? = ? ,

the statement for n = ?.

**Solution**

n = 7.

Then basis step is true sincs 2187 < 5040.

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

n = k + 1.

## Question-69

**Question-69**

**a)** Find a formula for

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)**

**b) **We prove this by induction. It is clear that for n = 1. We want to show that

, Starting from the left , we replace the quantity in brackets (by the inductive hypothesis), and then do the algebra , yielding the desired expression.

## Question-68

**Question-68**

Let P(n) be the statement that 1^{3 } + 2^{3} + …. + n^{3} = 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 1^{3} + 2^{3} + ….+ k^{3} = ?

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

You need to prove that 1 + 2 +….. + k + = ?

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

**Solution**

**a)** .

**b)**

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

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

**c)**.

**d) **.

For all k 1.

**e) **Ans The inductive hypotheis replaces the quantity 1^{3} + 2^{3} + …. + k^{3} from the left-hand side of part (d) , which shows that [1^{3} + 2^{3} + … + k^{3} ] + (k + 1)^{3.}

^{ = }

## 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 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 = log_{2} n.

**a) ** log n

n = ?

**b) ** n

n = ?

**c)** n. log n

= ?

**d)**

n = ?

**e)**

n =?

**Solution**

**a)**log n =

n =

**b)** n =

**c) **n.log n =

Log =

=

**d) ** =

n =

~ 10000

**e) ** =

Log = log

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 operations, each requiring 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 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 = log_{2} n.

**a)** log n

n = ?

**b) ** n

n = ?

**c)** n . log n

= ?

**d) **

n = ?

**e) ** n!

n = ?

**Solution**

**a) **

**b) **10000

**c) **

**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*−1*xn*−1+⋅⋅⋅+*a*1*x*+*a*0 at *x*=*c*.

**procedure** *Horner*(*c*,*a*0,*a*1,*a*2,…,*an*: real numbers)

*y*≔*an*

for*i*≔1to*n*

*y*≔*y** *c*+*an*−*i*

return*y*{*y*=*ancn*+*an*−1*cn*−1+⋅⋅⋅+*a*1*c*+*a*0}

**a) **Evaluate 9*x*2+2*x*+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.