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 Tictactoe can be easily analyzed using a
game tree.
More generally, every finite deterministic game (such as Tictactoe, 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 Tictactoe is acyclic,
but it is also not a tree.)
Write an algorithm that solves any game tree.