Question

In: Computer Science

Write the algorithm, following the ideas given in class, for merging two sorted arrays into one...

Write the algorithm, following the ideas given in class, for merging two sorted arrays into one sorted array. Note the algorithm is not the one for merge sort. 2) What is the best asymptotic upper bound for the algorithm? List reasoning steps.

Expert Solution

Algorithm:

1. Let two sorted array be A and B of size m and n respectively.

2. Create a new array C of size m+n

3. initialize-variables i=0,j=0,k=0

4. while I<n and j<m

if A[i] < B[j]

C[k] = A[i]

i = i+1, k = k+1

else

C[k] = B{j]

i = i+1, k=k+1

5. if i=n meaning all values of array A has been added to C. We need to assigned restover value of array B to C

while j < m

C[k] = B[j]

k=k+1, j=j+1

6. if j=m meaning all values of array B has been added to C. We need to assigned restover value of array A to C

while i < n

C[k] = A[j]

k=k+1, i=i+1

7. C is is merged array formed by merging two sorted array A and B

The asymptotic upper bound for the algorithm will be O(m+n).

This is because all the assignment operator takes constant time and loop is looping for m+n times. In this algorithm, we will get time complexity of a + b*(m+n) where a and b are positive constants and a represent assignment operation time and b times assignment operation in each loop for m+n times so b*(m+n). Hence, the asymptotic upper bound for the algorithm will be O(m+n).

venereology answered 1 year ago

Write and test a merge function that uses a recursive algorithm to merge two sorted arrays...

Write and test a merge function that uses a recursive algorithm to merge two sorted arrays of integers. Neither list contains duplicates, and the resulting list should not contain duplicates either. Hint: You may want to call a helper function from merge. PROGRAM: C

Write a method that takes two Sorted Arrays of different sizes and merges them into one...

Write a method that takes two Sorted Arrays of different sizes and merges them into one sorted array, and use the method to write a full recursive Merge Sort Algorithm.

Pseudocode and algorithm of merging k sorted list with running time O(Nlogk).

Given two unsorted arrays of integers. a) Write a pseudocode algorithm which will output only the...

Given two unsorted arrays of integers. a) Write a pseudocode algorithm which will output only the integers not common to both arrays. When writing pseudocode, consider that no implementation for data structures or algorithms exist. b) Implement your algorithm in Modern C++

(Subject: Data Structures and Algorithms) Faster merging. You are given two sorted sequences of $\lg{n}$ and...

(Subject: Data Structures and Algorithms) Faster merging. You are given two sorted sequences of $\lg{n}$ and $n-1$ keys. We would like to merge those two sorted sequences by performing $o(n)$ comparisons. (Note we are interested in comparisons, not running time.) Show how this can be done or argue that it cannot be done. Note: In class we showed that ordinary merging would require no more than $\lg{n}+n-1+1= n + \lg{n}$ comparisons.

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n]...

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n] and B[1 . . . n] and an integer k. Describe an algorithm to find the kth smallest element in the union of A and B in O(log n) time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B; if k = n, your algorithm should return the median of A ∪ B.) You can assume...

(Linear time algorithm for finding duplicates of two sorted arrays, 20pt) Devise a linear time O(m+n)...

(Linear time algorithm for finding duplicates of two sorted arrays, 20pt) Devise a linear time O(m+n) algorithm to find the duplicates between two sorted arrays (m, n are the sizes of two arrays). For instance, for inputs {1,3,5,7} and {1,2,3,4}, the correct outputs should be {1,3

in java code In the class Hw2, write a method removeDuplicates that given a sorted array,...

in java code In the class Hw2, write a method removeDuplicates that given a sorted array, (1) removes the duplicates so that each distinct element appears exactly once in the sorted order at beginning of the original array, and (2) returns the number of distinct elements in the array. The following is the header of the method: public static int removeDuplicates(int[ ] A) For example, on input A=0, 0, 1, 1, 1, 2, 2, 3, 3, 4, your method should:...

Write a method, twoSumSorted2, that solves the following variant of the Two-Sum problem: Given a sorted...

Write a method, twoSumSorted2, that solves the following variant of the Two-Sum problem: Given a sorted array of integers where each element is unique and a target integer, return in an Array List, the indices of all pairs of elements that sum up to the target. Each pair of indices is also represented as an Array List (of two elements). Therefore, the method returns an Array List of an Array List of size 2. If no pair in the input...

Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of...

Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of comparable objects L, and a new item x, find the location (index) of x or indicated that x is not in L. 5a) Give a recursive algorithm for binary search. No, while, for, repeat etc statements are allowed. Only if, if else and assignment statements are allowed. 5b) Write a difference equation for the running time of your Binary Search algorithm. Solve your equation...