Question

Select 3 different sized (order lg lg n, lg n, n, n lg n, n2, n3, nk, cn, n!) algorithms to code using a compiler of choice (VB, C++, Java). An example would be an algorithm to search for a number in a list of n numbers à q(n), and a second algorithm to sort a list of numbers using a bubble sort à q(n2). You could also choose to just calculate a open form expression like 1 + 2 + 3 + 4 + 5 + 6 + … n for a size n algorithm. Once the algorithms are coded and working (10pts. will be awarded on complexity/substance of algorithms), add a timer to the crucial section of the code that will correspond to the theta analysis. I have included some sample Java and C++ timer code below that should work. Run and time the three algorithms for n = 10, 100, 1000, 10000, etc… and chart the different times on a column, bar, or line chart. Show me the programs running/working with the time elapsed outputted for a run. 5pts. Turn in a word processed report listing the three algorithms code and the charts displaying the timed results of the runs. 5pts. Use long (16 bit) in Java and long long (16 bit) in C++ for your variables to avoid a memory problem.

Subject: Computer Science

Answer 1

CODE :

1) Searching a number in an array

#include <iostream>
#include <time.h>
using namespace std;
int main()
{
int n;
clock_t start = clock();

cout<<"Enter Number of Elements in Array\n";
cin>>n;
int arr[n],num,flag=0;

// Elements of Array
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}

cout<<"\nEnter the number to be serach in Array";
cin>>num;

// search num in Array
int j;
for(j = 0; j < n; j++)
{
if(arr[j] == num)
{
flag = 1;
break;
}
}
if(flag)
{
cout<<"Element Present at index "<<j+1<<" in Array\n";
}
else
cout<<"\n Element not found ";

clock_t end = clock();
double elapsed = double(end - start)/CLOCKS_PER_SEC;

cout<<"\nTotal time for execution : "<<elapsed<<endl;
return 0;
}

2) Sort number using Bubble Sort

#include <iostream>
#include <time.h>
using namespace std;
int main()
{
int n;
clock_t start = clock();

cout<<"Enter Number of Elements in Array\n";
cin>>n;
int arr[n];

// Elements of Array
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}

// Bubble Sort Implementation
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

// Print the Array
cout<<"\n Sorted Array"<<endl;
for(int i = 0; i < n; i++)
{
cout<<"\t"<<arr[i];
}

clock_t end = clock();
double elapsed = double(end - start)/CLOCKS_PER_SEC;

cout<<"\nTotal time for execution"<<elapsed;
return 0;
}

3) Addition of n elements

#include <iostream>
#include <time.h>
using namespace std;
int main()
{
int n;
clock_t start = clock();

cout<<"Enter nth number of series \n";
cin>>n;
// Summation formula
int sum = (n*(n+1))/2;

cout<<"\n Sum of first n element "<<sum<<endl;

clock_t end = clock();
double elapsed = double(end - start)/CLOCKS_PER_SEC;

cout<<"\nTotal time for execution"<<elapsed;
return 0;
}