P1 (40 points) Provide efficient algorithms for each of the problems below. You

ID: 3670777 • Letter: P

Question

P1 (40 points) Provide efficient algorithms for each of the problems below. You should describe the main idea in a few sentences and provide pseudo code. Your pseudocode can use any previously taught algorithm as a function call. Just specify what the call does and its time complexity. Also, write down the worst case complexities for your algorithms. Assume all arrays below are integer arrays.

(C, 10 points) Given unsorted arrays a and b of size n, do they have an element in common? Your solution must avoid sorting either array.

(D, 10 points) The rank of a given number e in an array a is the number of elements in a that are strictly less than e. Also, given array a, let minimum(a) represent the minimum element of a. Given unsorted arrays a and b of size n, find the rank of minimum(a) in the array b. Your solution must run in time (n).

Explanation / Answer

Assuming we can only read O(1) bits in O(1) time (anything else would be a rather exotic model of computation), there can be no algorithm solving the problem in O(n) worst case time complexity.

Proof Sketch: Each number in the input takes O(log(n ^ 100)) = O(100 log n) = O(log n) bits. The entire input therefore O(n log n) bits, which can not be read in O(n) time. Any O(n) algorithm can therefore not read the entire input, and hence not react if these bits matter.

Testing can be done as shown below :

Let's find k’th smallest element in time complexity better than O(nLogn). A simple optomization is to create aMin Heap of the given n elements and call extractMin() k times.
The following is C++ implementation of above method.

// A C++ program to find k'th smallest element using min heap

#include<iostream>

#include<climits>

using namespace std;

// Prototype of a utility function to swap two integers

void swap(int *x, int *y);

// A class for Min Heap

class MinHeap

{

int *harr; // pointer to array of elements in heap

int capacity; // maximum possible size of min heap

int heap_size; // Current number of elements in min heap

public:

MinHeap(int a[], int size); // Constructor

void MinHeapify(int i); //To minheapify subtree rooted with index i

int parent(int i) { return (i-1)/2; }

int left(int i) { return (2*i + 1); }

int right(int i) { return (2*i + 2); }

int extractMin(); // extracts root (minimum) element

int getMin() { return harr[0]; } // Returns minimum

};

MinHeap::MinHeap(int a[], int size)

{

heap_size = size;

harr = a; // store address of array

int i = (heap_size - 1)/2;

while (i >= 0)

{

MinHeapify(i);

i--;

}

// Method to remove minimum element (or root) from min heap

int MinHeap::extractMin()

{

if (heap_size == 0)

return INT_MAX;

// Store the minimum vakue.

int root = harr[0];

// If there are more than 1 items, move the last item to root

// and call heapify.

if (heap_size > 1)

{

harr[0] = harr[heap_size-1];

MinHeapify(0);

}

heap_size--;

return root;

}

// A recursive method to heapify a subtree with root at given index

// This method assumes that the subtrees are already heapified

void MinHeap::MinHeapify(int i)

{

int l = left(i);

int r = right(i);

int smallest = i;

if (l < heap_size && harr[l] < harr[i])

smallest = l;

if (r < heap_size && harr[r] < harr[smallest])

smallest = r;

if (smallest != i)

{

swap(&harr[i], &harr[smallest]);

MinHeapify(smallest);

}

// A utility function to swap two elements

void swap(int *x, int *y)

{

int temp = *x;

*x = *y;

*y = temp;

}

// Function to return k'th smallest element in a given array

int kthSmallest(int arr[], int n, int k)

{

// Build a heap of n elements: O(n) time

MinHeap mh(arr, n);

// Do extract min (k-1) times

for (int i=0; i<k-1; i++)

mh.extractMin();

// Return root

return mh.getMin();

}

// Driver program to test above methods

int main()

{

int arr[] = {12, 3, 5, 7, 19};

int n = sizeof(arr)/sizeof(arr[0]), k = 2;

cout << "K'th smallest element is " << kthSmallest(arr, n, k);

return 0;

}

Output: