IN C PROGRAMMING

Sample Cumulative Question #6 Note: The following problem is excerpted from the final exam I gave in Fall 2015. That semester, I had not covered the Fox, Goose, and Bag of Beans problem in class when I covered backtracking. On the actual exam, there was of course much more space for a written response 6. (Wildcard) Fox, goose, and bag of beans puzzle Here is a puzzle for you (paraphrased from Wikipedia): A farmer goes to a market and purchases a fox, a goose, and a bag of beans. On his way home, the farmer approaches a river where there is a boat he can use to cross to the other side. However, the boat only has room for the farmer and exactly one of his purchases - the fox, the goose, or the bag of beans. The farmer can't leave the goose alone with the bag of beans, or else the goose will eat the beans. The farmer can't leave the fox alone with the goose, or else the fox will eat the goose. (So, for example, if the farmer starts by ferrying the bag of beans across the river and drops it off there, then returns to the side where he left the fox and the goose, he'll find that the fox has eaten the goose. Goodbye, goose.) The central question to this puzzle is: What steps must the farmer take to get all his purchases safely to the other side? (You will derive that solution in part (c) of this problem, below.) (a) (3 pts) What is the name of the problem solving technique have we discussed in class that lends itself to solving this problem? (b) (7 pts) Briefly explain how you would represent the different states of this problem in memory if you were tasked with using as few bytes as possible to represent a state. (L.e., what kind of data type(s) and/or data structure(s) would you use? Is there a technique or data structure we covered in class that lends itself to a memory-efficient representation here?) For example, one state we have to represent, the initial state of the problem, has the farmer, fox, goose and bag of beans on one side of the river. Another state might be that the farmer is on one side of the river with a bag of beans, and the the goose and fox are left on the other side of the river. (Of course that's a bad state to be in, because the fox will eat the goose if the farmer isn't there to stop it.) Keep in mind that we also need a way to efficiently check off every state we've processed as we try to solve the problem, so we don't get stuck in an infinite loop, processing the same states over and over again without making any actual progress toward the final goal. Briefly explain keep track of which states have been processed already, given the representation you've chosen for the different states in this problem. (You don't need to write any code; just give a brief, high-level overview of the idea behind your approach.) (c) (10 pts) Trace through this problem on paper using the technique you named in part (a). Then, once you've found the solution, very clearly list the steps the farmer must take to get the fox, goose, and bag of beans across the river Sample Cumulative Question #6 Note: The following problem is excerpted from the final exam I gave in Fall 2015. That semester, I had not covered the Fox, Goose, and Bag of Beans problem in class when I covered backtracking. On the actual exam, there was of course much more space for a written response 6. (Wildcard) Fox, goose, and bag of beans puzzle Here is a puzzle for you (paraphrased from Wikipedia): A farmer goes to a market and purchases a fox, a goose, and a bag of beans. On his way home, the farmer approaches a river where there is a boat he can use to cross to the other side. However, the boat only has room for the farmer and exactly one of his purchases - the fox, the goose, or the bag of beans. The farmer can't leave the goose alone with the bag of beans, or else the goose will eat the beans. The farmer can't leave the fox alone with the goose, or else the fox will eat the goose. (So, for example, if the farmer starts by ferrying the bag of beans across the river and drops it off there, then returns to the side where he left the fox and the goose, he'll find that the fox has eaten the goose. Goodbye, goose.) The central question to this puzzle is: What steps must the farmer take to get all his purchases safely to the other side? (You will derive that solution in part (c) of this problem, below.) (a) (3 pts) What is the name of the problem solving technique have we discussed in class that lends itself to solving this problem? (b) (7 pts) Briefly explain how you would represent the different states of this problem in memory if you were tasked with using as few bytes as possible to represent a state. (L.e., what kind of data type(s) and/or data structure(s) would you use? Is there a technique or data structure we covered in class that lends itself to a memory-efficient representation here?) For example, one state we have to represent, the initial state of the problem, has the farmer, fox, goose and bag of beans on one side of the river. Another state might be that the farmer is on one side of the river with a bag of beans, and the the goose and fox are left on the other side of the river. (Of course that's a bad state to be in, because the fox will eat the goose if the farmer isn't there to stop it.) Keep in mind that we also need a way to efficiently check off every state we've processed as we try to solve the problem, so we don't get stuck in an infinite loop, processing the same states over and over again without making any actual progress toward the final goal. Briefly explain keep track of which states have been processed already, given the representation you've chosen for the different states in this problem. (You don't need to write any code; just give a brief, high-level overview of the idea behind your approach.) (c) (10 pts) Trace through this problem on paper using the technique you named in part (a). Then, once you've found the solution, very clearly list the steps the farmer must take to get the fox, goose, and bag of beans across the river