1. Let S and T be two arrays of m and n elements, respectively. Write an algorit

Question

1. Let S and T be two arrays of m and n elements, respectively. Write an algorithm that finds all the common elements and stores them in an array U. Show that can be done in Q(n + m).

2. Show that the median of five numbers can be found by making six comparisons.

3.Write an algorithm that creates a 3-2 tree from a list of keys. Analyze your algorithm and show that results using order notation.

4.Write an algorithm that creates a 3-2 tree from a list of keys. Analyze your algorithm and show that results using order notation. 3n/2-2 if n is even, 3n/2-3/2 if n is odd

5. Write a probabilistic algorithm that determines whether an array of n elements has a majority element (the element that appear the most). Analyze your algorithm, and show the results using order notation

Explanation / Answer

1.Algorithm for finding the common elements and stores in an array U.

        As it is givent that S and T be two arrays of m and n elements, respectively.here we need to assume that they are both of equal sizes to prove the time complexity.

   for (int m = 0; m < length(S); m++) start with the index of S araay as m=0 and find the length of S and increase the value untill the condition fails.
   for (int n = 0; n < length[T]; n++) start with the index of T araay as n=0 and find the length of T and increase the value untill the condition fails.
if(s[m]==(T[n])) if the index of any element is found as same and it is dotred in a new array U.
  add(U[m]);
Here we are having the arrays are of equals size and hence the best way is to approach is sorted merge array hence the time complexity would be Q(n + m).

2. Show that the median of five numbers can be found by making six comparisons.

Let us assume that we are having the numbers as 5,4,3,2,1.and take the elements in a single set as (54321)

5:4 3:2 1 comparisons are as follows.

let us take two two elements as one set and compare them with one as other as we know that 4<5 and 2<3 1

now compare the numbers 4>2 hence it would be 4:2 3 comparisons

now take out the number 2 and compare 4 and 5 as 4<5 3 1

now compare 1 and 3 as 1<3 hence it would be 1:3 4 comparisons

now compare the elements 4 and 5 and 1 and 3 hence it would be 2 4<5 1<3

now compare the 4 and 1 4and 1 5 comparisons and take out 1,2 4<5 3

4:3 hence this proves the 6 comparisons

Finally we have the sorted elements as 1,2,3,4,5 hence this proves the five elemetns requires the six comparisions and it would be a median of 3.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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