I. Introduction

It is an incredibly important day for you at UW CSE. Hannah, Brian, and Albert have pooled together their meager teaching wages to purchase donuts for their 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 have rearranged all the furniture and cubicles during the night, 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:

• Be introduced to the PriorityQueueADT.
• Implement your own BinaryHeap data structure, and compare the tradeoffs between various PriorityQueueADT implementations.
• Explore the similarities and differences between recursive and iterative algorithms.
• See an application of the Stack, Queue, and PriorityQueue ADT's in maze search.
• Gain experience analyzing an existing codebase's architecture.
• Develop code according to a pre-determined specification.

III. Assignment and Algorithm Overview

For the entire assignment, you are required to write several new maze-solving MazeRunner classes. There should be one MazeRunner class for each of the following algorithms:

1. Iterative Depth-First Search (DFS) -- please implement this search with a Stack
   More information on recursive DFS can be found here.
2. Breadth-First Search (BFS) -- please implement this search with a Queue
   More information on BFS can be found here.
3. Best-First Search (not abbreviated for obvious reasons) -- please implement this search with a BinaryHeap
   More information on Best-First Search can be found here.

We are requiring that your data structures be able to handle input of any size. That is, your data structures should be dynamically allocated, and be able to grow (and perhaps shrink) as necessary. You do not need to do this project in both C++ and Java; pick the language you are most familiar with.

Part 1 of this assignment asks you to implement and test the data structures that support the above algorithms. That is, you should only be writing the Stack, Queue, and BinaryHeap data structures. You should also take this opportunity to get an understanding of how these three graph search algorithms work for a general graph.

Part 2 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 2.

IV. Teams

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 below; and third, understand (at least) at a high level how your team member's code is structured and how it works.

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. If you choose to work with a partner, you will be required to implement one additional Above and Beyond project. This additional project is part of your required work, and will not count towards extra credit. If you are working alone, the "Above and Beyond" requirement is waived.

V. Provided Code

For the second part of this project, we will be providing code to read, parse, and build a Maze class which your algorithm will operate on, as well as sample a RandomMazeRunner. Your own MazeRunner classes should inherit from the abstract MazeRunner class. Your modifications to supplied code should be minimal, and well-justified in your README.

The provided code is located in /projects/cse/courses/cse326/02su/project2. You copy these files when logged in from any instructional machine. Further documentation on the Maze files architecture may be found here, or in the course directory.

VI. Maze Input and Output

The SquareCellMazeFactory class reads a maze file from a file specified on the command prompt. The file format is a picture of the maze. There is also some header information at the front that gives the dimensions of the maze (height, then width). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the entrance, and 'X' for the exit. For example, the following is a legal maze:

      7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        X|
      +-+-+-+-+-+-+-+

There are some sample input files in the course directory that you can use to test your program. You should also consider writing (and sharing with your classmates!) other test mazes to run your MazeRunner on.

