Question

a) Write a trial run for the algorithm using the input 5,3,1,4

b) Use induction to prove that your algorithm returns the correct value

The recursive algorithm in pseudocode is as follows (The input: a1,a2, ..., an a sequence of numbers where n>=1, the output: m, the minimum value of the sequence)

minvalue (a1,a2,...,an)

If(n=1) return a1

m: = minvalue(a2,a3,...,an)

If (a1

return m

Answer 1

In case of any queries, please revert back.

The Algorithm is as follows =>

minvalue (a1,a2,...,an) {

If(n=1) return a1

m: = minvalue(a2,a3,...,an)

If (a1 < m) return a1

return m}

Now, this is a recusrive function to find minimum value in a sequence of elements a1,a2,a3,a4....,an.

A.) Trial Run For the Algorithm

5,3,1,4

ITER 1 :

5,3,1,4

Now, n!=1 , so, we branch and call ITER 2 :

3,1,4

Now, n!=1, So, We branch and call ITER 3:

1,4

Now, n!=1, So, We branch and call ITER 4:

4

Now, n=1, So, ITER 4 returns 4 to ITER 3.

ITER 3 Compares return of ITER 4 that is 4 and 1.

Now, ITER 3 returns 1 to ITER 2.

ITER 2 Compares return of ITER 3 that is 1 and 3.

Now, ITER 2 returns 1 to ITER 1.

ITER 1 returns smaller of 1 and 5 which is 1

So, The final Function minvalue(5,3,1,4) returns 1.

B.) USE OF INDUCTION FOR PROVING CORRECTNESS.

Let us check the Base case First.

For, n=2 , We always get the correct value. This is becuase recursive call returns minimum of 2 values. So, the algortihm Satisfies the base case.

Now, Let us assume that algorithm gives correct result a1,a2....,am. We have to prove that algorithm will give correct result for a1,a2,a3.....,am,am+1.(In this way we can generalize algorithm over all Natural numbers N).

If we look at function and we add a value before a1 in a1,a2....,am ie. a0.

Now, we have :-

minvalue(a0,a1,a2......,am){

if(n=1) return a0

m = minvalue(a1,a2,a3.....,am) ////// We are sure that this statement gives correct value.

if(a0<m) return a0 //// So, the next 2 statements just compare m and a0.

return m //// They always return minimum of a0 and m.

}

Hence, our algorithm works for a1,a2.....,am+1 and so, we can generalize this for all natural numbers.

This is how inductive hypothesis proves correctness of the algorithm.