Assignments

Homework	[15 points] A farmer went to a market and purchased a wolf, a goat, and a cabbage. There is a river the farmer has to cross to bring the three things home. The farmer owns a boat. The boat capacity is two. Only the farmer can row the boat. In the absence of the farmer, the wolf eats the goat or the goat eats the cabbage. What is the strategy to transport the farmer and all three purchases to the other side of the river safely? [3 points] Define a state. Write the start, final, and invalid states. [10 points] Construct a state diagram. [2 points] Write the two optimal solutions. Write the minimum of trips. [15 points] There are two empty containers: a 3-liter container and a 5-liter container. There is a fresh pond with water that can be used to either fill up or empty a container. Three operations are allowed: fill, empty, and transfer. How would you measure exactly 4 liters of water using the two containers and the pond in the minimum number of steps/operations? [3 points] Define a state. [10 points] Construct a state diagram. [2 points] Write the optimal solution. Write the minimum number of steps/operations. [15 points] There are 9 identical-looking coins; one of these coins is defective and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the lighter coin with a two-arm weighing balance scale? [10 points] Draw the decision tree showing all possible options. [3 points] Write the solution clearly in words using step-by-step instructions. [2 points] Write the minimum number of weighings needed. [15 points] A good king has a cellar with 10 bottles of wine. A bad minister who had a deal with the neighboring king decides to kill the good king. He sends his most trustworthy servant to poison the wine bottles. The poison is so strong that even if diluted an unlimited number of times it still can kill a person. The king's guards catch and kill the servant after the servant has poisoned only one bottle. The guards do know that exactly one bottle is poisoned but do not know which one. The guards also know that it takes a day for the poison to have its effect. The king decides to get some rats to taste the wines and identify the poisoned bottle. What strategy can the king use to identify the poisoned bottle in 1 day and minimizing the total number of rats used? [10 points] Draw the table using the binary numbers strategy to show which rats sip wine from which bottle. [3 points] Explain the method of finding the poisoned bottle from the rats clearly in words using step-by-step instructions. [2 points] Write the number of rats required and report how many of them can die in the worst case. [15 points] There is a switch room and a light room. There are 10 switches in the switch room and 10 bulbs in the light room. There is a long corridor between the switch and the bulb room. One cannot see the contents/state in one room being in another room. It is not known which switch corresponds to which bulb. Assume that you are initially in the switch room, all switches are off, and hence all bulbs are off. How do you find the one-to-one correspondence between the switches and the bulbs minimizing the number of trips to the light room? [10 points] Draw the table using the binary numbers strategy to explain your method/approach. [3 points] Explain your method clearly in English using step-by-step instructions. [2 points] Write the number of trips to the light room. A trip is defined as the movement from the switch room to the light room. [15 points] We want to measure any integer weight in the range [1, 15] using a two-sided weighing balance using a minimum number of weights. Explain how can we solve the problem assuming: (a) We can place weights only on one side, and [5 points] Write the table. [2 points] Explain the method and write the minimum number of weights. (b) We can place weights on either side of the weighing balance. [5 points] Write the table. [3 points] Explain the method and write the minimum number of weights. [10 points] Explain in detail: (i) [5 points] What is your favorite puzzle (not covered in the class) and why? and (ii) [5 points] What puzzle-solving techniques did you learn in this course?

Homework

[15 points] A farmer went to a market and purchased a wolf, a goat, and a cabbage. There is a river the farmer has to cross to bring the three things home. The farmer owns a boat. The boat capacity is two. Only the farmer can row the boat. In the absence of the farmer, the wolf eats the goat or the goat eats the cabbage. What is the strategy to transport the farmer and all three purchases to the other side of the river safely?
[3 points] Define a state. Write the start, final, and invalid states.
[10 points] Construct a state diagram.
[2 points] Write the two optimal solutions. Write the minimum of trips.
[15 points] There are two empty containers: a 3-liter container and a 5-liter container. There is a fresh pond with water that can be used to either fill up or empty a container. Three operations are allowed: fill, empty, and transfer. How would you measure exactly 4 liters of water using the two containers and the pond in the minimum number of steps/operations?
[3 points] Define a state.
[10 points] Construct a state diagram.
[2 points] Write the optimal solution. Write the minimum number of steps/operations.
[15 points] There are 9 identical-looking coins; one of these coins is defective and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the lighter coin with a two-arm weighing balance scale?
[10 points] Draw the decision tree showing all possible options.
[3 points] Write the solution clearly in words using step-by-step instructions.
[2 points] Write the minimum number of weighings needed.
[15 points] A good king has a cellar with 10 bottles of wine. A bad minister who had a deal with the neighboring king decides to kill the good king. He sends his most trustworthy servant to poison the wine bottles. The poison is so strong that even if diluted an unlimited number of times it still can kill a person. The king's guards catch and kill the servant after the servant has poisoned only one bottle. The guards do know that exactly one bottle is poisoned but do not know which one. The guards also know that it takes a day for the poison to have its effect. The king decides to get some rats to taste the wines and identify the poisoned bottle. What strategy can the king use to identify the poisoned bottle in 1 day and minimizing the total number of rats used?
[10 points] Draw the table using the binary numbers strategy to show which rats sip wine from which bottle.
[3 points] Explain the method of finding the poisoned bottle from the rats clearly in words using step-by-step instructions.
[2 points] Write the number of rats required and report how many of them can die in the worst case.
[15 points] There is a switch room and a light room. There are 10 switches in the switch room and 10 bulbs in the light room. There is a long corridor between the switch and the bulb room. One cannot see the contents/state in one room being in another room. It is not known which switch corresponds to which bulb. Assume that you are initially in the switch room, all switches are off, and hence all bulbs are off. How do you find the one-to-one correspondence between the switches and the bulbs minimizing the number of trips to the light room?
[10 points] Draw the table using the binary numbers strategy to explain your method/approach.
[3 points] Explain your method clearly in English using step-by-step instructions.
[2 points] Write the number of trips to the light room. A trip is defined as the movement from the switch room to the light room.
[15 points] We want to measure any integer weight in the range [1, 15] using a two-sided weighing balance using a minimum number of weights. Explain how can we solve the problem assuming:
(a) We can place weights only on one side, and
[5 points] Write the table.
[2 points] Explain the method and write the minimum number of weights.
(b) We can place weights on either side of the weighing balance.
[5 points] Write the table.
[3 points] Explain the method and write the minimum number of weights.
[10 points] Explain in detail:
(i) [5 points] What is your favorite puzzle (not covered in the class) and why? and
(ii) [5 points] What puzzle-solving techniques did you learn in this course?