Last active
September 30, 2019 12:32
-
-
Save huzaifaarain/fdc813a0568f50cd01b0fcc6fa86a060 to your computer and use it in GitHub Desktop.
Algo Fall 2019 - Mid 1 Problem 5
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Following algorithm decides as if a given number M is the median of A or | |
otherwise. The algorithm outputs either M if M is the median, a number M + 1 if median | |
is larger than M and the number M – 1 otherwise. Give a tight bound on the running | |
time of this algorithm | |
*/ | |
#include <bits/stdc++.h> | |
using namespace std; | |
/** | |
* @param A int type array | |
* @param n int type size of array A | |
* @param M int type median value | |
* @return int | |
*/ | |
int Median_Or_Otherwise(int A[],int n,int M); | |
int Median_Or_Otherwise(int A[],int n,int M){ | |
int LESS = 0, EQUAL = 0; | |
for (int i=0;i< n;i++){ | |
if(A[i] < M) | |
LESS = LESS + 1; | |
else if(A[i] == M) | |
EQUAL = EQUAL + 1; | |
} | |
if(LESS < n/2 && (LESS + EQUAL) >= n/2) | |
return M; | |
else if (LESS >= n/2) | |
return M - 1; | |
else | |
return M + 1; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Use the algorithm in Part a, and the strategy advocated by the assistant professor | |
to design a divide-and-conquer based algorithm for finding the required median. | |
*/ | |
#include <bits/stdc++.h> | |
#include "./problem_5_part_a.h" | |
/** | |
* @param A int type array | |
* @param n size of array | |
* @param min Minimum value of median a | |
* @param MAX maximum value of median a | |
* @return int | |
*/ | |
int Divide_And_Conquer_Median(int A[],int n,int min,int MAX); | |
int Divide_And_Conquer_Median(int A[],int n,int min,int MAX){ | |
if(min == MAX) | |
return min; | |
int M = round((min + MAX) / 2); | |
int X = Median_Or_Otherwise(A,n,M); | |
if(M==X) | |
return M; | |
if(X < M) | |
return Divide_And_Conquer_Median(A,n,min,M-1); | |
else | |
return Divide_And_Conquer_Median(A,n,M+1,MAX); | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
An assistant professor at NUCES-FAST-LHR proposed a divide and conquer based strategy | |
(quite similar to binary search) for finding median for the above situation. | |
He said that to find median between two limits min {e.g. 1} and MAX {e.g. log(n) } one | |
should try the middle number M = rounded{ (min + Max)/2 } and check if M is the | |
median. However, if M is not the median then it must either be strictly greater than M or | |
strictly less than M | |
Further, a number M is median if number of elements strictly smaller than M is less | |
than n/2 and if number of elements smaller than or equal to M is greater than or equal | |
to n/2 | |
*/ | |
#include <bits/stdc++.h> | |
#include "./problem_5_part_b.h" | |
using namespace std; | |
/** | |
* @brief Helper function to print values of array | |
* | |
* @param A int type array | |
* @param n int type size of array | |
*/ | |
void print_array(int A[],int n); | |
int main(int argc, char const *argv[]) | |
{ | |
int n = 32; | |
int A[32] = {2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5}; | |
cout<<"Size of array n is "<<n<<endl; | |
cout<<"Range of values in array is 1 ... to log2(32) + 1 which is "<<(log2(32) + 1)<<endl; | |
cout<<"Original array is"<<endl; | |
print_array(A,n); | |
int result = Divide_And_Conquer_Median(A,n,1,(log2(32) + 1)); | |
cout<<"Median value is "<<result<<endl; | |
return 0; | |
} | |
void print_array(int A[],int n){ | |
for(int i=0;i < n;i++){ | |
cout<<A[i]<<" "; | |
if(i+1 == n){ | |
cout<<endl; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment