1. This problem was inspired by an ad on facebook was for the game "Taonga: The Island Farm". I will be changing the rules to make ours easier. The input to this problem is a tangle of knotted ropes and the output is either the sequence of allowed steps to untangle them or the statement that it is impossible. This is an example input After a Single Operation 3 mal The yellow and orange block were swapped with orange moving on top- Counter Examples Can you untangle this only moving the bottom weights? This is a knot which is impossible to solve moving only the bottom These are not tangled because for free the orange can be moved off the top. The following is an algorithm for the evil adversary to produce the tangled input. Each rope has one end attached to the ceiling, spaced along the wall. Each rope follows its own windy path down the wall. The only restriction is that following the rope, this path can never head back up. It is mono-tone down. For example, the both pink ropes are not allowed. The bottom of each rope is attached to its own heavy weight spaced along the floor. The paths of these ropes can cross over each other multiple times. (Lets assume that three ropes never cross in the exact same spot.) For each such crossing of two ropes, the adversary will decide which of the two should be on top. 1 The only operation that you are allowed is choose two consecutive weight on the floor switch their order along the floor by moving one of them in front of the other. You can move and shake the ropes at anytime for free. Clearly, there are knots that can be untied only by passing one of the ends of the rope through a loop. Given that you cannot lift the weighted rope bottoms off the floor, it is possible that untying this mess is impossible. (a) Loop Invariant Algorithm: Providing a loop invariant algorithm for this problem. Are there legal examples of tangled ropes for which untangling is impossible? (b) Running Time: Provide an upper and a lower bound on the number of weight switch operations that your algorithm performs (as a function of some parameters of the input). Prove this using your measure of progress. (c) Optimal: An interesting algorithmic question is whether or not your algorithm is optimal. In other words, are there legal examples of tangled ropes which can be untangles with fewer weight switch operations than your algorithm performs? I confess that I initially had a "proof that my algorithm is optimal. Can you guess what my proof was? But then I found the silly example with the spring shaped orange rope in which the weights don't have to move at all to "untangle the ropes. Quite frankly, my algorithm would use many many more operations than this. (d) Bonus Question: (Do NOT do this problem. I neither want you to spend too much time on it or make the TA read too much garbage. I have no idea how to answer this myself. We can chat about it later if people want.) Add to the precondition that the ropes have been untangled as much as possible without moving the weighted rope bottoms. For example, the silly spring shaped orange rope example would be completely untangled before starting. With this preprocessing, is your algorithm optimal? Either prove it is or give an example in which it is not. For example, can you untangle the example in the first figure with fewer operations than your algorithm? Hard Example: Now change the pre-condition so that each rope can travel along the wall both up and down but is not allowed to cross itself. Consider only the example in the last figure. Does your algorithm fail on this example? Why or why not? Either show how to untangle this one example without lifting the weighted rope bottoms off the floor or "prove" that it can't be done. I will give my usual hint. If you are doing something hard, then you are doing it wrong. If you are curious, the problem is harder in "Taonga: The Island Farm", because the weights can only be in an small number of fixed places and you can only move them one at a time from where it is to an empty location. I'm including the power point slides containing the figures in case it will help you try things out. copies a page. Right clicking on rope allows you to edit its defining points. Don't get bothered by the little line segments. I put them there to fake which line crosses on top. 2 1. This problem was inspired by an ad on facebook was for the game "Taonga: The Island Farm". I will be changing the rules to make ours easier. The input to this problem is a tangle of knotted ropes and the output is either the sequence of allowed steps to untangle them or the statement that it is impossible. This is an example input After a Single Operation 3 mal The yellow and orange block were swapped with orange moving on top- Counter Examples Can you untangle this only moving the bottom weights? This is a knot which is impossible to solve moving only the bottom These are not tangled because for free the orange can be moved off the top. The following is an algorithm for the evil adversary to produce the tangled input. Each rope has one end attached to the ceiling, spaced along the wall. Each rope follows its own windy path down the wall. The only restriction is that following the rope, this path can never head back up. It is mono-tone down. For example, the both pink ropes are not allowed. The bottom of each rope is attached to its own heavy weight spaced along the floor. The paths of these ropes can cross over each other multiple times. (Lets assume that three ropes never cross in the exact same spot.) For each such crossing of two ropes, the adversary will decide which of the two should be on top. 1 The only operation that you are allowed is choose two consecutive weight on the floor switch their order along the floor by moving one of them in front of the other. You can move and shake the ropes at anytime for free. Clearly, there are knots that can be untied only by passing one of the ends of the rope through a loop. Given that you cannot lift the weighted rope bottoms off the floor, it is possible that untying this mess is impossible. (a) Loop Invariant Algorithm: Providing a loop invariant algorithm for this problem. Are there legal examples of tangled ropes for which untangling is impossible? (b) Running Time: Provide an upper and a lower bound on the number of weight switch operations that your algorithm performs (as a function of some parameters of the input). Prove this using your measure of progress. (c) Optimal: An interesting algorithmic question is whether or not your algorithm is optimal. In other words, are there legal examples of tangled ropes which can be untangles with fewer weight switch operations than your algorithm performs? I confess that I initially had a "proof that my algorithm is optimal. Can you guess what my proof was? But then I found the silly example with the spring shaped orange rope in which the weights don't have to move at all to "untangle the ropes. Quite frankly, my algorithm would use many many more operations than this. (d) Bonus Question: (Do NOT do this problem. I neither want you to spend too much time on it or make the TA read too much garbage. I have no idea how to answer this myself. We can chat about it later if people want.) Add to the precondition that the ropes have been untangled as much as possible without moving the weighted rope bottoms. For example, the silly spring shaped orange rope example would be completely untangled before starting. With this preprocessing, is your algorithm optimal? Either prove it is or give an example in which it is not. For example, can you untangle the example in the first figure with fewer operations than your algorithm? Hard Example: Now change the pre-condition so that each rope can travel along the wall both up and down but is not allowed to cross itself. Consider only the example in the last figure. Does your algorithm fail on this example? Why or why not? Either show how to untangle this one example without lifting the weighted rope bottoms off the floor or "prove" that it can't be done. I will give my usual hint. If you are doing something hard, then you are doing it wrong. If you are curious, the problem is harder in "Taonga: The Island Farm", because the weights can only be in an small number of fixed places and you can only move them one at a time from where it is to an empty location. I'm including the power point slides containing the figures in case it will help you try things out. copies a page. Right clicking on rope allows you to edit its defining points. Don't get bothered by the little line segments. I put them there to fake which line crosses on top. 2