2. (Worth: 2 points. Page limit: 1 sheet; 2 sides) The manager at a local toy st
ID: 3714440 • Letter: 2
Question
2. (Worth: 2 points. Page limit: 1 sheet; 2 sides) The manager at a local toy store, Algos-R-Us, is in need of some algorithmic expertise. A few days back he received a shipment of Russian nesting dolls that was damaged in transit. All of the sets were disassembled, that is, none of the dolls were nested inside another. There are n dolls in all and k boxes to pack them into. The manager needs to figure out how to assemble the n dolls into k or fewer nested sets, if at all possible. For any two dolls, the only way to tell whether one can be nested inside the other is by direct examination. For some pairs of dolls, neither can be nested inside the other (e.g., due to one being shorter but wider than the other). Design and analyze an efficient algorithm to find an arrangement of the n dolls into k or fewer nested sets, if such a partition exists To be precise, the input to your algorithm consists of the numbers n and k, and for each pair i,j E [n], a bit that specifies whether or not doll i can be nested inside doll j. Your algorithm should return an arrangement of the n dolls into k or fewer nested sets, if such an arrangement exists, and return "Error" if not. Hint: Think of the arrangement of dolls as a matching that matches each contained doll with the doll that directly contains it. So each doll is matched at most once to a doll containing it, and at most once to a doll contained in itExplanation / Answer
The algorithm can be as follows:
In the first go equal sized dolls can be separated into different groups.Originally all the
dolls are in some k sets or less than k sets so we will definatltly get equal number of same
sized dolls.Once we get such separate groups we can pick one doll from each group to make a set.
The order of complexity of this algorithm will be O(n) as we will be considering all the dolls
one by one to make separate groups.After that making a set will be O(1).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.