P1 Provide efficient algorithms for each of the problems below. You should descr

Question

P1 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. (A, 5 points) Given sorted arrays a and b, each of size n, do they have an element in common? (B, 5 points) Given a sorted array a of size m and an unsorted array b of size n, do they have an element in common? Your solution must not sort the array b. (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). (E, 5 points) Given min heaps a of size m and b of size n, merge them into a single min heap of size m + n. Assume that m n. (F, 5 points) Given two unsorted arrays a and b, each of size n, output “YES” if every element of a is strictly less than every element of b, and “NO” otherwise.

P2 A company constantly receives (integer) price quotes for its product over the internet, and at any point, we are asked to store the k smallest price quotes, where k is fixed by the manager in advance. We consider three possible data structures for the task of maintaining the k smallest quotes so far. 1. A min heap data structure with k elements in it. 2. A balanced binary search tree data structure. 3. A sorted array of k elements. For each of the structures, write down how you would update the data structure when a new quote comes in and the worst case running time.

Explanation / Answer

A.

a[n]; b[n];

Given Both arrays a & b are sorted.
There might be a possiblity that they
have an element in common but its not necessary as the both share only same size.

Pseudocode:

Declarations
   int a[n],b[n];
   int i=0,j=0;
for i=0 to i<n
   for j=0 to j<n
       if a[i]==b[j]
       return true
       end if
   j++;
   end
i++;
end

Time Complexity : O(n^2)

B.

a[n]; b[n];

Given: Array a is sorted & b is not sorted.
There might be a possiblity that they have an element in common but
its not necessary as the both share only same size.

Declarations
   int a[n],b[n];
   int i=0,j=0;
for i=0 to i<n
   for j=0 to j<n
       if a[i]==b[j]
       return true
       end if
   j++;
   end
i++;
end

Time Complexity : O(n^2)

C.

a[n]; b[n];

Given: both a & b are not sorted.
There might be a possiblity that they have an element in common but
its not necessary as the both share only same size.

Declarations
   int a[n],b[n];
   int i=0,j=0;
for i=0 to i<n
   for j=0 to j<n
       if a[i]==b[j]
       return true
       end if
   j++;
   end
i++;
end

Time Complexity : O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.