Computer Science 789 Online Algorithms

Hint 3 for the Dungeon Searching Problem

Define G(t) to be the treasure in the first t rooms of the greedy path.

Define A(t) to be the treasure in the first t rooms of the other path.

Let F(t) equal half G(t) minus A(t). Use a potential argument to prove that F(n) is nonnegative. Then, we are done. (Why?)

Back to Course Page

Back to Assignment Page

Back to Assignment 1