|CSE Home||326 Home||About Us||Search||Contact Info|
Project 2 - The search for a-MAZE-ing donuts!
It is an incredibly serendipitous day for you at the Paul Allen Center. A mysterious bearded 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 (and the always hungry grad students from the night before haven't beat you there). Unfortunately, the Allen Center space czars just happened to have decided to rearrange all the furniture during the night (as part of their experimentation with different settings in the new building), turning the entire building into one complex and mystifying maze. You haven't had your morning coffee yet, and you just don't feel like running around looking for donuts—but you're so hungry! Why not let your computer solve the maze and find the donuts FOR you?
II. Learning Objectives
In this assignment, you will:
For the complete assignment, you are required to write several new maze-solving MazeRunner classes, each with one or more associated data structures. There should be one MazeRunner class for each of the following algorithms:
IIIa. Phase A: DFS and BFS
Your task for Phase A is to implement a stack, a queue, a depth-first search maze runner and a breadth-first search maze runner, according to the interfaces provided. Your data structure implementations should automatically grow (if interested you may also make them shrink—this is optional) as necessary. You should test these implementations to be sure they are correct before proceeding to Phase B. We'll also ask you to design and implement a collection of unit tests to verify that your code works properly.
Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution; if you use arrays, try to come up with a more time-efficient solution. You may reuse any code you wrote for Project #1 for this purpose but be sure that you implement the interfaces provided for this project.
You are free to implement the stacks and queues as you wish, although arrays are as simple as anything. Our usual rule prohibiting use of the Java class libraries to do the actual work remains. You should also take this opportunity to get an understanding of how the three graph search algorithms described here work for a general graph.
You should also implement unit tests for your data structures and verify that your code passes the tests. You should turn in a TESTING.txt file with an informal description of your test plan. Summarize the tests you implemented and explain how they provide comprehensive test coverage for your classes. This should not just be a dump of the test names and comments from the code file—we can read that. What we want is to get an idea of the thinking behind what you did. We recommend use of JUnit, but this is not a requirement. The testing strategy you discuss in TESTING.txt will be evaluated as a part of the project, but the code of your actual unit tests will not.
IIIb. Phase B: Priority Queues and Best-First Search
For Phase B you will write several implementations of the Priority Queue ADT and a best-first search maze runner to use them. Specifically, you will write a binary heap, a three heap, a d-heap, and a pointer-based heap (one of: skew heap, leftist heap, or binomial queue). You will also need to modify MazeRunnerLauncher.java to accept command line arguments appropriate for each type of maze runner or priority queue. Finally, you'll need to answer the questions from the write-up and turn them in in README.txt.
All of this is more work than it sounds, so do not leave it to the last minute.
IV. Detailed Requirements
IVb. Input and Output
There are some sample input files in the starter files mentioned above that you can use to test your program. You are highly encouraged to write (and share with your classmates!) other test mazes to run your MazeRunner on. Send them to us or post them on the message board (preferred).
After solving a maze, your MazeRunner should output the name of the search algorithm used followed by the solution path calculated by the search. The path should be given on a single line and should consist of the printed cells from the start to the exit, separated by single spaces. On the next line should be the length of the solution path, and on the following line should be the number of cells visited in the search, including cells that were not completely explored (i.e., marked "Visit in progress" when the search completes). For example, the output for the above maze might be:
Random search: (0,0) (1,0) (2,0) (3,0) (3,1) (3,2) (4,2) (4,3) (4,4) (4,5) (4,6) Length of path: 10 Number of cells visited: 15
Please note that the start and end cells are both included, but the length of the path is the number of edges traversed ( one less than the number of cells visited). Please do not include extraneous output. For the other search algorithms, use text "Breadth-first search:", "Depth-first search:" and "Best-first search:".
The solution displayed above corresponds to the solution path shown below with dots:
+-+-+-+-+-+-+-+ |*| | | | | + +-+ + + +-+ + |. | | | + + + +-+ +-+ + |.| | | | + +-+-+ +-+-+ + |. . . | | +-+ + +-+-+ +-+ | |. . . . O| +-+-+-+-+-+-+-+
Note that your MazeRunner does not need to output a text-graphical solution such as the one displayed above.
Note also that a search very likely involves visiting many nodes that are not on the final solution path. You will have to explore ways of keeping track of the solution path from the collection of nodes you visited. RandomMazeRunner gives an example of how this might be done. You will need to modify this technique to work for your algorithms.
IVc. README.txt Questions
Your README.txt should contain the following information and answer the following questions:
IVd. Grading Breakdown
The amount of code required for this project is actually very small. A significant part of your grade will be based on your program design and your README.txt.
Look at the course grading policy for a more detailed explanation on grading guidelines.
V. Provided Code
The skeleton code can be downloaded as p2code.zip. Some of the important files are:
For Phase A we provide interfaces for a Stack and a Queue, as we as an example MazeRunner (RandomMazeRunner, which picks the direction to explore in a random fashion.). You must write the implementations of the provided Stack and Queue interfaces as described above. Your own MazeRunner classes should implement the MazeRunner interface.
For Phase B we provide code to read the input maze given as a text file, parse it, and build a Maze class object from it, which your algorithm will operate on. We also provide the interface for the Priority Queue ADT, PriorityQueue.java. You must write several implementations of the PriorityQueue interface–a BinaryHeap, a ThreeHeap, a DHeap, and a pointer-based priority queue of some kind. For the array-based heaps (BinaryHeap, ThreeHeap, etc.) you can start with a copy of your code from one and make changes as necessary, although making the original code easy to generalize making appropriate use of inheritance may save a lot of time (hint, hint).
You are not required to modify any of the provided files besides MazeRunnerLauncher.java.
Further documentation on the Maze code architecture and how to get started can be found here. If you find the large codebase a bit overwhelming, this is good place to start.
VI. Logistics and Extra Information
You are encouraged (although not required) to work with a partner of your own choosing for this project. You may choose how to divide the work between the two of you under three conditions:
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 and provided you notify us in advance of the deadline, all team members will receive the same grade for the project.
Subversion and Group Spaces
If you would like to use a shared group directory, please contact one of the TA's for instructions. This is NOT necessary, just optional if it is your preference.
We can create shared space on attu for each group if you wish to set up a subversion repository; we'll have more details once the project groups are finalized.
Each group can have a Subversion repository available if you wish to use a repository to coordinate modifications to your code base. Subversion is useful for both teams and individuals, as it allows you to store backups of your code in a central server. For teams, each team member may be working on the code concurrently, and Subversion checks for conflicts when the changes are committed. For more information about Subversion, try the Subversion book. That link describes how to use Subversion on the command-line; you can also use TortoiseSVN on Windows (documentation) or the Subclipse plugin for Eclipse (not yet installed on the lab machines, but go here for install instructions for your own machine and here for usage instructions). The repository address is:
where username is your username and groupname is username1-username2 for pairs and username for folks working on their own.
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), we suggest improving and testing your "helper" data structures (i.e. Stack, Queue, BinaryHeap, ThreeHeap, etc.) without worrying about the Maze-related code.
Your tests should be:
Using JUnit is straightforward. Your section should cover the basics of writing test cases; to run a test case from the command line, do:
java junit.textui.TestRunner MyTestCase
where MyTestCase if the name of one of your TestCase classes. Eclipse has a JUnit GUI built in; see here for a howto.
VII. Getting Started
After downloading the provided code, compile everything and try to run the provided random mazeRunner from the launcher class as follows:
% java MazeRunnerLauncher -r sample-inputs/maze2.txt
(Or try one of the other mazes in sample-inputs) The "-r" option invokes the random maze runner. Take a look at RandomMazeRunner.java to get a general idea of how things work. After understanding this file, make a copy (say BFSMazeRunner.java) and try implementing a better algorithm.
To add these files to your SVN repository, you should do an svn add <filename> for each file. To import into Eclipse, you can drag-and-drop the files into your project or go to File->Import...
VIII. Going Above and Beyond
The following suggestions are meant for you to try if you finish the requirements early. Be sure to clearly describe what you did and how to run it in your README.txt. Recall that any extra-credit points you earn for these are kept separate from your assignment score and will be used to adjust your grade at the end of the quarter, as detailed in the course grading policy. Please don't put extra credit code in your main turnin—instead, put modified versions of your files in an archive extracredit.zip.
IX. What to Turn In
Phases A and B will be graded together when your entire assignment is turned in with Phase B. However, 15% of your grade will be based upon the "in-progress" checkin for Phase A. Although 15% is a relatively small fraction, you are highly encouraged to successfully complete all of Phase A by this deadline, as there is much more work to do in Phase B.
Only one person from each team should submit. The same person should submit both Phases A and B. You should submit all of the Java code you wrote.
Phase A Turn-in
For Phase A please include the following files plus any others you find necessary:
Phase B Turn-in
For Phase B, turn in all your code for this assignment (from both Phase A and Phase B). So you'll turn in the following files plus any others you find necessary:
Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to rea]