G12FCO -- Formal Computation

Problem Class 3(a) -- Backtracking

A maze is a network of `roads' joining `villages' in which one village is distinguished as the START and another as the FINISH. The task is to find a route from START to FINISH. Write pseudo-code for an algorithm to implement this.

Assume that you can `paint' selected roads and villages whatever colour you like, and that you can loop over all villages or over the roads out of a particular village -- exactly how this is to be done in C or QBasic or whatever will depend on details of how the network is represented within the computer. You can assume that it will be enough to paint the route a particular colour [`When this terminates, you get from START to FINISH by following the yellow brick road']. There may not be any such route, or there may be lots of valid routes.

Brownie points: Estimate the efficiency of your algorithm. [A maze constructor and solver is one of the standard screensavers on some of the PCs -- if you watch very quickly you can see how it's done.]

More brownie points: Show that the associated decision problem [`Does this network possess a route ...'] is in NP.

Problem Class 3(b) -- Feasibility

Our description of polynomial-time algorithms as feasible and others as infeasible is plainly not to be taken to extremes. Extend the previous tables with lines for the functions N^10, 1.1^N and N^(log N). Estimate the time, and the value of N, at which the first function becomes more feasible than the second and than the third.

top of page

G12FCO home page. border=0

Previous problem class. border=0

Next problem class. border=0

Lecture 9.