Consider mergesort as discussed in class. Instead of dividing the set of numbers into two nearly...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider mergesort as discussed in class. Instead of dividing the set of numbers into two nearly equal parts, we can partition the set of n numbers into three nearly equal n+1 n+2 parts containing [], [], and [2] numbers, sort each part separately, and then combine them 3 together into one sorted list. (a) [10 points] Write the pseudocode of the combining algorithm. (b) [20 points] Analyze the running time (or, equivalently, the number of comparisons, where a comparison is the act of comparing two numbers) made by this new version of mergesort in the worst case. A correct answer should give the recurrence, explain why it is correct and then present its solution. Try to get as tight a bound as you can. Excessively loose bounds on the number of comparisons will incur a loss of most points for this problem. For simplicity, you may assume that n is a multiple of 3 (hence, you could just write 1/3 instead of [1/3] or [n/3]). Consider mergesort as discussed in class. Instead of dividing the set of numbers into two nearly equal parts, we can partition the set of n numbers into three nearly equal n+1 n+2 parts containing [], [], and [2] numbers, sort each part separately, and then combine them 3 together into one sorted list. (a) [10 points] Write the pseudocode of the combining algorithm. (b) [20 points] Analyze the running time (or, equivalently, the number of comparisons, where a comparison is the act of comparing two numbers) made by this new version of mergesort in the worst case. A correct answer should give the recurrence, explain why it is correct and then present its solution. Try to get as tight a bound as you can. Excessively loose bounds on the number of comparisons will incur a loss of most points for this problem. For simplicity, you may assume that n is a multiple of 3 (hence, you could just write 1/3 instead of [1/3] or [n/3]).
Expert Answer:
Related Book For
Understanding Basic Statistics
ISBN: 9781111827021
6th Edition
Authors: Charles Henry Brase, Corrinne Pellillo Brase
Posted Date:
Students also viewed these programming questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
Portray in words what transforms you would have to make to your execution to some degree (a) to accomplish this and remark on the benefits and detriments of this thought.You are approached to compose...
-
Describe three ways in which a gradual increase in an extracellular signal can be sharpened by the target cell to produce an abrupt or nearly all-or none response.
-
It has long been a concern that there is a wage gap between men and women in the United States with some reports suggesting that women only make $0.77 for every dollar earned by a man. Design a study...
-
Assume Evco, Inc., has a current stock price of $50 and will pay a $2 dividend in one year; its equity cost of capital is 15%. What price must you expect Evco stock to sell for immediately after the...
-
What are the criteria used for estimating the total effort required by a salesperson to cover a territory?
-
The Buffalo Snow Shoe Company is considering manufacturing radial snow shoes, which are more durable and offer better traction. Buffalo estimates that the investment in manufacturing equipment will...
-
As of December 31, 2014, Toyota company: had assets of 13,050,000, liabilities of 4,650,000, share capital of 3,300,000 and retained earnings of 5,100,000. What is the Total equity as of that date?
-
You are planning to switch your cell phone provider. The Cellular worksheet presents three options for a cell phone plan with the new company. You could choose a pay-as-you-go plan, a traditional...
-
What is the function of Bluetooth in GPS?
-
When bankruptcy proceedings reach a point at which the business will likely cease to exist, financial statements are prepared on a Select answer from the options below limited entity basis. modified...
-
Regarding financial instruments. Financial assets are classified in the following measurement categories: Question 39 options: Amortized cost and depreciable expenses. Fair carrying net book value....
-
Explain how the five components of the Relational Leadership Model (inclusion, empowerment, purposefulness, ethical behaviors, and process orientation) can help healthcare leaders to address the...
-
1. Provide examples of how each of the following functional areas: A. Operations, B. finance, C. marketing, D. Human Resources, and E. IT impacts one another within healthcare organizations,...
-
identify one of your favorite products in indicate which strategy (pull or push) is used to manufacture and distribute that product. briefly explain why you answered the way you did. second, we're on...
-
Consider an economy that does not trade, has an income tax rate of 20% and a constant aggregate price level. The government expenditure multiplier is 2.5. Which of the following can we conclude?
-
Data on weekday exercise time for 20 females, consistent with summary quantities given in the paper An Ecological Momentary Assessment of the Physical Activity and Sedentary Behaviour Patterns of...
-
The following table shows the Myers-Briggs personality preferences for a random sample of 406 people in the listed professions (Myers-Briggs Type Indicator Atlas of Type Tables, by Macdaid,...
-
Sketch the areas under the standard normal curve over the indicated intervals and find the specified areas. Between z = 0 and z = 3.18
-
Look at the ogive. What percentage of the wells have a pH less than 8.15? Suppose a certain crop can tolerate irrigation water with a pH between 7.35 and 8.55. What percentage of the wells could be...
-
What is the relation between degrees Fahrenheit and degrees Rankine? And the relation between degrees Celsius and Kelvin?
-
State Newton's second law as you would apply it to a control mass.
-
Define a 1-pound force in terms of the acceleration it will give to a 1-pound mass. Give a similar definition for a newton in the SI system.
Study smarter with the SolutionInn App