Challenge Problems in Algorithms and Data Structures

Revised November 28, 2022.

Turn in your solution to one of these problem directly to Dr. Larmore (not the teaching assistant) by Wednesday April 26.
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.

The 13-coin problem is to use a balance scale to find a counterfeit coin among 13 coins, and determine whether it is too heavey or too light. The Wikipedia page Wikipedia page on Balance Puzzles states that there is no algorithm for this problem, but gives no proof. Prove it.
Given a linked list of integers, mergesort in O(n logn) time without creating any additional nodes. That is, never use the "new" constructor. The resulting sorted list uses exactly the nodes given in the input list, just rearranged.
You must write this as a C++ program, which I will test with my own data.
I falsely stated in class that this can be done using only constant workspace, where workspace means memory space needed not counting the space holding the linked list. My solution uses O(log n) workspace.
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.
You must write this as a C++ program, which I will test with my own data.
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?
You must write this as a C++ program, which I will test with my own data. Your program must be submitted as a text file (not handwritten) so that I can run it. Explanations may be handwritten.