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
#includes assign4_a.h.
A list, A, is said to be sorted in non-decreasing order (a.k.a.,
increasing) if in all cases Ai <= Ai+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.
Last modified: Fri 2003.06.20 at 09:34 NDT by Dennis Peters