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 ith inn is di
miles from A and costs ci 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.
