CSE 214 - HW 3

HW 3 - Note, this HW has 2 Parts

SETUP

Note that in this assignment, you will have to use the eclipse IDE. To start:

Download cse214_hw3_fall2009.zip and save it to a directory of your choice. Don't unzip the file! You'll need to remember where you put it.
Open eclipse now, and choose whatever workspace directory you like.
Click on:
- File
- Finish
You should now have a project with all the files necessary to do this homework, including source and data files.
Verify that the project was properly imported into eclipse. Are you able to open and edit the source code in eclipse?
NOTE: There should be no compiler errors after you import the zip file

Part 1 - using an array-implemented tree to predict this year's Major League Baseball Playoffs.

In class we mentioned how a full binary tree can be managed efficiently using an array rather than node objects. That's what we'll do in this part. In the Major League Baseball playoff system, 8 teams compete for one World Series Championship title. We can think of such a playoff as a bracket. A bracket for such a tournament could logically be managed by a full tree data structure. Examine the following 3 files:

BaseballTeam.java
BaseballPlayoffsFrame.java
BaseballPlayoffsManager.java

The BaseballPlayoffsFrame class has a main method that simply opens up a GUI, loads your tree with data concerning the 8 teams in the playoffs, and handles user input. The GUI has two buttons, which each time you press them they should produce random results weighted by team records for all playoff games. It will ask the tree managing class to perform this operation, sometimes asking it to perform this task, one doing it recursively, and one iteratively.

To do this, you will manipulate the tree, which stores all of its data in an array similar to the technique we discussed in lecture. I have defined the initTeams method, which takes an array of BaseballTeams, and places its contents into our tree-array, putting them into the indicices representing the tree leaves. All parent nodes, including the root, start out storing null, the reason is we don't know who's going to win the playoffs yet, only the teams entering, and based on the order they are given, who each team's opponent will be in the first round. You will have to write code that fills in the playoffs bracket with results.

YOUR TWO METHODS, BOTH IN THE PlayoffsManager CLASS:

Define the runPlayoffsRecursively method such that when called, it fills in the entire bracket with playoffs results. Games should be determined simply by calling the playGame method, which is a weighted method for randomly selecting a winner in a game between two team arguments. Note that you should update the records of the teams as the playoff games are played. You must use recursion in solving this method.

Define the runPlayoffsIteratively method such that when called, it does the same thing that the runPlayoffsRecursively method does, except that it does it using iteration, without recursion.

HINT: Remember how we talked about pre, in, and post order traversal in a tree and the differences between them. Note that post order traversal means that parent node data is processed after its children's node data is processed. This seems a natural fit for the recursive portion of this problem, since we can't compute the playoff winner until we know who has won in the previous rounds.

Part 2 - PresidentBinarySearchTree

In this HW we are going to use a Binary Search Tree (BST) to keep President objects sorted so that we may access them efficiently. In fact, Binary Search Trees are only useful if their contents are sorted. We will use the President number as the criteria for sorting our objects.

Examine the following files:

PresidentsData.txt
President.java
PresidentBinarySearchTree.java
PresidentTreeFrame.java

Go through the code of these classes and read the documentation. The PresidentTreeFrame has a main method. That application will render your PresidentBinarySearchTree. You will define methods for adding, removing, and getting information about the nodes.

YOUR FOUR METHODS, ALL INSIDE THE PresidentBinarySearchTree CLASS:

public void addPresidentIteratively(President president) - define the addPresidentIteratively method such that it adds the president parameter to the tree in its proper sorted location. It should do so using an iterative approach, rather than the recursive approach we used in lecture. Also note that you should not add duplicates to your tree.

public double calculateAverageYearsIteratively() - Define this method such that it calculates the average years in office of all the presidents in the entire tree. Recall that we did this in lecture using a recursive solution. I have provided a button for performing this function to help you compare the results of your own iterative solution.

public President removeRootIteratively() - Define the removeRootIteratively method such that when called it removes the root node from the tree. In order to do this, you'll have to find a new root. If your root's left child is null, it should be its right child. If your root's right child is null, it should be its left child. Otherwise, promote the rightmost node on the left side of the tree. Be careful to maintain all parent-child relationships. In addition, your method must return the data from the node that was removed.

public President removeRootRecursively() - Define this method such that it also removes the root from the tree, but does so using a recursive solution. For promoting nodes to become the root, promote the leftmost node on the right side of the tree (this is the opposite of the iterative solution). Again, your method must return the data from the node that was removed.

Handin Instructions

Go to the hand-in instructions page for the details on the required handin procedure. You must hand in by the designated due date and time in the course schedule for credit. Late assignments will not be graded.

Grading

All assignment will be graded purely based on program performance. Submissions that do not compile will receive 0 points. Submissions that never produce correct results will receive 0 points. The TAs will test your submissions using various input, and grades will be awarded depending on how often your code produces the correct results.

Web page created and maintained
by Richard McKenna