Consider the following modified merge sort algorithm. Note that the Merge procedure is identical to the...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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] = <9, 4, 6, 3, 7, 2, 8, 1, 5>. 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. 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] = <9, 4, 6, 3, 7, 2, 8, 1, 5>. 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.
Expert Answer:
Answer rating: 100% (QA)
1 After performing ModifiedMergeSortA updated arrays after each Merge operation are Merge A 1 ... View the full answer
Related Book For
Computer Organization and Design The Hardware Software Interface
ISBN: 978-0124077263
5th edition
Authors: David A. Patterson, John L. Hennessy
Posted Date:
Students also viewed these 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,...
-
Fill in each blank so that the resulting statement is true. I find (f g)(x) by replacing each occurrence of x in the equation for_______ with________ .
-
Compare this problem with the preceding problem. A plane sound wave in air at 20C, with wavelength 589 mm, is incident on a smooth surface of water at 25C, at an angle of incidence of 3.50. Determine...
-
Becker Products Company produces three products from a joint source. A single raw material is introduced into Process I from which products A, B, and C emerge. Product A is considered to be a...
-
The distribution of the ages of the winners of the Tour de France from 1903 to 2016 is approximately bell-shaped. The mean age is 27.9 years, with a standard deviation of 3.3 years. Use the...
-
Calculating NPV and IRR a project that provides annual cash flows of $24,000 for nine years costs $110,000 today is this a good project if the required return is 8 percent? What if its 20 per- cent?...
-
You are given the following information about aggregate demand at the existing price level for an economy: (1) consumption = $500 billion (2) investment = $50 billion (3) government purchases = $10...
-
In Problem 5-8, suppose that the daily demand at area 3 drops to 4 million gallons. Surplus production at refineries 1 and 2 is diverted to other distribution areas by truck. The transportation cost...
-
Define the word stakeholder in relation to an IT development project. You work for a small research organization with a number of branches throughout the country. At the moment each of these branches...
-
In preparing to launch a global project in Brazil. You are planning to visit to Brazil to interview potential global team members. You know that it is important to be aware of the value differences...
-
Produce a factual and concise biography, not exceeding three paragraphs, addressing the following: A description of critical professional experiences, qualifications, and achievements. A description...
-
What has been your personal experience with discrimination when looking for a job? Other than the suggestions by Ms. Block on what employers can do to reduce bias during selection processes, what...
-
A disk of radius R = 11.56 cm is centered at the origin and lies in the y-z plane. The disk has a surface charge density o = 4.81 x 10-6 C/m. Evaluate the electric field E(x) produced by this disk...
-
The Unsurpassed 125-year-old network that feeds Mumbai Respond to the following: What are key elements of the Mumbai Dabbawallas food delivery process that make it challenging operationally? What...
-
An investor is planning to invest in the bond market and has the following choices: Bond A: This is a coupon bond from AB Ltd. The bond has a face value of $1000 and a coupon rate of 6.25% paid...
-
a. What is the cost of borrowing if Amarjit borrows $28 500 and repays it over a four-year period? b. How many shares of each stock would he get if he used the $28 500 and invested equally in all...
-
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...
-
What is the purpose of a drilling machine ? Explain its working principle.
-
Describe the quick return motion mechanism for a shaper.
-
How drilling machines are classified?
Study smarter with the SolutionInn App