6 points for each problem.
1) Apply quicksort to the following array. Show the state of the array after each swap operation, and mark the current pivot in each step, as well as left and right.
(41,99,36,56,6,6,11,8)
2) Solve the following knapsack problem. Show the complete table.
Maximum capacity of knapsack: 11 pounds
Items (weight, value): i1 = (1,1); i2 = (2,5); i3 = (2,5); i4 = (6,20); i5 = (7,23)
Hint: the problem becomes somewhat easier to do by hand if you write the set of all items used in each table cell (in addition to the total value).
3) Use the sequence alignment algorithm presented in class to align the following strings. Show the complete table.
"TGCCAAGT", "GCTCAAT"
4) The following specifies the Wolf-Sheep-Cabbage game.
A farmer has a wolf, a sheep, and a cabbage. He also has a rowboat that can carry himself and one other item. The farmer is on the right bank of a river together with the boat, the wolf, the sheep, and the cabbage. He wants to move all the items to the other bank. But if the sheep is left alone with the cabbage, it will eat the cabbage. If the wolf is left alone with the sheep, it will eat the sheep. How can the farmer move everything to the left bank without anything being eaten?
Draw a graph that shows all the possible states and moves of this game. Each node is a state, and for each node, specify on which side of the river the boat, the wolf, the sheep, and the cabbage are. Each edge is a move. In each move, the farmer rows to the other bank, either with an empty boat or with a load. Mark all the nodes without outgoing edges as either winning states or losing states.
Assume you want to write a computer program to solve this puzzle. List all the nodes in the graph in depth-first order until you find a winning node. Then list all the nodes in breadth-first order until you find a winning node. Which was faster? Was there a reason why one was faster in this particular problem?