Project 2 - The search for
Fri. Jan. 18
Wed. Jan. 23
Notify instructor by email by 10 pm
Phase A Due
Wed. Jan. 30
by 11:00 pm using this
online dropbox, (not that we recommend waiting until the
last minute...) (no paper turnin)
Phase B Due
Wed, Feb. 13
Electronic turnin by 11:00 pm, Paper turnin beginning of Quiz Section
on Feb. 14
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 10 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?
In this assignment, you will:
- Work on the PriorityQueueADT, and implement
your own data structures.
- Gain experience with systematic testing.
- 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
- Train your computer to
do your most important tasks for you -- like finding donuts!
For the complete assignment, you are required to write several new
classes. There should be one MazeRunner
class for each of the following algorithms (subject to change in Phase B
- 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 =
More information on Best-First Search can be found here.
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 next week). In particular, you are required to design and implement
a collection of JUnit tests that verify that your code works properly.
Your task for Phase A is to:
- Implement a stack,
queue, a binary heap, and a three-heap according to the interfaces
implementations should automatically grow (if interested you may also
make them shrink - this is optional) as necessary.
Note: Growing an array implementation one element at a time is
not likely to be the most time efficient solution, if you use arrays,
try to come up with a more time-efficient solution.
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
(MazeStack.java), your queue implementation (MazeQueue.java), your binary
heap implementation (BinaryHeap.java), and your three-heap
The heaps should be implemented with arrays; you are free to implement
the stacks and queues as you wish, although arrays are as simple as anything.
(Although our usual rule prohibiting use of the Java class
libraries to do the actual work remains).
- Implement unit tests for your stack, queue, and priority queue heaps using
JUnit, and verify that your code passes the tests. Your tests will be evaluated
how comprehensive your test coverage is, and whether tests are small and
modular. But note that good test coverage is not synonymous
with having lots of tests
the same. (Hint: You may be able to reuse a single suite of tests for both
implementations of the priority queue if you think about how to take advantage
of interface types and maybe inheritance in the test code. Massive cut-'n-paste
is not as good an alternative.)
- You should also take
this opportunity to get an understanding of how the three graph search
algorithms described here work for a general
You should turn in a README file with an informal description
of your test plan. Summarize the tests you implemented and explain how they
provide comprehensive test coverage for your classes. This should not just
be a dump of the test names and comments from the code file - we can read
that. What we want is to get an idea of the thinking behind what you did.
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
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 AND UW email id 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”.
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 one of
the TA's for instructions. This is NOT necessary, just optional if it is your
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
For this first Phase, we are providing the interfaces for a Stack, a Queue, and a PriorityQueue. You must write an
implementation of the Stack
and Queue interface as
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, although making the original code easy to generalize
may save you time in phase B (hint, hint).).
Java code: Right-click on the links below to download the starter code.
-- interface for a PriorityQueue ADT. Both
BinaryHeap.java and ThreeHeap.java should implement this..
-- interface for a Stack ADT.
-- interface for a Queue ADT.
Your priority queue implementations must accept Comparable objects. Many classes
Integer implement the
In Phase B you will need to modify/create some more classes that
Comparable interface (in other words, writing your
compareTo method). Then you will be able to have priority queues
containing those objects. Unlike your stacks implementations for Project1
that were hardcoded to use doubles, your implementations of the
PriorityQueue interface need to use generics. Your implementations
ThreeHeaps in particular need to
comparing elements so the code will work on any
More information about Java's
Comparable interface may be found at Sun's
In addition, you might find this description from Fall 2006 cse143 to be useful.
Both generics and the
Comparable interface are discussed in section
the Weiss text, and there is a good tutorial on
Sun's web site. The tutorial is based on this
paper by Gilad Bracha, one of the
Java language designers.
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.
A and B will be graded together when your entire assignment is turned in with
Phase B. However, 15% of your grade will be based upon the
"in-progress" checkin for Phase A. Although 15% is a relatively 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.
We will be testing the code that you submit for the in-progress checkin - so we will expect that you have done the same!
Only one person from each team should submit. The same person should
submit both Phases A and B. You should submit all of the Java code
you wrote: MazeStack.java, MazeQueue.java, BinaryHeap.java, and