Quiz 4 Binary Search vs. Brute Force Search Algorithms for Finding a Local Minim
ID: 3723481 • Letter: Q
Question
Quiz 4 Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two- Dimensional Array Due: March 6th. 2018:1 PM (Submit through Canvas In this project, you will implement the binary search-based (n) algorithm. to determine the local minimum in an 'n'x 'n' two-dimensional array (as discussed in Module 2) and compare its run-time performance with that of a brute force O(n algorithm that searches for the local minimum element by element until one is found. Note that both the binary search and the brute force search algorithms should stop once a local minimum is found. You should create random two-dimensional arrays (with numRows = numCols) with unique elements in the range [. numRows numCols] for the following values of numRows (numCols) and determine the average execution time of the binary search and the brute force search algorithms by running 200 trials for each of the numRows (numCols) values. Determine the running times in nano seconds or milli seconds, as appropriate. numRows (numCols) values: 4, 6, 8, 10, 15, 20, 25, 30, 35, 40, 50, 75, 100, 150, 200, 250, 300, 350 Plot the results with numRows in X-axis and the average execution times (in nanoseconds or milliseconds of the binary search and the brute force search algorithms in the Y-axis Submission (everything included in ONE PDF File Uploaded in Canvas) (1 65 pts) Code for the binary search and the brute force search algorithms (2-15 pts) Excel plots of the numRows vs. average execution times of the two algorithms (3- 20 pts) Your interpretation of the results.Explanation / Answer
Answer:
Please find solution below,if having any confusion in solution feel free to comment.
Note:Code for brute force search and binary search is in C.
For comparision between brute force na d binary search,lets take a sorted matrix given below and search for elelment 25 in both case.
5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26
Bruteforce search with time complexity O(n2)
#include <stdio.h>
#include <limits.h>
#include <time.h>
#include <sys/time.h>
int search(int mat[5][5], int n, int k)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(mat[i][j]==k)
{
// printf("localMinindex=(%d,%d)",i,j);
break;
}
}
}
}
int main() {
int i,j,r,c;
printf("Enter number of rows ");
scanf("%d",&r);
printf("Enter number of column ");
scanf("%d",&c);
int mat[r][c];
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&mat[i][j]);
}
}
int locmin=INT_MAX;
struct timeval timer_usec;
long long int timestamp_usec; /* timestamp in microsecond */
if (!gettimeofday(&timer_usec, NULL)) {
timestamp_usec = ((long long int) timer_usec.tv_sec) * 1000000ll +
(long long int) timer_usec.tv_usec;
}
else {
timestamp_usec = -1;
}
printf("%lld microseconds since epoch ", timestamp_usec);
int loop;
for(loop=1;loop<=100000;loop++)
{
search(mat, r, 25);
}
if (!gettimeofday(&timer_usec, NULL)) {
timestamp_usec = ((long long int) timer_usec.tv_sec) * 1000000ll +
(long long int) timer_usec.tv_usec;
}
else {
timestamp_usec = -1;
}
printf("%lld microseconds since epoch ", timestamp_usec);
return 0;
}
Binary search with time complexity O(nlogn)
#include <stdio.h>
#include <limits.h>
#include <time.h>
#include <sys/time.h>
int bsearch(int mat[5][5], int n, int k)
{
int i = 0, j = n-1; //set indexes for top right element
while ( i < n && j >= 0 )
{
if ( mat[i][j] == k )
{
// printf("n Found at %d, %d", i, j);
return 1;
}
if ( mat[i][j] > k )
j--;
else // if mat[i][j] < k
i++;
}
printf("n Element not found");
return 0; // if ( i==n || j== -1 )
}
int main() {
int i,j,r;
printf("Enter number of rows & column ");
scanf("%d",&r);
int mat[r][r];
for(i=0;i<r;i++)
{
for(j=0;j<r;j++)
{
scanf("%d",&mat[i][j]);
}
}
// int locmin=INT_MAX;
struct timeval timer_usec;
long long int timestamp_usec; /* timestamp in microsecond */
if (!gettimeofday(&timer_usec, NULL)) {
timestamp_usec = ((long long int) timer_usec.tv_sec) * 1000000ll +
(long long int) timer_usec.tv_usec;
}
else {
timestamp_usec = -1;
}
printf("%lld microseconds since epoch ", timestamp_usec);
int loop;
for(loop=1;loop<=100000;loop++)
{
bsearch(mat, 5, 25);
}
if (!gettimeofday(&timer_usec, NULL)) {
timestamp_usec = ((long long int) timer_usec.tv_sec) * 1000000ll +
(long long int) timer_usec.tv_usec;
}
else {
timestamp_usec = -1;
}
printf("%lld microseconds since epoch ", timestamp_usec);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.