I. Introduction

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:

• Be introduced to the PriorityQueueADT, and implement your own D-Heap data structure.
• 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, and modifying existing code.

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:

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 ThreeHeap(e.g. a d-Heap where d = 3)
   More information on Best-First Search can be found here.

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:

1. Modify all three of these data structures to be able to grow (and optionally shrink) as necessary. (you may reuse any code you wrote for homework #1 for this purpose).
2. Convert the given BinaryHeap data structure into a ThreeHeap. You should find your work on homework #2 useful for this. To accomplish this, you must write and use appropriate parent(i), leftChild(i), middleChild(i), and rightChild(i) methods.
3. You should also take this opportunity to get an understanding of how these three graph search algorithms work for a general graph.

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.

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 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)

• StackAr.java -- array implementation of a stack
• QueueAr.java -- array implementation of a queue
• BinaryHeap.java -- array implementation of a binary heap
• PriorityQueue.java -- interface for BinaryHeap.java, and for the ThreeHeap.java code that you must write.
• Plus a bunch of helper classes like Overflow.java. Get these from the bundle above.

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 turnin

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: