2. Consider the following type of Bucket Sort. You have an array of n words, each...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. Consider the following type of Bucket Sort. You have an array of n words, each composed of the usual 26 English letters A,B,..., Z Suppose you placed the words in 8 buckets based on the first letter, with buckets for ABC, DEF, GHI, JKL, MN, OPQR, ST, and UVWZYZ. The plan is to sort the 8 buckets and then stack the sorted buckets back into the original array. Don't worry about storage for the buckets. 2.1. (2). The best possible case is for each of the 8 buckets to contain exactly n/8 words. Suppose we sort each of these 8 buckets with selection sort. (not a good sorting method, but it does have an exact work function). Give an exact expression for the total work w(n) required in this best case to sort all 8 buckets. 2.2. (2). The worst case would be if one bucket had all n words and the other 7 buckets had zero works. Give an exact expression for the total work w(n) in this situation. 2.3. (2) To get an idea of the average work, a "probably below average" situation would be if 4 buckets each had n/4 words and the other 4 had zero words. Give an exact expression for the total work w(n) in this situation. Make an effort to write the answer in as simple a form as possible. 2.4. (2) How much work (number if IF statements) is needed to sort the 12 words into the 8 buckets? Hint: is there an optimal way to do this? 2.5. (2) Combining the work discussed in 2.4 and the best case discussed in 2.1, what is the total work needed in the best case? 2.6. (2) Now consider the above problems, except with k buckets rather than 8. Assume that kn. Give a formula in terms of n and k for the best case total work. (formula should reduce to that of 2.5 ifk = 8). 2.7. (2) Consider problem 2.6 except this time use quicksort rather than selection sort for sorting the buckets. For simplicity, assume that quicksort of a size n array always takes exactly Was(n) = anlgn work for some constant a. Give an exact formula for the work needed in terms of n. k. and a. 2. Consider the following type of Bucket Sort. You have an array of n words, each composed of the usual 26 English letters A,B,..., Z Suppose you placed the words in 8 buckets based on the first letter, with buckets for ABC, DEF, GHI, JKL, MN, OPQR, ST, and UVWZYZ. The plan is to sort the 8 buckets and then stack the sorted buckets back into the original array. Don't worry about storage for the buckets. 2.1. (2). The best possible case is for each of the 8 buckets to contain exactly n/8 words. Suppose we sort each of these 8 buckets with selection sort. (not a good sorting method, but it does have an exact work function). Give an exact expression for the total work w(n) required in this best case to sort all 8 buckets. 2.2. (2). The worst case would be if one bucket had all n words and the other 7 buckets had zero works. Give an exact expression for the total work w(n) in this situation. 2.3. (2) To get an idea of the average work, a "probably below average" situation would be if 4 buckets each had n/4 words and the other 4 had zero words. Give an exact expression for the total work w(n) in this situation. Make an effort to write the answer in as simple a form as possible. 2.4. (2) How much work (number if IF statements) is needed to sort the 12 words into the 8 buckets? Hint: is there an optimal way to do this? 2.5. (2) Combining the work discussed in 2.4 and the best case discussed in 2.1, what is the total work needed in the best case? 2.6. (2) Now consider the above problems, except with k buckets rather than 8. Assume that kn. Give a formula in terms of n and k for the best case total work. (formula should reduce to that of 2.5 ifk = 8). 2.7. (2) Consider problem 2.6 except this time use quicksort rather than selection sort for sorting the buckets. For simplicity, assume that quicksort of a size n array always takes exactly Was(n) = anlgn work for some constant a. Give an exact formula for the work needed in terms of n. k. and a.
Expert Answer:
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these computer network questions
-
Python and most Python libraries are free to download or use, though many users use Python through a paid service. Paid services help IT organizations manage the risks associated with the use of...
-
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...
-
The table contains real data. MySpace U.S. Advertising Revenue ($ millions) (a) Determine the maximum and minimum values for each variable in the table. (b) Use your results from part (a) to find an...
-
Cindy Alexander, Turner, Inc.'s vice president of marketing has received a sales call from a vendor of customer relationship management (CRM) software. The vendor claims that the software and other...
-
Some lemon juice has a hydronium-ion concentration of 5.0 10-3 M. What is the pH of the lemon juice?
-
1. What was the dilemma that MAHLE was facing? 2. Why did MAHLE seek out SAP and MHP to help with its logistics problems? 3. What benefits did MAHLE receive from implementing the SAP Transportation...
-
The following are selected transactions of Andreu Company. Andreu prepares financial statements quarterly. Jan. 2 Purchased merchandise on account from Diego Company, $30,000, terms 2/10, n/30....
-
Future value is used to determine the value of dollar payments in the future, whereas present value indicates the current value of future dollars. Either simple interest, where interest is only...
-
XYZ is a calendar-year corporation that began business on January 1, 2017. For 2017, it reported the following information in its current year audited income statement. Notes with important tax...
-
If the sum of first 7 terms of an A.P is 49 and that of its first 17 terms is 289, find the sum of first n terms of the A.P.
-
What is the purpose of foreign exchange risk management?
-
____________ are words or phrases that let the audience know where you are within the presentation.
-
What objectives does the Bankruptcy and Insolvency Act seek to achieve?
-
How can services be exported?
-
How is a consumer debtor defined?
-
Palisade Creek Co. is a merchandising business that uses the perpetual inventory system. During May, the last month of the fiscal year, transactions were completed. In Part 1 of this problem, the...
-
An interest bearing promissory note for 90 days at 5.6% p.a. has a face value of $120,000. If the note is discounted 20 days after the issue date at a rate of 6.8% p.a., calculate the amount of...
-
Determine the running time of Shellsort for a. Sorted input b. Reverse-ordered input
-
Write a program that reads N points in a plane and outputs any group of four or more colinear points (i.e., points on the same line). The obvious brute-force algorithm requires O(N4) time. However,...
-
In a recent court case, a judge cited a city for contempt and ordered a fine of $2 for the first day. Each subsequent day, until the city followed the judge's order, the fine was squared (that is,...
-
Listed below are additional research questions and hypotheses from actual published articles. For each hypothesis, identify the independent and dependent variable. a. It is expected that achievement...
-
Name the scale of measurement (nominal, ordinal, interval, ratio) for each of the following variables: a. One's age (in years) b. Size of soft drink (small, medium, large, extra large) c. Voting...
-
A researcher hypothesizes that drivers who use cellular phones will get into a greater number of traffic accidents than drivers who do not use these phones. For this example, a. What are the...
Study smarter with the SolutionInn App