1 The following algorithm returns true if the sorted array A

1. The following algorithm returns true if the sorted array A contains all unique elements (no duplicates) and returns false otherwise:

ALL_UNIQUE(sortedA)

     for i = 1 to sortedA.length-1

            if sortedA[i] == sortedA[i+1]

                    return false

     return true

a. Write a loop invariant that can be used to prove the correctness of the algorithm.

b. Show that the loop invariant is true at the initialization of the loop.

c. Show the that loop invariant is true during the maintenance of the loop

d. Show that the loop invariant is true at the termination of the loop and show that the algorithm computes the correct output.

e. Using the cost constants c₁, c₂, … shown for each line of pseudocode above, give an expression for the number of times each line is executed (fill in to the right of the code), and an expression for the total cost of executing this function

Solution

cpp code:

#include <iostream>

/* run this program using the console pauser or add your own getch, system(\"pause\") or input loop */
using namespace std;
int main(int argc, char** argv) {
   int arr[10],n,i,j,temp=0;
   int dup = 0;
   cout << \"Enter number of elements in the array:\";
   cin >> n;
   for(i = 0; i < n;i++){
       cin >> arr[i];
   }
   cout << \"Array elements before sorting:\ \";
   for(i = 0; i < n;i++){
       cout << arr[i]<< \"\\t\";
   }
   cout << \"Array elements after sorting:\ \";
   for(j=0;j<n;j++){
       for(i=0;i<n;i++){
           if(arr[j] <= arr[i]){
               temp = arr[j];
               arr[j] = arr[i];
               arr[i] = temp;
           }
          
       }
   }
   for(i = 0; i < n;i++){
       cout << arr[i] << \"\\t\";
   }
  
   for(i=0;i<n;i++){
       for(j=0;j<n;j++){
           if(arr[i] == arr[j] && i!=j)
               dup++;
       }
   }
   if(dup > 1)
       cout << \"Duplicate Found!!!\";
   else
       cout << \"No Duplicates!!!\";
      
   return 0;
}