Skip to content

Instantly share code, notes, and snippets.

@huzaifaarain
Last active September 30, 2019 12:32
Show Gist options
  • Save huzaifaarain/fdc813a0568f50cd01b0fcc6fa86a060 to your computer and use it in GitHub Desktop.
Save huzaifaarain/fdc813a0568f50cd01b0fcc6fa86a060 to your computer and use it in GitHub Desktop.
Algo Fall 2019 - Mid 1 Problem 5
/*
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;
}
/*
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);
}
/*
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