Question

Please post all code in Pseudo code. Please post ORIGINAL answers do not copy from similar...

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.

Homework Answers

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) )

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Please post all code in Pseudo code. Please post ORIGINAL answers do not copy from similar...
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. 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...
Do not copy from others! Thank you! Design an algorithm to find all the common elements...
Do not copy from others! Thank you! 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?
We are given an array A of size n containing n positive and negative integers (the...
We are given an array A of size n containing n positive and negative integers (the array is indexed starting from 0). Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n and Pk=j k=i A[k] is maximized. Input sequence: [2, -4, 1, 9, -6, 7, -3] Output: [1, 9, -6, 7] or i = 2 and j = 5 Input sequence: [1, 2, 3, 4, 5, 6, -3] Output: [1,...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort algorithm. The Merge step merges n elements which takes O(n) time. Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Any code that is found to exceed linear time will fail the tests. Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
Write a MIPS assembly program that sorts an array using bubble sort translating the C code...
Write a MIPS assembly program that sorts an array using bubble sort translating the C code int main(void) { int array[] = {10, 2, 7, 5, 15, 30, 8, 6}; // input array int arraySize = sizeof(array)/sizeof(array[0]); bool swapped = true; int j = 0; int tmp; while (swapped) { swapped = false; //Note : "j" , "arraySize - j" are optimizations to the bubble sort algorithm j++; // j= sorted elements int i=0; /* "arraySize - j" is used...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort algorithm. The Merge step merges n elements which takes O(n) time. Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Any code that is found to exceed linear time will fail the tests. Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] import java.util.Scanner; import java.util.ArrayList; public class Solution...
Matrix Multiplication with Threads - C/C++ **Read entire question before answering** **Don't copy / paste code...
Matrix Multiplication with Threads - C/C++ **Read entire question before answering** **Don't copy / paste code without testing it. I will downvote your answer and mark as spam.** I have posted this question several times, do not copy / paste the same code that has been posted, IT DOESN'T WORK!! In this assignment you will use the Pthreads library to write a program that multiplies two square arrays and compare the difference between the imperative and parallel implementations of this...
using matlab please present code for the following (ALL PARTS PLEASE AND THANK YOU) 1. No...
using matlab please present code for the following (ALL PARTS PLEASE AND THANK YOU) 1. No Input/No Output Write a function that has no input and no outputs. This function will simply display some text when it is called. (this is my code, are there suggestions for improvements?) function Display() disp('some text') end 2. 1 Input/No Outputs Write a function with one input and no outputs. This function will simply display a variable that is provided as an input argument....
We see that this computes the product of two matrices. Add a new kernel code, called...
We see that this computes the product of two matrices. Add a new kernel code, called sum, to compute the sum of the two matrices. #include <stdio.h> #include <math.h> #include <sys/time.h> #define TILE_WIDTH 2 #define WIDTH 6 // Kernel function execute by the device (GPU) __global__ void product (float *d_a, float *d_b, float *d_c, const int n) {    int col = blockIdx.x * blockDim.x + threadIdx.x ;    int row = blockIdx.y * blockDim.y + threadIdx.y ;    float...
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n],...
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n], an array of any n numbers in unknown order integer i, j, m fori=1ton−1 do swap A[i] ↔ A[m] // OUTPUT: A[1..n], its numbers now sorted in non-decreasing order m=i for j = i to n do if A[j] < A[m] then m = j Give a proof that this algorithm sorts its input as claimed.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT