Input: data: array with n integers Input: n: size of data Output: permutation of data such...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Input: data: array with n integers Input: n: size of data Output: permutation of data such that data[1] data[2] ... < data[n] 1 Algorithm: StoogeSort 2 if n1 then 3 return data 4 else if n 2 then if data[1]>data[2] then end Swap them third [n/3] return data 9 else 10 11 12 13 14 StoogeSort(data[1..n-third]) 15 end StoogeSort(data third..n]) StoogeSort(data[1..n-third]) return data 1. Develop a recurrence for the worst case time complexity of the StoogeSort algorithm above. Show your work. Note: StoogeSort is a joke sorting algorithm. It is correct but has poor performance. 2. Use the Master Theorem to solve your recurrence in the previous question. Show your work. If the Master Theorem does not apply, explain why it does not. 3. Sketch and analyze a recursion tree for the recurrence T(n) 21(n/4)+ e(n). You may use the Master Theorem to check your work, but only your recursion tree will be considered. 4. Suppose that data is an array of size n that contains the value n followed by 1 to -1. For example, if n = 5, data =[5, 1,2,3,4]. What sorting algorithm would you recommend to use to sort data? Briefly justify your answer. Input: data: array with n integers Input: n: size of data Output: permutation of data such that data[1] data[2] ... < data[n] 1 Algorithm: StoogeSort 2 if n1 then 3 return data 4 else if n 2 then if data[1]>data[2] then end Swap them third [n/3] return data 9 else 10 11 12 13 14 StoogeSort(data[1..n-third]) 15 end StoogeSort(data third..n]) StoogeSort(data[1..n-third]) return data 1. Develop a recurrence for the worst case time complexity of the StoogeSort algorithm above. Show your work. Note: StoogeSort is a joke sorting algorithm. It is correct but has poor performance. 2. Use the Master Theorem to solve your recurrence in the previous question. Show your work. If the Master Theorem does not apply, explain why it does not. 3. Sketch and analyze a recursion tree for the recurrence T(n) 21(n/4)+ e(n). You may use the Master Theorem to check your work, but only your recursion tree will be considered. 4. Suppose that data is an array of size n that contains the value n followed by 1 to -1. For example, if n = 5, data =[5, 1,2,3,4]. What sorting algorithm would you recommend to use to sort data? Briefly justify your answer.
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
chegg Push and Pull Production Control Systems: MRP and JIT MCQ
-
Q1. You have identified a market opportunity for home media players that would cater for older members of the population. Many older people have difficulty in understanding the operating principles...
-
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...
-
On January 1, Year 2, PAT Ltd. acquired 90% of SAT Inc. when SATs retained earnings were $900,000. There was no acquisition differential. PAT accounts for its investment under the cost method. SAT...
-
A flip coil is a device used to measure a magnetic field. A coil of radius r, N turns, and electrical resistance R is initially perpendicular to a magnetic field of magnitude B. The coil is connected...
-
Ferris Company began January with 6,000 units of its principal product. The cost of each unit is $8. Merchandise transactions for the month of January are as follows:
-
The Thermo-Bond Manufacturing Company maintains its fixed-asset records on its computer. The fixed-asset master file includes the following data items: Required Refer to Table 9-7, which describes...
-
This is really an odd situation, said Jim Carter, general manager of Highland Publishing Company. We get most of the jobs we bid on that require a lot of press time in the Printing Department, yet...
-
7E Waterway Company exchanged equipment used in its manufacturing operations plus $4,140 in cash for similar equipment used in the operations of Wildhorse Company. The following information pertains...
-
The magnitude of the net force exerted in the x direction on a 3.00-kg particle varies in time as shown in the figure below. {Be sure to include a unit vector with your numerical answers to the...
-
Acme Corp. just paid a dividend of $3.00 per share (ie., D 0 = $3.00). The dividend is expected to grow at a constant rate of 4% per year. What is the expected dividend at the end of year three (D 3...
-
Suppose that there is a bond with 12 years left to maturity. The face value of the bond is $1,000. Coupon rate is 15%, and YTM is 12%. Coupons are paid semiannually. What is the price that you are...
-
What is the difference between tacit and explicit knowledge? describe an example of each. How might an organization manage tacit knowledge?
-
How does the application of advanced probabilistic risk assessment (PRA) techniques, such as fault tree analysis and event tree analysis, enhance the identification and quantification of hazards in...
-
Discuss the role of human factors in hazard analysis. How do techniques like Human Reliability Analysis (HRA) contribute to understanding and mitigating risks associated with human errors in...
-
Choose two examples of the "rights of an owner" and compare them in detail. e.g., sell, grant rights to third party interests, lease, mortgage, water rights, air space, quiet enjoyment, mineral rights
-
How many years will it take a $700 balance to grow into $900 in an account earning 5%?
-
Let H be a class of hash functions in which each hash function h H maps the universe U of keys to {0, 1, . . . , m 1}. We say that H is k-universal if, for every fixed sequence of k distinct keys x...
-
Show how to multiply the complex numbers a + bi and c + di using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component ac - bd...
-
Suppose that we are given a linear program L in standard form, and suppose that for both L and the dual of L, the basic solutions associated with the initial slack forms are feasible. Show that the...
-
Brian Hughes and Wendy Perez formed a partnership five years ago. The partnership has been very successful and is growing rapidly. The partners are evaluating future actions for the next five years....
-
Lola Stroud invests \($30,000.00\) in a partnership. Her partner, Juan Santo, invests \($50,000.00\). Miss Stroud has 10 years' experience in a similar business; Mr. Santo has no experience. Miss...
-
Where should the method of distributing partnership earnings be stated?
Study smarter with the SolutionInn App