- Backtracking Maze solving
- Recursive List Merge

The mazes presented in class can be generalized as a graph, as
implemented in graph.h and
graph.cpp, in which the nodes are valid positions
in the maze and edges are steps that can be taken. You are to write a
**recursive** function `findPath`

, as declared
in assign4_a.h that uses a backtracking algorithm
to find a path through the graph from `src`

to
`dest`

. If a path is found, then it should return
`true`

and `route`

should contain the sequence of
nodes visited (excluding `src`

) in travelling from `src`

to `dest`

.
Each pair that is adjacent in the route must be adjacent in `g`

.
If no such path exists, then it must return `false`

Submit your function definition only in `assign4_a.cpp`

that
`#include`

s `assign4_a.h`

.

A list, A, is said to be *sorted* in non-decreasing order (a.k.a.,
increasing) if in all cases A_{i} <= A_{i+1}. Given
two such sorted lists, it is easy to produce a new sorted list by a merge
sort algorithm -- recursively choosing the lesser of the two heads.
In this assignment you are to implement `merge`

as declared in assign4_list.h, using one
or more **recursive** private member functions (that you are to declare
and implement), so that
the result of invoking `l.merge(l1)`

, where `l`

and
`l1`

are both sorted lists, is that `l`

is changed to
include all members of both lists in non-decreasing order.

Submit a modified version of `assign4_list.h`

containing your
implementations. Please add your private member function implementation(s)
at the **end** of
`assign4_list.h`

, immediately before the `#endif`

.
The file already contains an empty implementation for `merge`

,
which you are to modify.

Be sure to include appropriate comments, including file and function header blocks (see Assignment Policies), and to use good style as outlined in Programming With Style. Submit your source code using Web Submit.

Back to 4892 homepage

*Last modified:
Fri 2003.06.20 at 09:34 NDT
by * Dennis Peters