Videos
Program Plan:
- In function “meanIterative()”:
- Compute sum of array elements using a “for” loop.
- Compute mean by dividing sum with number of elements in array.
- In function “varianceIterative()”:
- Compute sum of square of difference between each element with mean.
- Compute variance by dividing it with “n-1”.
- In function “meanRecursive()”:
- If starting index “ii” is same as “n-1”, return element divided by “n”.
- Otherwise, increment the value “ii” by “1” and compute mean all numbers in array by calling function recursively.
- In function “varianceRecursive()”:
- If starting index “ii” is same as “n-1”, return variance of that element.
- Otherwise, increment the value “ii” by “1” and compute variance all numbers in array by calling function recursively.
- In “main()” function:
- Create random input arrays of size “500”, “1000”, “1500” and “2000”.
- For each input array compute standard deviation by using both iterative and recursive functions.
- Compute running time for both and compare each other.
/**********************************************************
* Program to compare running time to compute standard *
* deviation of different sized samples using iterative *
* and recursive functions. *
**********************************************************/
Explanation of Solution
Program:
//Include header files
#include<iostream>
#include<ctime>
using namespace std;
//Iterative function to compute mean of n numbers
double meanIterative(int data[], int n)
{
//Declare variable
double mean;
//Initialize summ as 0
int summ=0;
//Each number from array
for (int i = 0; i < n; i++)
{
//Add number with summ
summ = summ + data[i];
}
//Compute mean of numbers
mean =(double) summ / (double)n;
//Return mean
return mean;
}
//Iterative function to compute variance of n numbers
double varianceIterative(int data[], int n, double mean)
{
//Declare variable
double varianc;
//Initialize summm as 0
double summm=0;
//Each number from array
for (int i = 0; i < n; i++)
{
//Add number with summm
summm = summm + pow((data[i] - mean), 2);
}
//Compute variance
varianc = summm / (float)(n-1);
//Return variance
return varianc;
}
//Recursive function to compute mean of n numbers
double meanRecursive(int data[], int ii,int n)
{
//If starting index ii is equal to n
if (ii == n-1)
//Return mean of that number
return (double)data[ii]/(double)n;
/*Otherwise increment value of ii by 1 and compute mean of numbers by calling function itself recursively*/
return (double)data[ii]/(double)n +meanRecursive(data, ii + 1, n);
}
//Recursive function to compute variance of n numbers
double varianceRecursive(int data[], int ii,int n, double mean)
{
//If starting index ii is equal to n
if (ii == n-1)
//Return variance of that number
return pow((double)data[ii]-mean,2)/(double)(n-1);
/*Otherwise increment value of ii by 1 and compute variance of numbers by calling function itself recursively*/
return pow((double)data[ii]-mean,2)/(double)(n-1) +varianceRecursive(data, ii + 1, n, mean);
}
//Program begins with main() function
int main()
{
//Declare variables
int data_500_S[500],data_1000_S[1000],data_1500_S[1500],data_2000_S[2000];
srand((unsigned)time(0));
//For each index of array of size 500
for(int ii=0;ii<500;ii++)
{
/*Compute random number and store it into array index*/
data_500_S[ii] = rand() % 10000;
}
//For each index of array of size 1000
for(int ii=0;ii<1000;ii++)
{
/*Compute random number and store it into array index*/
data_1000_S[ii] = rand() % 10000;
}
for(int ii=0;ii<1500;ii++)
{
/*Compute random number and store it into array index*/
data_1500_S[ii] = rand() % 10000;
}
for(int ii=0;ii<2000;ii++)
{
/*Compute random number and store it into array index*/
data_2000_S[ii] = rand() % 10000;
}
//Declare variables
double meeanIte, varianceIte,standarddevIte,meeanRec, varianceRecu,standarddevRecu ;
//For array input of size 500
cout<<"For n=500: \n"<<endl;
//Capture current time and store it as initial time
double start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_500_S, 500);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_500_S, 500,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
double stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_500_S, 0,500);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_500_S, 0,500,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//For array input of size 1000
cout<<"\n For n=1000: \n"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_1000_S, 1000);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_1000_S, 1000,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute ruuning time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_1000_S, 0,1000);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_1000_S, 0,1000,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;
//For array input of size 500
cout<<"\n For n=1500: \n"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_1500_S, 1500);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_1500_S, 1500,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << " Milli seconds"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_1500_S, 0,1500);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_1500_S, 0,1500,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//For array input of size 500
cout<<"\n For n=2000: \n"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_2000_S, 2000);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_2000_S, 2000,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli Seconds"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_2000_S, 0,2000);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_2000_S, 0,2000,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli Seconds"<<endl;
//Return from program
system("pause");
return 0;
}
Comparison:
| Input array size, n | Running time in Milliseconds | |
| Iterative Method | Recursive method | |
| 500 | 17 | 14 |
| 1000 | 9 | 6 |
| 1500 | 7 | 7 |
| 2000 | 7 | 7 |
Conclusion:
- Running time for input array of size “n” equals “500” is larger for iterative method than recursive method.
- For other input arrays the running time for both iterative and recursive are almost similar or sometimes it varies for small values.
Output:
For n=500:
Mean using Iterative function is: 4394.44
Variance using Iterative function is: 8.22268e+006
Standard deviation using Iterative function is: 2867.52
Running time for iterative function: 17 Milli seconds
Mean using Recursive function is: 4394.44
Variation using Recursive function is: 8.22268e+006
Standard deviation using Recursive function is: 2867.52
Running time for Recursive function: 14 Milli seconds
For n=1000:
Mean using Iterative function is: 4908.97
Variance using Iterative function is: 8.77065e+006
Standard deviation using Iterative function is: 2961.53
Running time for iterative function: 9 Milli seconds
Mean using Recursive function is: 4908.97
Variation using Recursive function is: 8.77065e+006
Standard deviation using Recursive function is: 2961.53
Running time for Recursive function: 6 Milli seconds
For n=1500:
Mean using Iterative function is: 4531.62
Variance using Iterative function is: 8.7867e+006
Standard deviation using Iterative function is: 2964.24
Running time for iterative function: 7 Milli seconds
Mean using Recursive function is: 4531.62
Variation using Recursive function is: 8.7867e+006
Standard deviation using Recursive function is: 2964.24
Running time for Recursive function: 7 Milli seconds
For n=2000:
Mean using Iterative function is: 4641.43
Variance using Iterative function is: 8.57314e+006
Standard deviation using Iterative function is: 2927.99
Running time for iterative function: 7 Milli Seconds
Mean using Recursive function is: 4641.43
Variation using Recursive function is: 8.57314e+006
Standard deviation using Recursive function is: 2927.99
Running time for Recursive function: 7 Milli Seconds
Want to see more full solutions like this?
Chapter 5 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
- Show the correct stereochemistry when needed!! mechanism: mechanism: Show the correct stereochemistry when needed!! Br NaOPh diethyl ether substitutionarrow_forwardIn javaarrow_forwardKeanPerson #keanld:int #keanEmail:String #firstName:String #lastName: String KeanAlumni -yearOfGraduation: int - employmentStatus: String + KeanPerson() + KeanPerson(keanld: int, keanEmail: String, firstName: String, lastName: String) + getKeanld(): int + getKeanEmail(): String +getFirstName(): String + getLastName(): String + setFirstName(firstName: String): void + setLastName(lastName: String): void +toString(): String +getParkingRate(): double + KeanAlumni() + KeanAlumni(keanld: int, keanEmail: String, firstName: String, lastName: String, yearOfGraduation: int, employmentStatus: String) +getYearOfGraduation(): int + setYearOfGraduation(yearOfGraduation: int): void +toString(): String +getParkingRate(): double In this question, write Java code to Create and Test the superclass: Abstract KeanPerson and a subclass of the KeanPerson: KeanAlumni. Task 1: Implement Abstract Class KeanPerson using UML (10 points) • Four data fields • Two constructors (1 default and 1 constructor with all…arrow_forward
- Plz correct answer by best experts...??arrow_forwardQ3) using the following image matrix a- b- 12345 6 7 8 9 10 11 12 13 14 15 1617181920 21 22 23 24 25 Using direct chaotic one dimension method to convert the plain text to stego text (hello ahmed)? Using direct chaotic two-dimension method to convert the plain text to stego text?arrow_forward: The Multithreaded Cook In this lab, we'll practice multithreading. Using Semaphores for synchronization, implement a multithreaded cook that performs the following recipe, with each task being contained in a single Thread: 1. Task 1: Cut onions. a. Waits for none. b. Signals Task 4 2. Task 2: Mince meat. a. Waits for none b. Signals Task 4 3. Task 3: Slice aubergines. a. Waits for none b. Signals Task 6 4. Task 4: Make sauce. a. Waits for Task 1, and 2 b. Signals Task 6 5. Task 5: Finished Bechamel. a. Waits for none b. Signals Task 7 6. Task 6: Layout the layers. a. Waits for Task 3, and 4 b. Signals Task 7 7. Task 7: Put Bechamel and Cheese. a. Waits for Task 5, and 6 b. Signals Task 9 8. Task 8: Turn on oven. a. Waits for none b. Signals Task 9 9. Task 9: Cook. a. Waits for Task 7, and 8 b. Signals none At the start of each task (once all Semaphores have been acquired), print out a string of the task you are starting, sleep for 2-11 seconds, then print out a string saying that you…arrow_forward
- Programming Problems 9.28 Assume that a system has a 32-bit virtual address with a 4-KB page size. Write a C program that is passed a virtual address (in decimal) on the command line and have it output the page number and offset for the given address. As an example, your program would run as follows: ./addresses 19986 Your program would output: The address 19986 contains: page number = 4 offset = 3602 Writing this program will require using the appropriate data type to store 32 bits. We encourage you to use unsigned data types as well. Programming Projects Contiguous Memory Allocation In Section 9.2, we presented different algorithms for contiguous memory allo- cation. This project will involve managing a contiguous region of memory of size MAX where addresses may range from 0 ... MAX - 1. Your program must respond to four different requests: 1. Request for a contiguous block of memory 2. Release of a contiguous block of memory 3. Compact unused holes of memory into one single block 4.…arrow_forwardusing r languagearrow_forwardProgramming Problems 9.28 Assume that a system has a 32-bit virtual address with a 4-KB page size. Write a C program that is passed a virtual address (in decimal) on the command line and have it output the page number and offset for the given address. As an example, your program would run as follows: ./addresses 19986 Your program would output: The address 19986 contains: page number = 4 offset = 3602 Writing this program will require using the appropriate data type to store 32 bits. We encourage you to use unsigned data types as well. Programming Projects Contiguous Memory Allocation In Section 9.2, we presented different algorithms for contiguous memory allo- cation. This project will involve managing a contiguous region of memory of size MAX where addresses may range from 0 ... MAX - 1. Your program must respond to four different requests: 1. Request for a contiguous block of memory 2. Release of a contiguous block of memory 3. Compact unused holes of memory into one single block 4.…arrow_forward
- using r languagearrow_forwardWrite a function to compute a Monte Carlo estimate of the Beta(3, 3) cdf, and use the function to estimate F(x) for x = 0.1,0.2,...,0.9. Compare the estimates with the values returned by the pbeta function in R.arrow_forwardWrite a function to compute a Monte Carlo estimate of the Gamma(r = 3, λ = 2) cdf, and use the function to estimate F(x) for x = 0.2, 0.4, . . . , 2.0. Compare the estimates with the values returned by the pgamma function in R.arrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology Ptr
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage
New Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
Operations Research : Applications and AlgorithmsComputer ScienceISBN:9780534380588Author:Wayne L. WinstonPublisher:Brooks Cole