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
- 1. Complete the routing table for R2 as per the table shown below when implementing RIP routing Protocol? (14 marks) 195.2.4.0 130.10.0.0 195.2.4.1 m1 130.10.0.2 mo R2 R3 130.10.0.1 195.2.5.1 195.2.5.0 195.2.5.2 195.2.6.1 195.2.6.0 m2 130.11.0.0 130.11.0.2 205.5.5.0 205.5.5.1 R4 130.11.0.1 205.5.6.1 205.5.6.0arrow_forwardAnalyze the charts and introduce each charts by describing each. Identify the patterns in the given data. And determine how are the data points are related. Refer to the raw data (table):arrow_forward3A) Generate a hash table for the following values: 11, 9, 6, 28, 19, 46, 34, 14. Assume the table size is 9 and the primary hash function is h(k) = k % 9. i) Hash table using quadratic probing ii) Hash table with a secondary hash function of h2(k) = 7- (k%7) 3B) Demonstrate with a suitable example, any three possible ways to remove the keys and yet maintaining the properties of a B-Tree. 3C) Differentiate between Greedy and Dynamic Programming.arrow_forward
- What are the charts (with their title name) that could be use to illustrate the data? Please give picture examples.arrow_forwardA design for a synchronous divide-by-six Gray counter isrequired which meets the following specification.The system has 2 inputs, PAUSE and SKIP:• While PAUSE and SKIP are not asserted (logic 0), thecounter continually loops through the Gray coded binarysequence {0002, 0012, 0112, 0102, 1102, 1112}.• If PAUSE is asserted (logic 1) when the counter is onnumber 0102, it stays here until it becomes unasserted (atwhich point it continues counting as before).• While SKIP is asserted (logic 1), the counter misses outodd numbers, i.e. it loops through the sequence {0002,0112, 1102}.The system has 4 outputs, BIT3, BIT2, BIT1, and WAITING:• BIT3, BIT2, and BIT1 are unconditional outputsrepresenting the current number, where BIT3 is the mostsignificant-bit and BIT1 is the least-significant-bit.• An active-high conditional output WAITING should beasserted (logic 1) whenever the counter is paused at 0102.(a) Draw an ASM chart for a synchronous system to providethe functionality described above.(b)…arrow_forwardS A B D FL I C J E G H T K L Figure 1: Search tree 1. Uninformed search algorithms (6 points) Based on the search tree in Figure 1, provide the trace to find a path from the start node S to a goal node T for the following three uninformed search algorithms. When a node has multiple successors, use the left-to-right convention. a. Depth first search (2 points) b. Breadth first search (2 points) c. Iterative deepening search (2 points)arrow_forward
- We want to get an idea of how many tickets we have and what our issues are. Print the ticket ID number, ticket description, ticket priority, ticket status, and, if the information is available, employee first name assigned to it for our records. Include all tickets regardless of whether they have been assigned to an employee or not. Sort it alphabetically by ticket status, and then numerically by ticket ID, with the lower ticket IDs on top.arrow_forwardFigure 1 shows an ASM chart representing the operation of a controller. Stateassignments for each state are indicated in square brackets for [Q1, Q0].Using the ASM design technique:(a) Produce a State Transition Table from the ASM Chart in Figure 1.(b) Extract minimised Boolean expressions from your state transition tablefor Q1, Q0, DISPATCH and REJECT. Show all your working.(c) Implement your design using AND/OR/NOT logic gates and risingedgetriggered D-type Flip Flops. Your answer should include a circuitschematic.arrow_forwardA controller is required for a home security alarm, providing the followingfunctionality. The alarm does nothing while it is disarmed (‘switched off’). It canbe armed (‘switched on’) by entering a PIN on the keypad. Whenever thealarm is armed, it can be disarmed by entering the PIN on the keypad.If motion is detected while the alarm is armed, the siren should sound AND asingle SMS message sent to the police to notify them. Further motion shouldnot result in more messages being sent. If the siren is sounding, it can only bedisarmed by entering the PIN on the keypad. Once the alarm is disarmed, asingle SMS should be sent to the police to notify them.Two (active-high) input signals are provided to the controller:MOTION: Asserted while motion is detected inside the home.PIN: Asserted for a single clock cycle whenever the PIN has beencorrectly entered on the keypad.The controller must provide two (active-high) outputs:SIREN: The siren sounds while this output is asserted.POLICE: One SMS…arrow_forward
- 4G+ Vo) % 1.1. LTE1 : Q B NIS شوز طبي ۱:۱۷ کا A X حاز هذا على إعجاب Mohamed Bashar. MEDICAL SHOE شوز طبي ممول . اقوى عرض بالعراق بلاش سعر القطعة ١٥ الف سعر القطعتين ٢٥ الف سعر 3 قطع ٣٥ الف القياسات : 40-41-42-43-44- افحص وكدر ثم ادفع خدمة التوصيل 5 الف لكافة محافظات العراق ופרסם BNI SH ופרסם DON JU WORLD DON JU MORISO DON JU إرسال رسالة III Messenger التواصل مع شوز طبي تعليق باسم اواب حمیدarrow_forwardA manipulator is identified by the following table of parameters and variables:a. Obtain the transformation matrices between adjacent coordinate frames and calculate the global transformation matrix.arrow_forwardWhich tool takes the 2 provided input datasets and produces the following output dataset? Input 1: Record First Last Output: 1 Enzo Cordova Record 2 Maggie Freelund Input 2: Record Frist Last MI ? First 1 Enzo Last MI Cordova [Null] 2 Maggie Freelund [Null] 3 Jason Wayans T. 4 Ruby Landry [Null] 1 Jason Wayans T. 5 Devonn Unger [Null] 2 Ruby Landry [Null] 6 Bradley Freelund [Null] 3 Devonn Unger [Null] 4 Bradley Freelund [Null] OA. Append Fields O B. Union OC. Join OD. Find Replace Clear selectionarrow_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