Question

Problem 1: Describe using pseudocode and implement an efficient algorithm for finding the ten largest elements in an array of size n. What is the running time of your algorithm?

Problem 2: An array A contains n-1 unique integersin the range [0, n-1]. There is one number from this range that is not in A. Design a O(n) algorithm for finding that number. Describe the algorithm in pseudocode. Implement the algorithm in Java. Hint : Consider computing a function of the integers in A that will immediately identify which one is missing.

Problem 3: Perform an experimental analysis of the two algorithms given below. Subsequently provide the growth functions and a BigOh analysis of the 2 algorithms.

public static double[] prefixAverage1(double[] x) {

int n = x.length;

double [] a = new double[n];

for (int j =0; j < n; j++)

{

double total =0;

for (int i =0; i <=j ; i++)

total += x[i];

a[j] = total / (j + 1);

}

return a;

}

public static double[] prefixAverage2(double[] x)

{

int n = x.length;

double [] a = new double[n];

double total = 0;

for (int j =0; j < n; j++)

{

total += x[i];

a[j] = total / (j + 1);

}

return a;

}

Answer 1

1.Finding 10 largest element in array

   Approach 1: A simple and straight forward approach would be to just sort the array and find the last 10 numbers . Time Complexity:O(nlogn).

Pseudo Code:

void findLargest(int [] arr){

if(arr.length < 10) return;

Arrays.sort(arr);

for(int i = arr.length-1; i >=arr.length - 10; i--){

print(arr[i]);

}

Approch 2: This is an efficient method. Here we use MinHeap to store 10 largest element:

Algorithm:

a.First we will create a MinHeap of first 10 elements in array.

b.We know the property of MinHeap as both child elements are greater than parent . Therefore we have minimun number as the root of MinHeap.

c. We start comparing the number in arr from 10 to n-1 with root of MinHeap. If number is greater we set this number as the root of MinHeap(index=0) and call heapify to maintain the property of heap.(Repeating this step would keep 10th largest as root of MinHeap and all other larger than root)

d. Traverse the MinHeap array to get 10 largest number.

Pseudo Code:

  void findLargest(int arr[]){

MinHeap minHeap = new MinHeap(10,arr); //Heapifying array from 0-9 index

for(int i=10;i<arr.length;i++){

if(arr[0] < arr[i]){

arr[0] = arr[i]; //setting greater element as root of MinHeap

minHeap.heapify(arr)

}

for(int i=0;i<10;i++)

print(arr[i]);

}

}

Time Complexity:O((n-10)Log10)

2. Numbers are given in the range [0,n-1] .So total numbers = n

We know sum of first n natural numbers = n*(n+1)/2

Here to find sum of first n-1 natural numbers(excluding 0 from sum) = n*(n+1)/2 - n = n*(n-1)/2

If one is missing Total Numbers in input = n-1

So to find the missing no. we can add all the number given in an array and substract from the sum.

Algorithm for above code:

void findMissin(int[] arr)

{

int n = arr.length + 1; //missing 1 number

int totalSum = n*(n-1)/2;

int arrSum = 0;

for(int i=0;i<arr.length;i++){

arrSum += arr[i];

}

print("Missing Number is" + totalSum-arrSum);

}

Although above can cause interger overlflow if n is large.

To handle that case what we can do is while adding from array we also subtract the number in the range

Just that the number from the range will be one step ahead as it contais the missing number.

int totalSum = 0;

for(int i=1;i<arr.length+1;i++){

totalSum += i;

totalSum -= arr[i-1];  

}

print("Missing Number is:" + totalSum);

Time Complexity:O(n)

3.Time Complexity Analysis

for prefixAverage1 - As for each iteration of outer loop, the inner loop will run for 1+2+3....(n-1) times.

Therefore keeping the summation it will run for n(n-1)/2 times = O(n^2) (ignoring lower order terms and constants)

for prefixAverage2 - As there is just 1 loop running for n times. The time complexity for it would be O(n)