Computer Science 789 Online Algorithms

Hint 1 for the Dungeon Searching Problem

You only need to prove that the value of the greedy path is at least half the value of an arbitrary path. Do you see why?

If you ask, "how does the fact that the other path is optimal enter into the proof?" the answer is that it doesn't.

Back to Course Page

Back to Assignment Page

Back to Assignment 1