Question

In: Computer Science

Select 3 different sized (order lg lg n, lg n, n, n lg n, n2 ,...

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, , etc…). An example would be an algorithm to search for a number in a list of n numbers → (n), and a second algorithm to sort a list of numbers using a bubble sort → (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  analysis. I have included some sample Java and C++ timer code below that should work. Show me the programs running/working with the time elapsed outputted for a run. 5pts. 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. 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.

Solutions

Expert Solution

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;
}


Related Solutions

Select 3 different sized (order lg lg n, lg n, n, n lg n, n2, n3,...
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...
Problem 3-40 (LG 3-4, LG 3-6) MLK Bank has an asset portfolio that consists of $120...
Problem 3-40 (LG 3-4, LG 3-6) MLK Bank has an asset portfolio that consists of $120 million of 15-year, 12 percent coupon, $1,000 bonds with annual coupon payments that sell at par. a-1. What will be the bonds’ new prices if market yields change immediately by ± 0.10 percent? a-2. What will be the new prices if market yields change immediately by ± 2.00 percent? b-1. The duration of these bonds is 7.6282 years. What are the predicted bond prices...
Find the order of growth for the following function ((n^3) − (60n^2) − 5)(nlog(n) + 3^n...
Find the order of growth for the following function ((n^3) − (60n^2) − 5)(nlog(n) + 3^n )
1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the definition and proof of...
1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the definition and proof of big-O notation. 2- Prove using the definition of Omega notation that either 8 n is Ω (5 n ) or not. please help be with both
Show that (1 + 2 +. . .+n)2 > 12 +. . .+ n2, for n...
Show that (1 + 2 +. . .+n)2 > 12 +. . .+ n2, for n ≥ 2.
(1) T(n)=9⋅T(n3)+n2⋅(log⁡(n))2 (2) T(n) = 10 * T(n/3) + n^2 One of these can be solved...
(1) T(n)=9⋅T(n3)+n2⋅(log⁡(n))2 (2) T(n) = 10 * T(n/3) + n^2 One of these can be solved using the Master Theorem; the other cannot. Which one can be solved using the Master Theorem? Compute the solution to this recurrence relation. Which one cannot be solved using the Master Theorem? Carefully explain why not. (NOTE: A complete solution will use the definition of big-O.) Use another method to solve this recurrence relation. To make this a bit easier, you may assume that...
Find the sum (n=5, to infinity) of the series (n2 -n)/2n
Find the sum (n=5, to infinity) of the series (n2 -n)/2n
Give an O(lg n)-time EREW algorithm that determines for each object in an n-object list whether...
Give an O(lg n)-time EREW algorithm that determines for each object in an n-object list whether it is the middle (n/2 th) object.
A sequence {an} is given by: an = n2 - 1, n € N. Show that it is not an arithmetic progression (A.P)?
A sequence {an} is given by: an = n2 - 1,   n € N. Show that it is not an arithmetic progression (A.P)?   
2.00mole of nitrogen (N2) gas and 2.00mole of argon (Ar) gas are in separate, equal-sized, insulated...
2.00mole of nitrogen (N2) gas and 2.00mole of argon (Ar) gas are in separate, equal-sized, insulated containers at the same temperature. The containers are then connected and the gases (assumed ideal) allowed to mix. PART A: What is the change in entropy of the system? PART B: What is the change in entropy of the environment? PART C: Repeat part A but assume one container is twice as large as the other.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT