Important Deadlines

Updates

Outline

• I. Introduction
• II. Learning Objectives
• III. Assignment and Algorithm Overview
• IIIa. Phase A: Stacks, Queues, and PQueues
• Description
• Code requirements
• README Questions (look at this before starting)
• IIIb. Phase B (brief description): Running the maze (like a mouse)
• IV. Logistics: Teams, Shared Group Directories and Version Control
• V. Phase A Provided Code
• V. Phase A Turning

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 Allen Center space czars just happened to have decided to rearrange all the furniture and cubicles during the night (as part of their experimentation with different settings in the new building), turning the entire building into a complex and mystifying maze. Since you haven't had your morning coffee yet, you decide to sit back and let your computer solve the maze and find the donuts for you!

In this assignment, you will:

• Work on 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.
• Understand Java "Memory Leaks"
• See and modify Javadoc comments. Look at this link for more info on Javadocs.

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

In Phase A of this assignment, we are giving you substantial starter code for the generic stack, queue, and binary heap data structures (moderately modified from the Weiss book).

Code Requirements

Your task for Phase 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 Project #1 for this purpose. Be sure to fix the comments! You are graded on style and incorrect/misleading comments is the worst kind of bad style.
2. Fix the memory leaks!!! There's one known memory leak in each of the data structure implementations. Find them and fix them.
3. Convert the given BinaryHeap data structure into a ThreeHeap. You should find your work on Written Homework #1 useful for this. You will need to write and use appropriate parent(i), leftChild(i), middleChild(i), and rightChild(i) methods.
4. You should also take this opportunity to get an understanding of how these three graph search algorithms work for a general graph.

1. How much time do you expect to spend on this project?
2. How much time did you actually spend on this project?
3. What is a "memory leak" in Java? When does it happen?
4. Do you like Jelly Donuts? With Raspberry filling?
5. What is the difference between a Runtime and a Checked Exception? When would you use either one? Briefly justify your usage.
6. What do you think of Javadoc? Did you try running Javadoc on your code (javadoc *.java)?

Phase B will involve implementing the above tree traversal algorithms (they will be implemented as MazeRunner classes), understanding operations on a maze as a graph, and analyzing and extending the maze code which we will provide.

IV. Logistics: Teams, Shared Group Directories and Version Control

You will work in a team of 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 so that you both understand your answers to the questions answered in the README (for Phase B); and third, understand (at least) at a high level how your team member's code is structured and how it works.

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. You will be assigned a unix group (such as cse326a, cse326b, ...) for the team, which you can use to share files.

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.

Shared Group Directories: We will create a shared working directory for each group:

E.g.    /projects/instr/03au/cse326/project2/team-x     for group x.

This directory will have read/write permission only for the members of group x (and the course staff), who will all be made members of the unix group cse326x. How you structure your code, backups, test suites, etc. within this directory is totally up to you and your partner. Three things to note: (1) you can share files by simply making them unix group readable/writable - click here for a quick introduction to unix groups from a UWACM Tutorial; (2) there is much more space in this projects partition than in your unix home directories; (3) when you finish the project, save your code in your personal home directory for reference because the same group id might be assigned to a different group for later projects.

Recommended - CVS for version control: Since this is a shared project, it is worth learning a concurrent revision control system. CVS is a simple revision control system that you can use to facilitate merging and backing up of the code you write. Using CVS will help ensure that you and your partner do not accidentally delete each others changes. It is even useful for personal projects where you want to be able to keep a revision history (say, in case you find that you want to revert to a version of your code you wrote 5 days ago). CVS is a good tool and it is highly recommended that you learn it so that you can use it in this and future CSE courses. There is a UWACM tutorial here that gives the basics of how to use CVS as well some info on other Unix development tools. Note: There are versions of CVS for windows, but that isn't covered in the tutorial.

V. Phase A 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 broken into two Phases. For Phase A, we suggest improving and testing your basic "helper" data structures (i.e. Stack, Queue, BinaryHeap) without worrying about the Maze-related code.

For this first Phase, 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: The base code is located in the directory /projects/cse/courses/cse326/03au/projects/project2/code-phaseA/. You can copy the java files from this directory when logged on to the instructional unix server attu. It is also linked to on this website. Here is a brief description of the code:

• PriorityQueue.java -- interface that corresponds to a PriorityQueueADT. It is for BinaryHeap.java, and for the ThreeHeap.java code that you must write.
• BinaryHeap.java -- array-style binary heap implementation of a PriorityQueue
• Stack.java -- interface that corresponds to a StackADT.
• StackArray.java -- array implementation of a Stack
• Queue.java -- interface that corresponds to a QueueADT.
• QueueArray.java -- array implementation of a Queue
• A bunch of helper classes like OverflowException.java, UnderflowException.java, EmptyHeapException.java, and IntComparator.java.

The priority queue implementations make use of Comparators (e.g. IntComparator.java) to decide how to order the relative priorities of objects, and Phase B will involve writing at least one of your own. More information about Java comparators may be found at Sun's website.

For Phase B of this project, we will be providing additional code which will read, parse, and build a Maze class object from a text file. We will also give a simple MazeRunner class from which you can inherit your own MazeRunners.

Only one person from each team should submit. The same person should submit both Phases A and B. Follow the normal turnin procedures, using the name "project2A" for this first turn-in. You should submit:

1. All of the Java code (use *.java), including your new ThreeHeap.java
2. The README file

For the hardcopy, please place the README file in front, and include any code that you have written or modified. You do not have to hand in printouts of files that we provided that you did not modify (eg. PriorityQueue.java). Also, please be sure to follow the printing instructions as this ensures a consistent style for the TAs to grade.