Trace the algorithm of the Scuffle for the input 34 57 72 101 135 Assume that th

Question

Trace the algorithm of the Scuffle for the input 34 57 72 101 135 Assume that the values of rand are r and f(1. 5) = 2. R and (2. 5) - 5 r and (3, 5) - 3. R and (4. 5) - 4 Input: A. n Output: A (shuttled) shuttle(A n) {for i = 1 to n - 1 swap(Ai, Ar and (i, n))} Exercise 6: Let consider that 1 + 2+ ... + n = Wn^2 + Xn + Y For all n, and for some constant W, X and Y. a) Assuming that this is true, plug in n = 1, 2, 3 to obtain three equations in the three unknowns W, X and Y. b) Solve for W, X and Y with the three equations obtained in the previous question. c) Prove using the mathematical induction that the statement is true.

Explanation / Answer

Q.6) 1 + 2 +3 + ....+n = Wn2 + Xn + Y

a) put n = 1, you will get

1 = W(1)2 + X(1) + Y

1 = W + X + Y...................(I)

put n = 2

1 + 2 = W(2)2 + X(2) + Y

3 = 4W + 2X + Y ................(II)

put n = 3

1 + 2 + 3 = W(3)2 + X(3) + Y

6 = 9W + 3X + Y .............(III)

(b) To find the value of W, X and Y

subtract equation (I) from (II)

3 = 4W + 2X + Y i.e 3 = 4W + 2X + Y

- 1 = W + X + Y -1 = - W - X - Y by negative sign , signs get change of equation (I)

   2 = 3W + X + 0

2 = 3W + X .......(IV)

Now, subtract (II) from (III)

6 = 9W + 3X + Y i.e     6 = 9W + 3X + Y

- 3 = 4W + 2X + Y - 3 = - 4W - 2X - Y

   3 = 5W + X +0

3 = 5W + X ............(V)

solve equation (IV) and (V)

subtract (IV) from (V)

3 = 5W + X i.e 3 = 5W + X   

- 2 = 3W + X   -2 = -3W - X

   1 = 2W + 0

1 = 2W which implies that W = 1/2

now put tthe value of W in equation (IV) so you will get value of X

2 = 3(1/2) + X

2 = 3/2 + X

2- 3/2 = X

(4-3)/2 = X

1/2 = X

Now, put the value of W and X in equation (I) to get the value of Y

1 = 1/2 + 1/2 + Y

1 = 1 + Y

1 -1 = Y

0 = Y

Therefore W = 1/2 , X = 1/2, Y = 0

(c) By using Mathematical induction

statement is 1 + 2 + 3 + ----------+ n = (1/2)n2 + (1/2)n + 0

1 + 2 + 3 + ...........+ n = 1/2)n2 + (1/2)n

Basic step:- put n = 1

L.H.S = 1

and R.H.S = (1/2)(1)2 + (1/2)(1) = 1/2 + 1/2 = 1

Inductive step:-

Assume that this is true for n= k, therefore 1 + 2 + 3 +.......+k = (1/2)k2 +(1/2)k

= (1/2)k ( k + 1) take (1/2) k common

prove that this is true of n = k+1

replace k by k+1

1 + 2+ 3 + ..........+ k+1 = (1/2)(k+1)2 + (1/2)(k+1)

L.H.S = 1 + 2+ 3 + ..........+ k+1

= 1 + 2 + 3 +.........+ k + k+1 ,we know the addition upto 1 + 2 + 3 ....+k from above which is (1/2)k(k+1)

= (1/2)k(k+1) + k+1 ( by carry k+1 )

=(k+1) ((1/2)k + 1) ( by taking k+1 common)

= (k+1) (k/2 + 1)

= (k+1) ( (k+2)/2)

= ( (k+1) (k+2)) / 2

R.H.S = (1/2)(k+1)2 + (1/2)(k+1)

= (1/2)(k+1) ( k + 1 + 1) (by taking k+1 common)

= (1/2)(k+1)(k+2)

= ((k+1) (k+2)) / 2

Therefor L.H.S = R.H.S

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.