Question: Consider the following modified merge sort algorithm. Note that the Merge procedure is identical to the one used in the Merge-Sort algorithm we discussed

Consider the following modified merge sort algorithm. Note that the Merge procedure is identical to the one used in the Merge-Sort algorithm we discussed in class. Modified-Merge-Sort (A, p, r) // Input: An array A[p..r] of n pair-wise comparable elements // Output: Array A[p..r] sorted in non-decreasing order 1 if p < r 2 3 4 5 6 7 8 mid1= p + (r - p)/3 mid2 P + 2* (r p)/3 Modified-Merge-Sort (A, p, mid1) Modified-Merge-Sort (A, mid1 + 1, mid2) Modified-Merge-Sort (A, mid2 + 1, r) Merge (A, p, mid1, mid2) Merge (A, p, mid2, r) = 1. (6pts) Perform Modified-Merge-Sort(A, 1, 9) on array A[1..9] = . List all the updated arrays after each Merge operation. 2. (3pts) Formulate a recurrence relation to describe the running time of algorithm Modified-Merge-Sort (A, p, r). Make sure to specify the base case(s). 3. (3pts) Solve the recurrence relation to give a tight bound (using 8) on the algorithm's running time.

Step by Step Solution

★★★★★

3.50 Rating (157 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

1 After performing ModifiedMergeSortA updated arrays after each Merge operation are Merge A 1 ... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

To ensure that you can provide the best service to this client group, you have consulted a health and nutritionist specialist to provide advice on food types and the best diet which can be combined...

Angela owns 250 shares that currently trades at $80 each. She declares a 2-for-1 consolidation. What is the approximate value of her portfolio?

An ammonia bath is the one most widely used for depositing Pd-Ni alloy coatings. The article "Modelling of Palladium and Nickel in an Ammonia Bath in a Rotary Device" (Plating and Surface Finishing,...

Consider the following modified merge sort algorithm. It divides the input array into three subarrays, and then sorts each one recursively; after that, it merges the first two sorted subarrays and...

If you are in any kind of manufacturing, you will be required to budget direct[or raw] materials. For example in a steel mill one of the primary raw materials is iron ore. Lets say your product...

Consider the following " 3 - way merge sort" algorithm that takes input S , a sequence of n elements, where n = 3 m ( i . e . , n is a power of 3 ) and Merge 3 is a procedure that takes 3 sorted...

Problem 4. For this question, we will have to modify Merge sort algorithm. In the divide and conquer step, you will divide the array into thirds, recursively sort each third, and finally combine the...

C++ Linked List Implementation Motivation As we discussed in class, the data structures that you use to implement your program can have a profound impact on it's overall performance. A poorly written...

MATH 1P67: Mathematics for Computer Science Spring 2016 Assignment 3: Recursions and Complexity Due: Wednesday, June 29, at 19:00 (7:00 pm) 1. Double Tower of Hanoi contains 2n disks of n different...

Can you write a psedocode and make sure to comment each line of the psedocode do it in easier way? 2 . Create pseudocode for the following algorithm. To get credit for this problem, your pseudocode...

YOUR TASK As a Marketing Consultant, advice John Samson by preparing a strategic marketing plan to the Board to position HHRE as the market leader and a viable venture in the real estate business....

Question No. 4. A 5-star hotel has 200 rooms that has historically charged one set of prices for its room, which was Rs. 5000 per night. The variable cost for one room includes cleaning,...

Linux Systems Administration In this module's class activities, you acted as a system administrator in order to troubleshoot a malfunctioning Linux server. The senior administrator was quite pleased...

Draw the kinematic diagram of the following linkages and find their mobility using Gruebler's equation. 1 B 2 3 -O- D 6 C 4 Point C is not a joint. It is a significant point on link 5.

The Canadian Tire trying to expand into the USA Company: The Canadian Tire What are the sustainable strategic goals of the company? What aspects about the country could be good for the company on the...

All of the factors below would be considered 'negative' factors (or red flags) when evaluating going concern, EXCEPT: an increase in the current ratio denial of trade credit by suppliers an increase...

Before the latest financial crisis and recession, when was the largest recession of the past 50 years, and what was the cumulative loss in output over the course of the slowdown?

Write down a Verilog module implementation of a 2-to-4 decoder (and/or encoder).

Calculate (1.666015625 10 0 1.9760 10 4 ) + (1.666015625 10 0 -1.9744 10 4 ) by hand, assuming each of the values are stored in the 16-bit half precision format described in Exercise 3.27 (and...

Give an algorithm for constructing the sum-of-products representation for an arbitrary logic equation consisting of AND, OR, and NOT. The algorithm should be recursive and should not construct the...

Consider the same study by Heffner et al. (1974) and the data set described in Problems 4 and 5, where the response measured was the lever press rate (LPR) taken by a thirsty rat to press a lever and...

Consider a different (fictitious) study to compare two treatments for the relief of heartburn. This new study involves a two-period "cross-over" design in which each subject is given two...

Consider the same study by Heffner et al. (1974) and the data set described in Problem 4, in which the response measured was the lever press rate (LPR) used by a thirsty rat to press a lever and...