Challenge Problems in Algorithms and Data Structures

Revised November 22, 2005.

The purpose of these problems is to provide a challenge to the top students, meaning those who master the regular material of the course and would like to learn more.
Do not try to work these problem to improve a poor grade ... if you are doing badly in the course, concentrate on the regular material.

Consider problem 10 on page 61 of Levitin. Prove that 9 is the smallest possible competitiveness. That is, if A is a search algorithm, and if C and K are constants such that C < 9, that must exist an n such that, if the door is at n, A takes more than Cn + K steps to find it.
Let G be a weighted acyclic directed graph, with a designated "start" node, s. You wish to find two paths, each starting at s, such that every node of G is on at least one of the two paths. The cost of a solution is the sum of the weights of the edges of the two paths. Design a dynamic programming algorithm that finds a solution of minimum cost, or determines that there is no solution.
An older version of this problem.
Give a linear time (that is, O(n)-time) algorithm for the Traveler's Problem:
A traveler must walk from A to his home at B, along a road of length m miles. There are n inns on the road. The i^th inn is d_i miles from A and costs c_i to stay at. The traveler can walk at most w miles per day. How can he get home at minimum cost, if he must stay at an inn every night until he gets to B?
Solve this problem on layered graphs.
The simple game Tic-tac-toe can be easily analyzed using a game tree. More generally, every finite deterministic game (such as Tic-tac-toe, Chess, Checkers, Go, and Mill) has an associated game graph, which is usually (incorrectly) called a "game tree." (The reason it's wrong to call it a "tree" is that it usually isn't. The game graphs of Chess and Checkers contain cycles. The game graph of Tic-tac-toe is acyclic, but it is also not a tree.)
Write an algorithm that solves any game tree.