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.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

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

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
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,...
(a) Write an algorithm (use pseudo-code) to determine whether a function f ∶ Z100 → Z100...
(a) Write an algorithm (use pseudo-code) to determine whether a function f ∶ Z100 → Z100 is surjective. That is, supply a “Method” to go with Input: A function (array) f with f(i) ∈ Z100 for i = 0, 1, . . . , 99. Output: Boolean B. B=‘true’ if f is surjective, ‘false’ otherwise. Try to make your algorithm as efficient as possible. Do NOT include an implementation of your algorithm in a programming language. (b) How many comparisons...
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...
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...
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....
In this problem your task is to find a missing number. The input will always consist...
In this problem your task is to find a missing number. The input will always consist of an array of n positive integers such that the difference between every two consecutive numbers is a fixed constant but one integer is missing. See below for two example inputs/outputs: Input sequence: [0, 2, 4, 6, 10] Output: missing number is 8 Input sequence: [1, 4, 7, 13, 16] Output: missing number is 10 Note that in the first example the constant c...
Describe recursive algorithms for the following variants of the text segmentation problem. Assume that you have...
Describe recursive algorithms for the following variants of the text segmentation problem. Assume that you have a subroutine IsWord that takes an array of characters as input and returns True if and only if that string is a “word”. (a) Given an array A[1 .. n] of characters, compute the number of partitions of A into words. For example, given the string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL. Do this by appropriately modifying the...
q : explain the code for a beginner in c what each line do Question 2....
q : explain the code for a beginner in c what each line do Question 2. The following code defines an array size that sums elements of the defined array through the loop. Analyze the following code, and demonstrate the type of error if found? What we can do to make this code function correctly ? #include <stdio.h> #define A 10 int main(int argc, char** argv) { int Total = 0; int numbers[A]; for (int i=0; i < A; i++)...
USE PYTHON LANGUAGE PLEASE FOCUS YOU SHOULD ENTER AN ARRAY AND THEN THE PROGRAM GIVE OUTPUT(...
USE PYTHON LANGUAGE PLEASE FOCUS YOU SHOULD ENTER AN ARRAY AND THEN THE PROGRAM GIVE OUTPUT( TRUE/ FALSE) QUIZ 8 Array Challenge Have the function ArrayChallenge(arr) take the array of numbers stored in arr and return the string true if any two numbers can be multiplied so that the answer is greater than double the sum of all the elements in the array. If not, return the string false. For example: if arr is [2, 5, 6, -6, 16, 2,...
For each pseudo-code function below (after the next ==== line), write a useful loop invariant capturing...
For each pseudo-code function below (after the next ==== line), write a useful loop invariant capturing correctness for the main loop in each of the following programs and briefly argue initialization, preservation, and termination. EXAMPLE PROBLEM: //Function to return the max of an array A Maximum(array of integers A) Local integer integer m m=0 for i = 1 to n if A[i] > m then m = A[i] end function Maximum EXAMPLE SOLUTION: The loop invariant is m = max(0,...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT