The following pseudocode specifies an algorithm intended to calculate the mean o

Question

The following pseudocode specifies an algorithm intended to calculate the mean o f a non-empty array A of real numbers (floats). The intention is that the variable m should contain the mean of the values in A when the algorithm terminates. Mu(A) m=A[1] for j =2 to A. length m=m+(A[j]-m)/j Describe informally why the algorithm does or does not perform correctly. If necessary, make a minor correction to the algorithm. Include an example with A length = 4. State a loop invariant assertion suited to proving that the (possibly revised) algorithm performs correctly. Initialization: show that this loop invariant assertion is true at loop Initialization. Maintenance: show that this loop invariant assertion is maintained as true at the beginning of each loop repetition. To receive credit, include all algebra necessary to support your claim. Termination: show that the loop terminates and that the truth o f the loop invariant assertion at loop Termination implies that the algorithm correctly computes the mean of the values in A.

Explanation / Answer

Mu(A)

m=A[1]

for j=2 to A.length

m=m+(A[j]-m)/j

example:

Note:Array index starts from 0, hence there is small change in code

#include<iostream>
using namespace std;
int main()
{
   float a[4]={1,3,2,2},m,sum;
   m=a[0];
   for(int i=1;i<4;i++)
       m=m+(a[i]-m)/(i+1);
   cout<<m;
}

Loop Invariant in this case: varibale 'm' is always the mean of Subarray[1 to j-1]

(intially 'm'=A[0], mean of single value is the value itself)

Now let us check this and prove that algorithm is correct.

Initialization: Before the first iteration j=2. So Subarray [1:1] is the array to be tested.As it has only one element so it is the mean and is in variable m.
Thus Invariant is satisfied.

Maintanence: This can be easily verified by checking the invariant after each iteration.In this case it is satisfied.

Termination: This is the step where we will prove the correctness of algorithm.

When the loop terminates then value of j is A.length+1. Again Loop invariant is satisfied.This means that 'm' is the mean of Subarray[1 to A.length]

This is what we want to do with our Algorithm.Thus our Algorithm is correct.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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