The algorithmic problem solving group conducts research into mathematical method, in particular the problemsolving skills involved in the formulation and solution of algorithmic problems. Our goal is to articulate these skills primarily by way of concrete examples, but also by the development of appropriate mathematical theory.
Written by Joao Ferreira.
 Speaker:
Roland Backhouse
 Date:
20th May 2008, from 2.00pm to 3.30pm
 Location:
C60, School of Computer Science
 Description:

The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly nontrivial. The case in which there are just four people and the capacity of the bridge is two is a wellknown puzzle, widely publicised on the internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present an algorithm that determines the shortest total crossing time; the number of primitive computations executed by the algorithm (i.e. the worstcase time complexity of the algorithm) is proportional to the square of the number of people.
The slides of the talk are now available.
Direct link for the paper, containing all the proofs.