Average Case In this project we will try to match the Average Case of algorithm

Question

Average Case

In this project we will try to match the Average Case of algorithm A5 as we calculated in class and the “Real Average” of the algorithm.

A5: int Find (int x, int A[ ], int n) // array of size n

      { int j;

        for (j=0; j < n; j++) {

        (1)      if (x = = A[j]) {

                      return (j+1); //the position is 1 more than the index

                  }

        }

        return 0; // x is not an element of the array

    }

The project is composed of three steps:

1) (Calculated Average)

  Let n = 50.

Let bound be an integer.

Let x be an integer between 0 and bound.

Let hits=0.

Generate a sequence of n integers using a random number generator where the numbers of the sequence are between 0 and bound. Save this new sequence in an array Sequence.

If x is equal to any of the numbers generated in the sequence increment hits by one (if x appears more than once do not increment hits every time).

Repeat steps e and f 10,000 times (in other words create 10,000 sequences of 50 integers each. Clearly Sequences is a 50 x 10,000 two-dimensional array.

Let q=hits/10,000.

Calculate A(n) for algorithm A5 using the formula derived in class.

2) (Real Average)

Using the sequences created in the previous step (two-dimensional array Sequences) run algorithm A5 10,000 times using each time an input of Sequences. Let total-steps be a variable that tells you the total number of steps executed so far, that is, initialize total-steps to zero, and add the number of steps executed by A5 on each of the inputs, to this variable. For example if A5 executes 25 steps on the first input, then add 25 to total-steps. Let say on second input A5 performs 15 operations, now total-steps = 40 (i.e. 25 + 15). Keep doing this until all the 10,000 inputs are executed by A5. To calculate the Real Average let A2(n)=total-steps/10,000.

3) On step 3 compare A(n) as calculated in step 1) to A2(n) calculated in Step 2.

Run steps 1), 2) and 3) for the following values of bound

bound = 30, 50, 80, 100, 1000, 10,000, infinite

You final output should look like:

Bound       Calculated Average        Real Average

30                   XX                               XX

50                   XX                               XX

..                        ..                                 ..

10,000            XX                               XX

Infinite           XX                               XX

Explanation / Answer

1.

#include<iostream>
#include<cstdlib>

using namespace std;

int countMatch(int x, int *arr, int n) {
   int hits = 0;
   for (int i = 0; i < n; i++)
       if (x == arr[i])
           hits++;
   //cout << "pass search" << endl;
   return hits;
}

int * getRandArray(int n, int bound) {
   int *arr = new int(n);
   srand (time(NULL));
   for (int i = 0; i < n; i++)
       arr[i] = rand() % bound;
   //cout << "pass get" << endl;
   return arr;

}

int main() {
   int n = 50;
   int *arr;
   int bound;
   int hits = 0;
   int x;
   cout << "Enter bound: ";
   cin >> bound;
   cout << "Enter x: ";
   cin >> x;
   for (int i = 0; i < 10000; i++) {
      
       arr = getRandArray(n, bound);
       hits += countMatch(x, arr, n);
       delete arr;
       //cout << "pass delete" << endl;
   }
   float q = (float)hits/10000;

   cout << "q = " << q;
}

to debug remove the single line comments

This is answer to question 1. if you need answers to other questions too, please comment below because if not mentioned, we are suppose to answer only the 1st question.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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