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.

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 it