Computer Science 789 Online Algorithms

Fall 1999 Assignment 1

Due in class September 14, 1999.

  1. Consider the Pascal function log2 that computes the floor of the base 2 logarithm of any positive integer.

    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.

  2. Recall the Dungeon Searching problem given in class and in Handout 1. At each layer of the dungeon, there are two rooms, a small room and a large room. The entrance hall leads to either the small room or the large room of layer 1. The small room of each subsequent layer can be entered only from the large room of the previous layer, while a large room can be accessed from either room of the previous layer.

    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.

  3. Prove the other half of the graph potential lemma in Handout 3.

    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 Course Page

Back to Assignment Page