CSE326
Summer 2004
Assignment 5
7/15/2004

Data Structures: Alive!

Files

Due in two parts: Electronic parts on Wednesday evening, July 21 and 28, paperwork in class the following days.

Please work with the same parter as for the previous project.  Turn in only one copy, and put both partner's name on the paper.  Both will receive the same grade under normal circumstance.  (PS We will be shuffling partners after this assignment).  There are no textbook problems this week, but for your own sake and to keep up with the material, you might consider looking through some of the problems at the end of the chapters.

Remenber this? "Read carefully through 4.39-4.40.  Think about each step and how you would program it.  Will be the basis of a future project..."

The future is now!  Write Java code along the lines suggested by those problems.  Specifically:

Part I:
The goal of the first week is to get a binary tree structure that you can display and perform basic operations on.

Create a class Node.java to implement the interface INode.java, and DrawableNode.java which implements IDrawableNode.   Also, write test code which creates trees and displays.  How this fits together will become gradually clearer after you look at the interfaces.  In particular, the drawing code itself will be in the draw paint method of IDrawableNode.  If you are new to Java graphics, feel free to get as much help as you need from Martin and Deepak or from your classmates.  You can focus on using the basic drawing facilities provided in classes such as Graphics, Shape classes such as Line, Rectangle, etc.  You won't have to worry about events or user interface stuff.  We will give you a class which will provide a context for calling your drawing method (7/15: not yet in the Files directory 7/19: now in the Files directory).

During the first week, you should also be thinking ahead to the work of Part II.

Part II:
The goal this week is to use your tree-drawing  code as the basis for an interesting "animation".  An animation is a sequence of images intended to illustrate some algorithm or process.  Here are some examples (you can use one, or even better, think of something of real interest to you that probably no one else will pick!  Maybe we'll have a prize for the best "concept".  Let your imagination rule.):

• showing a structure being built, step by step, such as: inserting a list of elements into an initially empty tree.
• showing the steps which make up a single operation, such as rebalancing an AVL tree, traversing a structure, or re-heaping a heap.
• show how one structure is transformed into another (such as a general non-binary tree being converted to a child-sibling tree).

In doing this, you might want or need to show more than just circles for nodes and straight lines for edges.  You can make any data structure you wish the focus on the animation, though it might be best to choose one we have studied this quarter, or which is similar to one of those.  Note that the INode interface is general enough to allow structures other than binary trees, such as lists, multiway trees, and graphs.  And of course your concrete subsclasses can build on INode in many possible ways.

To control your animation, you may need some data structure (who knows what? a list of actions or of parts of trees or user inputs or ...? etc.) 

Finally, there should be some way for a user to interact with the animation, to supply data before or during the display, or make choices, specify parameters, etc.  This does not have to be done with an elaborate GUI.  Anything at all is fine, even if it's a bit clunky.

The exact code you turn in will vary from team to team.  The way the projects will operate will vary, too.   There will be an electronic code turn-in as usual, as well as written reports.  In addition, expect there to be a live demo session, at which the team members will demonstrate their project to Martin and/or Deepak.  These sessions will be scheduled after the final turn-in.

First week Deliverables:

• Code files as described above.
• A short report (one page or less) describing how well what was turned in meets the requirements, and listing any bugs or special considerations which need to be taken in account during grading.
• A proposal for your animation (one page).  Give it a title or theme.  Describe what the user will see.  State what kinds of interactions or user control will be available.  Describe what data structures are plausible (for control, not the trees themselves). You might include drawings (hand-made).  This is a draft, and you may change parts of it as you implement later.

Second Week Deliverables:

• Final code files.
• Project Report.  This can basically be your proposal from the first week, revised and finalized. There should be instructions so that someone would know how to run your program without you being present.  Add a section describing how well the project works, listing any bugs you know of.
• Individual Report: Each individual should turn in a confidential report, describing the nature and extent of this person's contributions to the project.  This is in reference to the full two weeks, not just the final part.
  

Have fun!