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...
-
The financial statements of Shoppers Drug Mart are presented in Appendix A at the end of this book. Instructions (a) Is Shoppers Drug Mart a service company, merchandising company, or manufacturing...
-
On June 1, $40,000 of treasury bonds were purchased between intrest dates. The broker commission was $600. The bonds pay interest at 12%, which is paid semiannually on January 1 and July 1. What is...
-
Does Fairmont have any personnel whose last name is similar?
-
Each of the following items must be considered in preparing a statement of cash flows (indirect method) for Turbulent Indigo Inc. for the year ended December 31, 2014. a) Plant assets that had cost...
-
1. Solve the following using convolution and correlation a. Let I={0, 0, 1, 0, 0} & Let k (mask) = {3, 2, 8} 3 3 b. Let I = & Let k (mask) = 3 3 1 24 3 4
-
TourneSol Canada, Ltd. is a producer of high quality sunflower oil. The company buys raw sunflower seeds directly from large agricultural companies, and refines the seeds into sunflower oil that it...
-
What Strengths are Four Seasons leverage against Market Wide Opportunities?
-
For the simplex tableau X2 $1 52 P RHS 4 1 0 0 29 3 0 1 0 50 -4 0 01 0 perform one pivot operation and enter the resulting tableau below. The pivot element has a box around it. X X2 X 3 3 -10 $2 P RHS
-
Discuss some of the key principles of Quantum Physics, such as Heisenberg's Uncertainty principle, the concept of superposition, and the phenomenon of quantum tunneling. Question 4. Application of...
-
Define and explain the formation of polar and non-polar covalent bonds. State and discuss the cause of their similarities and differences. Use the case of water and hydrocarbons as the basis for your...
-
YAG laser operates at approximately 1.06 m wavelength and has gain with spectral width = 150 GHz. a) For a simple air-filled resonator based on parallel-plane mirrors spaced by 10 cm, how many...
-
What process does the "GU-AG Rule" apply to in eukaryotes. If the AG sequence was mutated in exon 1 in a gene with 3 exons, how would this process be affected?
-
3. As the coronavirus spreads, colleges are scrambling to respond to potential health-care crises, campus closures, and other issues that are arising and evolving on a daily basis. A major challenge:...
-
10m solution. If Ka(HA) = 10 then pOH of solution will be [Given : log4=0.6] (A) 6.7 (B) Greater than 6.7 & less than 7.0 (C) Greater 7.0 & less than 7.3 (D) Greater than 7.3
-
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...
-
A Marist poll survey showed that 47% of respondents chose whatever as the most annoying phrase used in conversation. What is the probability of randomly selecting someone choosing something different...
-
According to the National Association for College Admissions Counseling and USA Today, 19.8% of college students take at least one class online. What is the probability of randomly selecting a...
-
Let R be the event of randomly selecting a senator and getting a Republican, and let D represent the event of randomly selecting a second different senator and getting a Democrat. Use words to...
Study smarter with the SolutionInn App