1 Let S and T be two arrays of m and n elements respectively

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

Solution

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.