CSE326 Summer 2006

CSE Home

326 Home

About Us

Search

Contact Info

Administrative  Home  Message Board  Annoucement Archive  Class List Archive  Anonymous Feedback  Mail Instructor & TAs Lectures  Calendar & Slides  Midterm Study Guide Projects  Project 1  Project 2 Phase A  Project 2 Phase B  Project 2 Phase C  Project 3 Homework  Homework 1  Homework 2  Homework 3  Homework 4  Homework 5  Homework 6  Homework 7  Homework 8 Policies  General Guidelines  Grading Policies  Programming Guidelines  Writeup Guidelines Computing  Unix Basics

Project 2 - The search for a-MAZE-ing donuts! Phase A Important Deadlines Project released Mon, June 26   Partner selection Wed, June 28 Notify instructor by email by 10:00pm using this link. Phase A Due Thurs, July 6 Electronic turnin by 11:00pm, (no paper turnin) Phase B Due Thurs, July 13 Electronic turnin by 11:00pm Phase C Due Fri, July 21 Electronic turnin by 11:00pm Outline I. Introduction II. Learning Objectives III. Assignment and Algorithm Overview IIIa. Phase A: Stacks, Queues, and PQueues Code requirements README Questions (look at this before starting) IIIb. Phase B (brief description): Running the maze IV. Logistics: Teams V. Phase A Provided Code VI. Phase A Turnin I. Introduction 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 7 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: Work on the PriorityQueueADT, and implement your own data structures. 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. Train your computer to do your most important tasks for you -- like finding donuts! III. Assignment and Algorithm Overview For the complete assignment, you are required to write several new maze-solving methods. Iterative Depth-First Search (DFS) -- please implement this search with a Stack More information on DFS can be found here. Breadth-First Search (BFS) -- please implement this search with a Queue More information on BFS can be found here. 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. IIIa. Phase A: Stacks, Queues, and PriorityQueues Description In Phase A of this assignment, you will be writing code that implements a given (new) interface for a stack, queue, and priority queue (2 implementations).  You should test these implementations to be sure they are correct before proceeding to Phase B (posted later this week). Code Requirements Your task for Phase A is to: Implement a stack, queue, a binary heap, and a three-heap according to the interfaces provided.  Your implementations should be able to grow (and optionally shrink) as necessary. 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. Make a separate file for your stack implementation (MyStack.java), your queue implementation (MyQueue.java), your binary heap implementation (BinaryHeap.java), and your three-heap implementation (ThreeHeap.java).  You are free to implement the ADT's with data structures of your choice. You should also take this opportunity to get an understanding of how the three graph search algorithms described here work for a general graph. README.TXT Questions Surprise! There are no readme questions for Phase A. Don’t worry - the README file will return for Phase B. IIIb. Phase B: Solving the Maze (more later) Phase B will involve implementing the above tree traversal algorithms (they will be implemented as methods within a larger class), understanding operations on a maze as a graph, and analyzing and extending the maze code which we will provide. IV. Logistics: Teams 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: 1.      You must document each team member's effort in the README file (record this now so you have the info for the phase B readme file); 2.      Work together so that you both understand your answers to the questions answered in the README (for Phase B); 3.      Understand (at least) at a high level how your team member's code is structured and how it works (code for both Phases A & B). If working 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 the top of this document.  If you are planning on working alone, you should also email the instructor a message stating “I am working alone”.  Please use this link for either message. 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. If you would like to use a shared group directory, please contact Gary for instructions. This is NOT necessary, just optional if it is your preference. 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, ThreeHeap) without worrying about the Maze-related code. For this first Phase, we are providing the interface for a Stack, a Queue, and a PriorityQueue.  You must write an implementation of the Stack and Queue interface as described above.  In addition, you must write two implementations of the PriorityQueue interface – a BinaryHeap and a ThreeHeap.  (For the ThreeHeap we suggest starting with a copy of your BinaryHeap code and making changes as necessary). Java code: 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. Stack.java -- interface that corresponds to a StackADT. Queue.java -- interface that corresponds to a QueueADT. 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 provide code for visualization of the maze and the maze solution. You will add your solving methods to this class. VI. Phase A Turnin Phases A and B will be graded together when your entire assignment is turned in with Phase B. However, 10% of your grade will be based upon the "in-progress" checkin for Phase A. Although 10% is a 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 all Phases. You should submit: All of the Java code you wrote: MyStack.java, MyQueue.java, BinaryHeap.java, and ThreeHeap.java The turn in link will open closer to the due date but can be found here.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to gyngve]