CSE 373, Autumn 2004: Assignment 4
Objectives
There are two objectives to this assignment:
(1) to help you understand priority queues and issues surrounding
their implementation; and
(2) to prepare you for some of the logistical
challenges of doing your term projects. These challenges include
(A) working in a partnership (finding a partner, communicating
effectively with your partner, dividing up responsibility,
scheduling milestones and meetings, solving problems),
(B) coming up with your own ideas and evaluating them as part
of a specification and design process, and
(C) gaining familiarity
with a peer evaluation process.
When and How
Turn this assignment electronically by 5:00 PM on Monday, November 8.
This assignment must be done in a team of two unless you have
special permission for a different arrangement.
Turn in your files at the Assignment 4
turn-in page.
You'll have an opportunity to demonstrate your applet to classmates
on either November 8 or November 10. You'll also evaluate the
applets of classmates on your demo day.
Your Task
Using the Visual Applet Framework,
create a demonstration of the Binary Heap data structure,
showing both array and tree-style displays of the structure.
Your team should be sure to implement the "basic requirements" in your applet.
Then your team should select one of the "extention features" and
implement that. Finally,
Your team should then come up with a new feature and implement that.
Here are some guidelines for each of these three requirements.
Basic Requirements
- Display the array representation of the binary heap at the top of the display area.
- Display the binary tree representation of the binary heap just below the display area, with the root at the top and the leaves at the bottom. Each node will have its key value ("priority value") displayed inside.
- Implement the commands FINDMIN, DELETEMIN, and INSERT.
In your implementations of DELETEMIN and INSERT, each time the
binary heap is changed (for example, when a parent and child
swap values) be sure the update-display method is called, so that
each step of the operation can be seen on the screen.
- Implement the STATS command. This should print out into the history window the current number of items in the priority queue, the number of FINDMIN operations performed so far on this priority queue, the number of DELETEMIN operations, and the number of INSERT operations.
Extensions
Choose one of the following features and implement it as part of
your solution to this assignment.
- Implement two new methods for the priority queue: a method FILL_ARRAY
that takes a comma-delimited list of numbers and puts them into
the heap array but does not enforce the heap property, and
the BUILDHEAP method that takes the values in the array and moves
them around (efficiently) to satisfy the heap property.
- Implement two new methods: STRING_MODE and INTEGER_MODE.
The method STRING_MODE makes all the operations work with strings
instead of numbers. Numbers would still be allowed because they
can be treated as strings. In string mode, the display of the
array would change to vertical on the left side of the display, so
that it is easy to show strings of length up to 10 characters.
The tree nodes would also show the strings, so they would get a little
wider in order to accommodate strings of length up to 10. The priority
queue should operate correctly even if the strings are longer than 10
characters, but then you don't need to be concerned if the displays
don't look nice. FINDMIN should return the string that is
lexicographically first.
The INTEGER_MODE simply specifies going back to the regular, numeric mode.
- Add a feature that allows every item in the priority queue to
have not only a numeric key but also a "data" value that is a string.
That means that there will be two parallel arrays instead of just one.
These arrays should both be laid out vertically at the left side of
the screen so that there is enough room to display the strings (up to
length 10, as in the previous option). Each tree node should show
BOTH the numeric key and the string data. The command INSERT should
take two arguments, separated by a comma. The first is the numeric key,
and the second is the string. FINDMIN should print out both the key
and the string into the history window and status line.
- This option has two parts: (a) Add the following measurements to the STATS command:
The number NCIT of comparisons performed during INSERT operations so far,
the number NCDT of comparisons performed during DELETEMIN operations so far,
the number NSIT of swaps performed during INSERT operations so far,
the number NSDT of swaps performed during DELETEMIN operations so far,
the maximum number NCIM of comparisons performed by a single INSERT operation
so far,
the maximum number NCDM of comparisons performed by a single DELETEMIN
operation so far,
the ratio RCIM of NCIM to log base 2 of n, where n is the number of items
in the priority queue at the time of that particular operation, and
the ratio RCDM of NCDM to log base 2 of n.
(b) Also, modify your painting method so that whenever the binary heap changes,
the nodes (normally one or two) that have changed are highlighted.
Thus the bubbling up and percolation down will be obvious, because the
nodes with changing values will be highlighted.
Your own idea
Make up a new feature of your own and add it to your applet.
This feature could be a new command, or an improvement to the
display. It could be the computation of a new statistic by
the STAT command. It could be an ability to handle more
sophisticated kinds of data. However, it should be something original,
not in the list of choices above.
Demonstrations and Peer Evaluations
Each team will participate in demos and peer evaluations.
Your day is either on Monday, Nov. 8 or Wednesday, Nov. 10.
Here is how to determine your day:
Take your last name initial and your partner's last name initial.
These should be capital letters. Find
the ASCII code value
for each. Add the values together getting a sum S.
Take S modulo 2. You will have a number that is either 0 or 1.
If your number is 0, then you will demo on November 8.
If your number is 1, then you will demo on November 10.
If you show up correctly (and on time) on the proper day for your demo,
you will get 2 class participation points.
Each team must have at least 2 peer evaluations completed and
at least one Instructor/TA evaluation.
In addition, each person in the class must complete at least
two peer evaluations of others. The peer evaluations must be
done using the forms provided at your demo session.
(version of 22 Oct. 2004, S. Tanimoto. Updates on peer evaluation
added Nov 5.)