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

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 implementing and testing your basic "helper" data structures (ie, Stack, Queue, BinaryHeap) without worrying about the Maze-related code. You will not be required to submit the code that you write for part 1, but you are encouraged to start working on part 1 as soon as possible. You are also encouraged to reuse whatever code/programs you have already written, although use of Weiss is discouraged.

For this first part, we are providing the interface for a PriorityQueueADT. You must use this interface unchanged (we suggest the use of inheritance. Thus, the concrete BinaryHeap data structure -- which is an implementation of the abstract PriorityQueueADT interface -- should be descended from the PriorityQueue class). We will not be providing starter code for your Stack and Queue classes.

• For C++ students:
  (void* version) PriorityQueue.hh and Comparator.hh
  (templated version) PriorityQueue.hh
• For Java students:
  PriorityQueue.java

(Information about Java comparators may be found at Sun's website. Information about C++ function pointers may be found here, and C/C++ void pointers can be found here)

For part 2 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.