Question

Please post all code in Pseudo code. Please post ORIGINAL answers do not copy from similar questions. Please post in a format that can be directly copied. Reasoning on answers would be most helpful but not required. Thank you in advance for your help.

1.Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5. What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?

2. Consider the following algorithm for finding the distance between the two closest elements in an array of numbers.

ALGORITHM MinDistance(A[0..n − 1])//Input: Array A[0..n − 1] of numbers

//Output: Minimum distance between two of its elements

dmin ← ∞
for i ← 0 to n − 1 do

forj ←0ton−1do
ifi̸=j and|A[i]−A[j]|<dmin d m i n ← | A [ i ] − A [ j ]|

return dmin

Make as many improvements as you can in this algorithmic solution to the problem. If you need to, you may change the algorithm altogether; if not, improve the implementation given.

3.a.Consider the definition-based algorithm for adding two n × n matrices. What is its basic operation? How many times is it performed as a function of the matrix order n? As a function of the total number of elements in the input matrices?

b. Answer the same questions for the definition-based algorithm for matrix multiplication.

Answer 1

Solution to Question 1:

PseudoCode:

m = arr1.length
n = arr2.length

index1 = 0
index2 = 0

while ( index1 < m and index2 < n ){
  
   if( arr1[index1] == arr2[index2] ):
       index1 = index1 + 1
       index2 = index2 + 1
       print(arr1[index1])
      
   else if ( arr1[index1] < arr2[index2] ):
       index1 = index1 + 1
      
   else:
       index2 = index2 + 1
      
}

Maximum Number of Comparisons: Minimum of m and n, ie: O( min(m,n) )