8. Breaking bag. A bag is an abstract data type which may hold any number of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
8. Breaking bag. A bag is an abstract data type which may hold any number of objects. You may query the bag to determine how many objects are in the bag. This takes constant time. You may also apply the probabilistic operation split to a bag, which partitions the objects in the given bag into two new bags. All you know about split is that for every pair of objects in the input bag, the probability that both objects end up in the same output bag is < 1/2. Also, if a bag contains n objects, applying split to the bag takes time O(n). 3 Your goal is to design and analyze a probabilistic algorithm that takes as input a bag containing n objects and produces as output n bags such that each output bag contains a single object. The ordering of the output bags is irrelevant. Your algorithm should run in expected time O(nlogn). Here is an outline you should follow: (a) The algorithm is the obvious divide and conquer algorithm, using the split operation to get two sub- problems, and then recursing on both, as necessary. Write out this algorithm. (b) To analyze the running time, consider any two objects in the original bag, and argue that after d levels of recursion, the probability that they remain in the same bag is at most 2-d. (c) Using (b), argue that for any particular object in the original bag, the probability that it is not in a bag by itself after d levels of recursion is at most 2-d(n - 1). Hint: union bound. = (d) Using (c), show that for any particular object i in the original bag, if Di is the depth in the recursion tree at which i ends up in a bag by itself, then E[Di] O(logn). Hint: use the tail sum formula E[Di] = d>1 Pr[Di d]. (e) Finally, argue that the running time T is O(i (Di + 1)), where the sum is over all objects i in the original bag, and from this and part (d), argue that E[T] = O(nlogn). Hint: linearity of expectation. 8. Breaking bag. A bag is an abstract data type which may hold any number of objects. You may query the bag to determine how many objects are in the bag. This takes constant time. You may also apply the probabilistic operation split to a bag, which partitions the objects in the given bag into two new bags. All you know about split is that for every pair of objects in the input bag, the probability that both objects end up in the same output bag is < 1/2. Also, if a bag contains n objects, applying split to the bag takes time O(n). 3 Your goal is to design and analyze a probabilistic algorithm that takes as input a bag containing n objects and produces as output n bags such that each output bag contains a single object. The ordering of the output bags is irrelevant. Your algorithm should run in expected time O(nlogn). Here is an outline you should follow: (a) The algorithm is the obvious divide and conquer algorithm, using the split operation to get two sub- problems, and then recursing on both, as necessary. Write out this algorithm. (b) To analyze the running time, consider any two objects in the original bag, and argue that after d levels of recursion, the probability that they remain in the same bag is at most 2-d. (c) Using (b), argue that for any particular object in the original bag, the probability that it is not in a bag by itself after d levels of recursion is at most 2-d(n - 1). Hint: union bound. = (d) Using (c), show that for any particular object i in the original bag, if Di is the depth in the recursion tree at which i ends up in a bag by itself, then E[Di] O(logn). Hint: use the tail sum formula E[Di] = d>1 Pr[Di d]. (e) Finally, argue that the running time T is O(i (Di + 1)), where the sum is over all objects i in the original bag, and from this and part (d), argue that E[T] = O(nlogn). Hint: linearity of expectation.
Expert Answer:
Answer rating: 100% (QA)
a The algorithm can be described as follows 1 If the bag contains only one object create a bag conta... View the full answer
Related Book For
Cost management a strategic approach
ISBN: 978-0073526942
5th edition
Authors: Edward J. Blocher, David E. Stout, Gary Cokins
Posted Date:
Students also viewed these programming questions
-
The new line character is utilized solely as the last person in each message. On association with the server, a client can possibly (I) question the situation with a client by sending the client's...
-
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...
-
Consider : You have been asked to evaluate whether your organization's current pay structure makes sense in view of what competing - address the following: How would you determine what organizations...
-
Data for Brigus Wholesale Ltd. are presented in P5-6B. Instructions (a) Calculate the profit margin and gross profit margin. (b) The vice-president of marketing and director of human resources have...
-
Write a paper on HLI yes HLI, Human life interaction. For this discussion I want you to forget about the computer. Look for two life Interactions. One Positive and One Frustrating, Photos are...
-
How does a lockbox system contribute to internal control over cash receipts.
-
Brooks Company carries three inventory items. The following information pertains to the ending inventory : Required a. Determine the ending inventory that Brooks will report on the balance sheet,...
-
The Segway is a two-wheeled self-balancing electric vehicle, as shown in Fig. 1. In this problem, we only consider the translational motion of the vehicle and rotation of the control panel bar. The...
-
The names of the employees of Matson Office Systems and their regular salaries are shown in the following payroll register. Note that Wayne and Young are paid monthly on the last payday, while all...
-
Which impression management tactic is Cassandra using when she asks for help planning the retirement party when she could do it easily on her own? a . self - promotion b . supplication c ....
-
Determine the output from the following code segment: int outer = 1; while (outer < 4) { int inner = 1; while (inner
-
Consider the program in Fig. 8.10 where Lines 22 and 23 are swapped. Draw a series of contour diagrams to show the state of execution for \(n=3\). import java.util.*; class Ch8Sample2 ( public static...
-
Write a program that asks a user to enter a file name and three numbers, and then store the three numbers in the user-specified file. After the execution of the program, open the file with a utility...
-
Determine the output from the following code segment: String star; star int i; for (i=0; i <5;i++) { } System.out.println (star); star + star;
-
Trace the program in Fig. 8.1 for \(x=2\) and \(n=5\) and draw the tree similar to the one in Fig. 8.21. import java.util.*; class Ch8Samplel { public static void main(String[] args) { Scanner...
-
A company reports the following intangibles at December 31, 2019, prior to impairment testing: Book value Customer lists $1,500,000 Brand names 5,200,000 Goodwill 8,000,000 The customer lists have a...
-
Assessing simultaneous changes in CVP relationships Braun Corporation sells hammocks; variable costs are $75 each, and the hammocks are sold for $125 each. Braun incurs $240,000 of fixed operating...
-
Earth Baby Inc. (EBI) recently celebrated its tenth anniversary. The company produces organic baby products for health-conscious parents. These products include food, clothing, and toys. Earth Baby...
-
Listed below are selected items from the cost-of-quality (COQ) report for Watson Products for last month. Category Amount Rework ........... $ 725 Equipment maintenance ...... 1,154 Product testing...
-
Healthy Selections Cereals Inc. (HSC) is a large food-processing company specializing in whole-grain, high-energy, low-calorie and low-fat cereals that appeal to the health-conscious consumer. HSC...
-
What are some reasons a potential prospect might not be readily accessible? How far should you go to try to overcome such an accessibility problem before you move to the next lead?
-
List three or four criteria you could use to qualify a lead as a likely prospect. How would you find out if the lead meets these criteria?
-
Who is currently in your own network that you could use for prospecting? How might you add to your network?
Study smarter with the SolutionInn App