Question

Counting evens

1. Write the pseudo-code for a brute force approach to counting the number of even integers in an array of n integers.

2. Write the pseudo-code divide-and-conquer algorithm for counting the number of even integers in an array of n integers.

3. Give the recurrence relation for the number of additions in your divide-and-conquer algorithm.  

Answer 1

Brute force approach pseudo code:

// function to count no. of even integers
// pseudo code
// input: arr : array of int, n: size of array
// 0 based indexing
// output: no. of even integers
// brute force approact

int countEven(int arr[],int n){
        int count = 0; 
        // loop through array
        for(int i=0;i<n;i++){
                if(arr[i]%2 == 0){ // even integer
                        count = count + 1;
                }
        }
        // return count value
        return count;
}

Divide and conquer approach:

// function to count no. of even integers
// pseudo code
// input: arr : array of int, s: starting index of array, e: last index of array
// initial call: countEven(arr,0,n-1); where n is size of array
// 0 based indexing
// output: no. of even integers
// divide and conquer approach

int countEven(int arr[],int s,int e){
        // base case
        if(s-e == 0){ // only one element then check it directly
                if(arr[s]%2 == 0 ){
                        return 1;
                } else{
                        return 0;
                }
        }
        // mid value of array
        int mid = (s+e)/2;
        // call to left half
        int count = countEven(arr,s,mid); 
        // call to right half
        count = count + countEven(arr,mid+1,e); // also add to count
        // return count value
        return count;
}

===============

Recurrence relation:

Let n be the size of array and T(n) represent no. of addition for array of size n.

T(1) = 0 // we directly return the value by checking, (base case)

T(n) = 2*T(n/2) + 1 // call to left and right half and we use one addition to count

==================

For any query coment