Engr. 4892 Assignment 4

Due: 0900 Friday, June 27, 2003.

  1. Backtracking Maze solving
  2. 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.

  3. Recursive List Merge
  4. 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.

Back to 4892 homepage

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