Description
Average Case
In this project we will try to match the Average Case of algorithm A10 as we derived in
class and the “Real Average” of the algorithm using Monte Carlo approach.
A10: void Insertion (int A[ ], int n) // in reality the elements to be sorted are indexed from
// index 1 to index n
{
int i,j, temp;
A[0]=-32768; //smallest possible integer using 2 bytes integer representation
for (i=1; i<=n, i++) {
j=i;
(1) while ( A[j] < A[j-1]) { // swap
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
j–;
}
}
}
First you must modify A10 to return the number of steps executed. Please note that we
consider only basic operations, which are the “comparisons” only. Call this subroutine
Insertion-Mod( ).
1) (Calculated Average)
Let n = 100.
Calculate the Average-case A(n) as we derived in class.
Let bound be an integer (choose a large number).
Let tot-number-steps = 0 (accumulates total number of
Generate a sequence of n integers (positive and negative as well) using a random
number generator where the numbers of the sequence are between 0 and bound.
Call Insertion-Mod ( ) using this sequence and add the number of steps returned
by this algorithm to tot-number-steps.
Repeat steps e 100,000 times (i.e., generate 100,000 random sequences and
update tot-number-steps).
Calculate the real average of algorithm A10 and let this number be A2(n).
Repeat steps a)-thru g) for the following values of n, n= {100, 500, 1000, 2500, 3000,
3500}.
You final output should look like:
Input size Calculated Average Real Average
100 XX XX
500 XX XX
.. .. ..
3500 XX XX
Please explain the outcome of the experiments.
