Assignment 9

CS 290 Fall 2008

Assignment 9 –Trees and Recursion and some complexity experiments!

100 assignment points

Assigned: 11/20/2008

Due: 12/04/2008 at the start of class

Pre-Lab (Do Before Lab): Bring materials – a USB for a take home copy. Read and understand the assignment.

Assignment:

Not a great cover story. We are creating a binary tree of voters, and we’re going to compare the situation to using sets. Imagine that we have large numbers of voters and it matters how long it takes to confirm if they are legitimate. We’re testing out some capabilities related to that task. Part of the project has been written and is available in a zip file on Blackboard. Javadocs should be included in the zip as well. There are a lot of classes included, but only 3 should need modification.

You will write:

· methods in the GUI class to handle (The headers remain in the file):

o GUI event handler to handle getting the deepest level of the tree when the Deepest button is clicked.

o GUI event handler to handle getting the average depth of the tree when the Ave Depth button is clicked.

o Major parts of the GUI event handler to handle comparing different data structure approaches when the Compare button is clicked. The missing part is responsible for looping through (copies of) the queue of Voters to test (correct and 10% incorrect voters), and trying to find whether they are in the tree and voterSet instance variables – timing the time it takes (one line of code related to timing is left in as an example), and presenting statistics related to the task. (see screen shot for sample outputs)

o GUI event handler to handle getting adding a user-specified voter to the tree when the Add button is clicked.

· Methods in the LinkedBinaryTree (with generic) class to handle:

o deepestLevel (or getDeepestLevel) – returns, for a linked binary tree, the deepest level of the tree. E.g. a tree with just a root would have a deepest level of zero, each level below that, add one. Call recursive BinaryTreeNode method to do most of the work. Do not change, destroy, empty or damage the invoking tree.

o averageLevel (or getAverageLevel) – returns the average level of nodes in the tree Call recursive BinaryTreeNode method to do most of the work. Do not change, destroy, empty or damage the invoking tree.

· Methods in the BinaryTreeNode (with generic) class to handle:

o getDeepestLevel – returns (int) the deepest level of children (and other descendents) of the invoking node.

E.g. The subtree headed by node D below has a deepest level of 3.

E F

G H I

o getSumofLevels – returns (int) the sum of levels of invoking node and all children (and other descendents) of the invoking node. E.g. the subtree headed by D above has a sum of levels of: 11 (D=0, E=1, F=1, G=2, H=2, I=2, J=3). Useful for figuring average depth of the tree (hint, hint)

Also, for this assignment, there are questions to answer. See below.

User Interface:

· Sample screen shots are provided below.

· Display output to the text area on the GUI.

· The GUI design can be changed, but keep the same buttons, inputs and outputs. I’m afraid that NetBeans fought me tooth and nail to prevent me from making the window narrower, and I lost.

Miscellaneous Details:

· The Start From Scratch and Add capabilities can be of value for testing methods before trying them on large data. They are set up expecting the user to type the voter id, name, and password all in one text field separated by commas.

· System.currentTimeMillis() gets the number of milliseconds currently elapsed since a specific given time in the distant past before you were born. The result can be assigned into a long (long integer) for later use (e.g. a starting time can be compared to an ending time)

Questions:

a) What is the Big-Oh efficiency for the contains method for a set?

b) What is the Big-Oh efficiency for the find method for a binary tree?

c) What is the Big-Oh efficiency for the find method for a binary search tree?

d) There is data in files with 14 voters, 100 voters, 1000 voters, 10000 voters. At what point does it seem that the efficiency of the different approaches starts to have a real impact? Briefly Explain!

e) If a binary tree is balanced, what would the depth of the tree be relative to the number of elements?

f) Does the tree size in the experiments using various data tend to suggest that the trees tend to be balanced? Briefly Explain!

g) The order of the voter ids (how the tree is organized) in the main data files is pretty much random. Is this good or bad? Briefly explain!

h) There is one sorted file (of 1000 voters, not even 10,000). On my computer, running this data froze up my computer. Why do you think this is?

i) It appears that the binary search tree find method takes advantage of the tree being ordered and the find method of the regular binary tree does not. Does it gain an advantage that way? Briefly explain!

j) Are any differences significant in your opinion? Briefly explain!

Please make sure that your answers the these questions are your answers (and not somebody else’s or some sort of group answer)

Good Programming Practices:

· MAKE SURE YOUR PROGRAM WORKS! (i.e. gets correct results). It must provide all of the requested capabilities AND provide them in the expected way.

· Add YOUR NAME, e-mail address, and date in comments at the beginning of each file that you modify in the program

· Indent to show any structure of the program (The IDE usually does this well if you don’t go back and change things)

· You MUST include some comments that explain your program in order to get full credit, including a javadoc compatible comment for any methods that you write that don’t already have one.

Red Tape to Aid Grading:

· Please set the name of the project to something other than the default name (JavaApplication1, …).

· Add your name in a jlabel on the GUI form and/or in the title bar.

· Since a large part of the code you will be handing in is supplied in advance, you need to make your code easy to find via marking it with a comment with a bunch of #’s. E.g.

// ####################################

Name your zip file so that it identifies you as well as the assignment (e.g. yourlastname assignment9.zip). This is required for this assignment!!!!

Hand in:

Compressed (zipped) folder with your entire project containing all files related to the project, submitted to Blackboard.
Answers to the questions above.
(no print out required for this assignment)

Do your own assignments !!!! Work that is copied or done with somebody (when not assigned to a group) will be punished. If programs are copied, both students will receive a zero for the assignment. If significant sections of programs are copied, points will be taken off. Changing small aspects of a copied program does not make it not a copy. Asking another for help on a step or two in a many-step assignment is acceptable; looking at another person’s program is temptation for cheating; handing in a near duplicate program is cheating