Algo Fall 2019 - Mid 1 Problem 4

problem_4_part_a.h

/*
write an algorithm called Count-Values that takes as
input two arrays A and C and then compute value of each counter and store it in array C.
Your algorithm must have ϴ (n) time complexity.
Hint C[ A[i] ] = C[ A[i] ] + 1 might be a useful statement here 
*/
#include <bits/stdc++.h>
using namespace std;

/**
 * @param A int type array A 
 * @param C int type array C
 * @param n int type size of array A
 */
void count_values(int A[],int C[],int n);

void count_values(int A[],int C[],int n){
    for(int i = 0;i < n;i++){
        C[A[i]] = C[A[i]] + 1;
    }
}

problem_4_part_b.h

/*
write the algorithm called Find-Median that uses the counters computed
in part a to find the median elements of A. This algorithm must have a running time
bounded by ϴ ( log(n) ). 
*/
#include <bits/stdc++.h>
using namespace std;
/**
 * @brief write the algorithm called Find-Median that uses the counters computed
in part a to find the median elements of A. This algorithm must have a running time
bounded by
 * 
 * @param C int type array 
 * @param n int type size of array
 * @return int index of element which is the median of array
 */
int FindMedianUsingCounters(int C[],int n);

int FindMedianUsingCounters(int C[],int n){
    int CumSum = 0;
    int l = 0;
    int h = 0;
    for(int k = 0;k < log2(n) + 1 ; k++){
        CumSum = CumSum + C[k];
        if(CumSum >= n/2){
            return k;
        }
    }
    return -1;
}

problem_4_part_c.cpp

#include <bits/stdc++.h>
#include "./problem_4_part_a.h"
#include "./problem_4_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);
/**
 * @brief generate array of size n with all elements having zero
 * 
 * @param A int type array
 * @param n size of n
 */
void zeros_array(int A[],int n);

int main(int argc, char const *argv[])
{

    int n = 32;
    int A[32] = {1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5,5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
    int c_size = log2(n)+1;
    int C[c_size];
    cout<<"Size of array n is "<<n<<endl;
    cout<<"Range of values in array is 1 ... to log2(32) + 1 which is "<<(log2(n) + 1)<<endl;
    cout<<"Original array is "<<endl;
    print_array(A,n);
    cout<<"Initializing array c with zero elements "<<endl;
    zeros_array(C,c_size);
    print_array(C,c_size);
    cout<<"Calling Count Values "<<endl;
    count_values(A,C,n);
    cout<<"Array C after calling Count Values "<<endl;
    print_array(C,c_size);
    cout<<"Calling FindMedianUsingCounters on array c "<<endl;
    int M = FindMedianUsingCounters(C,n);
    cout<<"Median value is "<<M<<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;
        }
    }
}

void zeros_array(int A[],int n){
    for (int i = 0; i <= n;i++){
        A[i] = 0;
    }
}

result_screenshot.png