It is an incredibly important day for you at UW CSE. A mysterious benefactor has appeared during the night and has left behind donuts for the entire CSE 326 class! You've managed to get out of bed at a yawningly-early 10 AM, meaning you have first dibs on all the yummy goodness of fresh-baked donuts if you can get to them in time. Unfortunately, the Sieg space czars just happened to have decided to rearrange all the furniture and cubicles during the night (in preparation for the move to the new building, of course), turning the entire building into a complex and mystifying maze. Since you haven't had your morning coffee yet, you decide to let your computer solve the maze for you.
II. Learning Objectives
For this assignment, you will:
III. Assignment and Algorithm Overview
For the complete assignment, you are required to write several new maze-solving MazeRunner classes. There should be one MazeRunner class for each of the following algorithms:
In Part A of this assignment, we are giving you substantial starter code for the generic array, queue, and binary heap data structures (from the Weiss book). Your task for Part A is to:
Part B will involve implementing the above algorithms (they will be implemented as MazeRunner classes), understanding how a maze is like a graph, and analyzing the maze code which we will provide during part B.
You may work on a team of at most two for this project. You may choose how to divide the work, under three conditions: first, document each team member's effort in the README file; second, work together and both understand your answers to the questions answered in the README (for part B); and third, understand (at least) at a high level how your team member's code is structured and how it works.
If you want to work with a partner, you must find your partner and send a single email to the instructor with the name of both partners by the deadline given at top.
Remember to test your team's code as a whole to make sure that your portions work together properly! Also, be aware that except in extreme cases when you notify us in advance of the deadline, all team members will receive the same grade for the project.
Since you will be working in groups for the rest of your academic and professional careers, we strongly encourage you to work in a team for this project! Feel free to ask for a partner over the cse326@cs discussion list.
V. Provided Code
To facilitate understanding of this rather complex project, and to encourage good modular decomposition and "unit testing" (testing small pieces of code instead of testing the entire program all at once), this project is in broken into two parts. For this first part, we suggest improving and testing your basic "helper" data structures (ie, Stack, Queue, BinaryHeap) without worrying about the Maze-related code.
For this first part, we are providing the interface for a PriorityQueue, and an existing BinaryHeap implementation of this interface. You must use this interface unchanged to construct a second ThreeHeap implementation (we suggest starting with a copy of the BinaryHeap code and making changes as necessary).
Java code: (download the whole bundle here. On UNIX, use "unzip code.java", or run WinZip from a PC)
The priority queue implementations make use of Comparators (e.g. IntComparator.java) to decide how to order the relative priorities of objects, and part B will involve writing at least one of your own. More information about Java comparators may be found at Sun's website.
For part B of this project, we will be providing additional code which will read, parse, and build a Maze class from a text file, as well as a simple MazeRunner class which you can inherit your own MazeRunners from.
VI. Part A turninPart A and B will be graded together when your entire assignment is turned in with part B. However, 10% of your grade will be based upon a "in-progress" checkin for part A. If you submit your code before the deadline given at top, you will receive full credit for this part. However, you are highly encouraged to successfully complete all of part A by this deadline, as there is much more work to do for part B.
Only one person from each team should submit. The same person should submit both parts A and B. Follow the normal turnin procedures, using the name "hw3a" for this first turn-in. You should submit: