C++ please read all the question
Create 3 large arrays to search, where the size will be variable up until it reaches your machines limit.
They should contain the same information since we are
going to compare 3 different algorithms.You are going to do
operational studies on them to determine their order.
O(N), O(log(N)), and O(1)?
Search algorithms.Linear, Binary, Hash
You should know which algorithms are what order,now you are going
to prove it.
Fill the 3 arrays with the same information but use random strings
of say size 20 characters.Or use 1 array and 3 separate
programs.
You will perform searches on the arrays given strings that are in
the array and those that are not. Make this about a 50-50 mix, or
at least know what the mix is.
a) Perform the linear search, record the time. If
it does it very quickly you will need to adjust the size and the
number of loops over the data till you get a few seconds. Then
start increasing N. The object is to see how time increases as N
increases.
b) Perform the same task with the Binary
Search.Obviously using Binary the data first has to be ordered.
This is an O(N^2) to O(NlogN) function just on it's own but it only
needs to be done once. Don't take this time into account. Yes, I
know that's bad, but I just want to show specific algorithm
differences not including the sort.
c) Perform the same task with the Hash
function.This is tricky since you have to develop the Hash
function. Also, I want you to use chaining. This makes it easy
since there are no collisions and you don't have to use algorithms
for collisions, just use a linked list when a collision
occurs.
When done, plot the results of each algorithm as Time vs. N It
should be easy to conclude the order of the algorithm.
CODE:
#include<iostream>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include<time.h>
#include <list>
using namespace std;
class Algorithms
{
public:
int *LinearArray;
int *BinaryArray;
int *Temp_array;
int size,count;
list<int> *table;
int BUCKET;
public:
Algorithms(int size)
{
LinearArray = (int *)malloc(20 * sizeof(int));
BinaryArray = (int *)malloc(20 * sizeof(int));
Temp_array = (int *)malloc(20 * sizeof(int));
this->size=size;
this->BUCKET=size;
table=new list<int>[BUCKET];
}
~Algorithms()
{
delete LinearArray;
delete BinaryArray;
delete Temp_array;
}
public:
void readData()
{
int random_Number;
srand((unsigned)time(0));
for(int i=0;i<size;i++)
{
random_Number=(rand()%100)+1;
Temp_array[i]=BinaryArray[i]=LinearArray[i]=random_Number;
}
}
public:
void printdata()
{
for(int i=0;i<size;i++)
{
cout<<Temp_array[i]<<"\t";
}
cout<<"\n"<<endl;
}
public:
void Linear_Search(int key)
{
bool status=false;
int i;
for(i=0;i<size;i++)
{
if(key==LinearArray[i])
{
status=true;
break;
}
}
if(status==false)
cout<<"\nThe Key is Not Found"<<endl;
else
cout<<"\nThe Key is present at "<<i <<" Location"<<endl;
}
public:
int binarySearch(int array[], int leftindex, int rightindex, int key)
{
if (rightindex>= leftindex)
{
int mid =leftindex+ (rightindex -leftindex)/2;
if (array[mid] == key)
return mid;
if (array[mid] > key)
return binarySearch(array,leftindex, mid-1,key);
return binarySearch(array, mid+1,rightindex,key);
}
return -1;
}
void insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
int hashFunction(int x)
{
return (x % BUCKET);
}
int HashSearch(int key)
{
list <int> :: iterator i;
int index = hashFunction(key);
for (i = table[index].begin();i != table[index].end(); i++)
{
if (*i == key)
return 0;
}
return -1;
}
};
int main()
{
Algorithms obj(10);
time_t start,end;
double tc;
cout<<"\n------------------------------"<<endl;
cout<<"\n*** Implementation Of the Algorithm ***"<<endl;
obj.readData();
cout<<"\nInput Data Elements are"<<endl;
obj.printdata();
cout<<"\nEnter the key to Search in a list"<<endl;
int key;
cin>>key;
cout<<"\nPerforming Linear search "<<endl;
start=clock();
obj.Linear_Search(key);
end=clock();
tc=(difftime(end,start)/CLOCKS_PER_SEC);
cout<<"\ntime efficiency of Linear search is: "<<tc<<endl;
start=clock();
cout<<"\nNow Performing Binary Search "<<endl;
int result=obj.binarySearch(obj.BinaryArray,0,obj.size,key);
if(result==-1)
{
cout<<"\nThe Key is Not found Binary Search "<<endl;
}
else
cout<<"\nThe Key is Found at "<<result<<" Location"<<endl;
end=clock();
tc=(difftime(end,start)/CLOCKS_PER_SEC);
cout<<"\ntime efficiency of Binary search is: "<<tc<<endl;
for(int i=0;i<obj.size;i++)
{
obj.insertItem(obj.Temp_array[i]);
}
cout<<"\nNow Performing Hash Function "<<endl;
result=obj.HashSearch(key);
if(result==-1)
cout<<"\nKey Not Found in Hashtable"<<endl;
else
cout<<"\nKey is Found in Hashtable"<<endl;
}
Sample Output:-
--------------------
------------------------------
Implementation Of the Algorithm
Input Data Elements are
35 94 79 59 60 28 57 47 15 36
Enter the key to Search in a list
15
Performing Linear search
The Key is present at 8 Location
time efficiency of Linear search is: 0
Now Performing Binary Search
The Key is Not found Binary Search
time efficiency of Binary search is: 0
Now Performing Hash Function
Key is Found in Hashtable
--------------------------------
Process exited after 52.19 seconds with return value 0
Press any key to continue . . .
Please like it........
C++ please read all the question Create 3 large arrays to search, where the size will...
C++ please read all the question Create 3 large arrays to search, where the size will be variable up until it reaches your machines limit. They should contain the same information since we are going to compare 3 different algorithms.You are going to do operational studies on them to determine their order. O(N), O(log(N)), and O(1)? Search algorithms.Linear, Binary, Hash You should know which algorithms are what order,now you are going to prove it. Fill the 3 arrays with the...
Instead of using a linked list to resolve collisions, as in separate chaining, use a binary search tree. That is, create a hash table that is an array of trees. To display a small tree-based hash table, you could use an inorder traversal of each tree. The advantage of a tree over a linked list is that it can be searched in O(logN) instead of O(N) time. This time savings can be a significant advantage if very high load factors...
We know that binary search on a sorted array of size n takes O(log n) time. Design a similar divide-and-conquer algorithm for searching in a sorted singly linked list of size n. Describe the steps of your algorithm in plain English. Write a recurrence equation for the runtime complexity. Solve the equation by the master theorem.
please check my answers if it wrong answer me a) (25 points) Suppose that you are asked to analyze the performance. Algorithms operate on 1D array of size nor 2D a of the algorithms below, write down the Big O or order of grow terms of n. If the algorithm cannot be applied to the array, write 0(1), O(log n), O(n), O(n logn), 90), O(n"), O(n!). The will only be given for reasonable Big O answers. & algorithms for their...
Language = c++ Write a program to find the number of comparisons using the binary search and sequential search algorithms as follows: o Suppose list is an array of 1000 elements. o Use a random number generator to fill the list. o Use the function insertOrd to initially insert all the elements in the list. o You may use the following function to fill the list: void fill(orderedArrayListType& list) { int seed = 47; int multiplier = 2743; ...
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
Write and test a function in C++ that uses the binary search algorithm to search an array of sorted strings – use a do..while loop to allow user to perform multiple searches w/o terminating the program – see sample output below. Use this name array: string names[SIZE] = { "Collins, Bill", "Smith, Bart", "Allen, Jim", "Griffin, Jim", "Stamey, Marty", "Rose, Geri", "Taylor, Terri", "Johnson, Jill", "Allison, Jeff", "Looney, Joe", "Wolfe, Bill", "James, Jean", "Weaver, Jim", "Pore, Bob",...
for java 4. Instead of using a linked list to resolve collisions, as in separate chaining, use a binary search tree. That is, create a hash table that is an array of trees. To display a small tree-based hash table, you could use an inorder traversal of each tree. The advantage of a tree over a linked list is that it can be searched in O(logN) instead of O(N) time. This time savings can be a significant advantage if very...
Consider the function FINDDUPLICATES(A[0. 1) that returns a list of all duplicate items in the unsorted integer array A of size n. For example, given the array |3, 2, 4, 3], the function should return the value 3. For the array 11 2,3 5,5,5,66,81, the function should return an array (or list) 5,6 In this task, you will develop two alternative solutions for the FINDDUPLICATES(Ao..n 1 func- tion. In your implementations, you may call any of the algorithms introduced in...
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an array in ascending order. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that...