## Question-72

Question-72

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

.

Complete the basis step.

Solution

A1 B1 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 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 =   < 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 13  + 23  + …. + n3 = 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 + = ?

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 13 + 23 + …. + k3  from the left-hand side of part (d) , which shows that [13 + 23 + … + k3 ] + (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 = log2 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 = log2 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−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.

## 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.