After solving a maze, a MazeRunner should output a solution path calculated by the search. The path should be given on a single line and should consist of the printed locations (using the built-in print method) separated by spaces. On the next line should be the length of the solution path, and on the following line should be the number of nodes expanded in the search (remember that a search might involve visiting many nodes not on the solution path. You will have to find a means of extracting the path from the collection of nodes you visited). The solution should be preceeded by a line giving the name of the search algorithm used. For example, the output for the above maze might be:

     A* Search
     (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (4,5)
     (4,6) 
     10
     15

The solution displayed above to the following solution path:

      +-+-+-+-+-+-+-+
      |*|   | | |   |
      +.+-+ + + +-+ +
      |.  |   |     |
      +.+ + +-+ +-+ +
      |.|   |     | |
      +.+-+-+ +-+-+ +
      |.....  |     |
      +-+ +.+-+-+ +-+
      |   |........X|
      +-+-+-+-+-+-+-+

VII. Maze Visualization

      % mazerunner -v mazefile

Try using the visualizer with the random solver so you can see how it works. In your own MazeRunner, you will need to call setCellState() in MazeCell to make the colors change. This function has nothing to do with the validity of your algorithm! It is meant expressly to signal changes in your maze state so things like the visulaizer know when to update themselves.

VI. Detailed Requirements

You are expected to turn in all your code (use the turnin utility to submit your project. This project is called "project2" in the turnin system). You will also need to include a README which contains the following information:

• The names of your team members and your team's name
• If you worked in a team, a breakdown of the work.
• (Answer this question before you begin) How long do you think this project would take you to finish?
• How much time did you actually spend on this project?
• Acknowledgement of any assistance you received from anyone but your team members, the 326 staff, or the Weiss book.
• An explanation of how to compile your program.
• A brief description of how your project goes "above and beyond" the basic requirements.

Also, please answer the following questions (justify your answers, of course; 3-4 sentences each should be fine):

1. Give a high-level summary of how you implemented the recursive DFS algorithm iteratively. What differences did you note between these two algorithm design techniques? Which would you use for DFS? Other algorithms?
2. Why is it more important for DFS than BFS to check whether a cell has been visited yet?
3. If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster, BFS or DFS (any reasonable answer -- as long as it is justified -- will be accepted)?
4. In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
5. Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
6. Which search algorithms (if any) are guaranteed to find the shortest path to the exit? Which ones aren't?
7. An alternative to using iterators would be to search for MazeCell by coordinate. Does the simplification of your algorithm justify the added complexity of iterators in the provided codebase?
8. For this project, nested/inner classes were used to group together logically-related classes. Was this useful for understanding the program's architecture, or unnecessary code complication? Justify your answer.
9. The codebase currently supports only mazes with square-shaped cells. Given the functionality of the current codebase, is the added complication of abstract Maze, MazeCell, and MazeRunner classes worthwhile?
10. Were there any features of the language you used (Java or C++) that you found particularly useful or frustrating? What language do you think is most suited for this project (does not have to be Java or C++)?
11. What's Brian's favourite junk food? Hannah's? Albert's?
12. What did you enjoy about this assignment? What did you hate? Could we have done anything better?

VII. Grading Breakdown

Each part of the assignment will be worth (approximately) the following. Please budget your time appropriately.

40%	Program correctness (including boundary cases) and error-free compilation
30%	Architecture/design of program. Style, commenting, layout. Other forms of program documentation.
30%	README and answers to writeup questions

VIII. Going Above and Beyond (for credit)

The following suggestions are meant for you to try if you finish the requirements early. They will be worth a nominal amount of extra credit.

• Write an additional reference- or pointer-based heap implementation (either a LeftistHeap or a SkewHeap). In your README, write a paragraph on the tradeoffs between a pointer- or reference-based heap. Some possible topics to cover include runtime, coding complexity, memory usage, etc.
• Using the Manhattan distance has several problems, including the fact that the MazeRunner is sometimes fooled into going down "dead ends" in the maze. What other heuristics might be used in your MazeRunner? When might your heuristics perform better than the Manhattan distance, and when might they perform worse (you may want to consider factors such as space usage and time to calculate the heuristic)? Then, run your Best-First MazeRunner with its new heuristic on several mazes and report which heuristic performed better, and in what type of maze it did better in.
• There is a version of Best-First Search called "A*" (pronounced "A-Star"). A* has some theoretically and practically interesting qualities. Contact Brian or Hannah to get a reference to A* Search, and write an A* MazeRunner. Comment on the advantages and disadvantages of this algorithm.
• We saw that, in general, a truly random algorithm for maze search (ie, the RandomMazeRunner) performed poorly. However, algorithm research in recent years has focused on the well-applied use of randomization, with some dramatic results. Design and implement a new randomized maze runner (or modify one of your existing maze runners), and answer the following questions: (1) in what ways do you think your randomized algorithm is "better" than the analogous deterministic algorithm? Worse? (2) present a maze in which the randomized algorithm performs (in general) better than a deterministic algorithm. (3) If the deterministic algorithm does as good as, or better than, the randomized algorithm in some mazes, present an example. If such a maze does not exist, explain why.
• Do something cool with the visualizer. Please let Brian and Hannah know what you're going to do before you start.
• Go all out: We're letting you express your creative side here. Can your MazeRunner handle mazes with multiple exits? What about rendering your maze in 3-D? If you do anything about the basic design specifications, check with Brian and Hannah, and document what you did. Of course, your code should still meet the basic requirements.