Due in class September 14, 1999.
Prove that, if n is a positive integer, the number of recursive calls needed to evaluate log2(n) is O(log n).
I will give hints. Each hint is stronger than the last, so start with no hints. If you feel you need a hint, start with the first hint. If you feel you need another hint, read the second hint, and so forth.
Each room contains a treasure, consisting of either zero, one, or two gold pieces. An adventurer moves through the dungeon and collects all treasure in the rooms he visits. His goal is to maximize the treasure.
Each path through the dungeon has a value, defined as the treasure contained in all the rooms in that path. We say a path is optimal if its value is maximum, over all paths.
The greedy algorithm is as follows. If you are in the last layer, just exit. Otherwise, if you are in a small room, you have no choice, so just go to the large room of the next layer, If you are in a large room, peek into the two rooms of the next layer. Enter the room with the larger treasure, and if they are equal, enter the large room. We call the resulting path the greedy path.
Your problem is to prove that the value of the greedy path is at least half the value of the optimal path, for any dungeon.
Specifically, we proved, in class September 9, that if a game graph has a potential Red can win. I want you to prove the converse.
There is a problem with this assignment in formulating the question. In order to give a proof, you must first have a mathematical formulation of the statement, "Red can win."

Back to Assignment Page