Children’s toy maker Problem.
Problem (page limit: 3 pages)
Children’s toymaker AlgosRUs is creating a stacking puzzle where n oddly shaped discs need to be placed on k pegs, and has employed you to help with the task. Each disc can either be placed directly on a peg or must be placed on top of another disc that is strictly larger than it in all directions. Your task is to decide whether n given shapes can be assembled into k “stacks” to be placed on the pegs. As input to the problem, you are given an n x ti matrix (7, where for all i, j E ink = I if disc i can be placed on disc j and Cii = 0 otherwise. You can assume that the given matrix represents a collection of shapes that are physically possible. Given n, C, and k as input, your goal is to design an algorithm that will output “Yes” if a feasible arrangement of the n discs on k pegs exists, and “No” otherwise. For example, suppose that n = 4 and the matrix C is given by:
1 0 1 0 0 0 [() 0 1 0 1 0 0 0 0
Then the discs can be arranged on two pegs as shown in the picture below. However, the discs cannot be arranged on a single peg.
V le .16.16.
top view side view
1
(a) Show that the following greedy algorithm does NOT solve this problem correctly by providing a counterexam-ple. Make sure you include the matrix C and either a description of the shapes consistent with C or a diagram showing the shapes.
Algorithm 1: Greedy
Input: The list of discs D, the compatibility matrix C, and the number of pegs k I for i 4— 1 to k do 2 [ Find the largest number of discs from the list D that can be put on one peg, call it ni, and remove these discs from the list D; 3 if ni + n2 + … + nk = n then 4 L return YES s else 6 L return NO
Line 2 can be done with a dynamic programming algorithm, but you do not need to specify the details. If your counterexample relies on a particular tie-breaking rule (i.e., a rule that specifies which discs to remove in line 2 when there are multiple longest sequence of discs that can be put on one peg), please specify it. I lowever, to obtain full marks for this part, your counterexample should not rely on the tie-breaking rule.
(b) Design an algorithm that solves this problem and has runtime polynomial in n. Provide a brief proof of correct-ness, as well as an analysis of the running time of your algorithm. Hint: try to reduce this problem to maximum flow, minimum cut, or some other application of network flow discussed in the lectures. You do not need to present an algorithm for solving the problem you reduce to, but make sure you explain how the reduction is made and argue its correctness.
The post Children’s toy maker Problem appeared first on My Assignment Online.
