CSC 477/677 Assignment 3

Due date: Tuesday, February 17, 2015, 2:30 PM.

1. Replace the following for loop by a while loop, and then write its loop invariant. Assume that a number n and an array x[1] .. x[n] of integers are given. Assume that odd(i) is a Boolean function that is true if i is an odd integer.

   int: sum = 0;
   for (int i = 1; i ≤ n; i++)
     if(odd(i)) sum = sum + i;
   

2. The following is code for bubblesort. The supposed advantage of bubblesort is that, once the array is sorted, it halts, and that might happen quickly. Here is the code for bubblesort. Assume that n and x[1] .. x[n] are given.

   int kounter = 0;
   bool sorted = false;
   while(not sorted){
     kounter++;
     sorted = true;
     for(int i = 1; i < n; i++)
       if (x[i+1] < x[i]){
         swap(x[i],x[i+1]);
         sorted = false;
       }    
     }
   cout << "The array was sorted after"; kounter; "passes of bubblesort";
   

   
   
   Replace the inner loop by a while loop, and write loop invariants for both loops. Copy the code onto your homework paper, indicating where in the code each loop invariant holds.