CS 206 - Introduction to Data Structures
Assignment 9: Due 11:59PM Thursday Nov 21 11:59pm
Part 1 -- Making better trees
The tree program discussed in class on Nov 14 makes a drawing that is tree-like without really looking much like a tree. The challenge for this assignment is to "tweak" the tree code so that the resulting tree is more tree-like. You can do whatever you want to the existing code but you must preserve the "fractal" nature of the code. That is, you cannot have rules that apply only to short branches (or only to long branches). The one exception to this is that you may do something different when you get to the base case. The existing code does nothing at the base case other than stop. You could for instance, add a leaf at the end of every branch.
I encourage you to experiment with colors, and with drawing shapes other than just lines. For instance, you might replace the simple line drawer with code that draw lines of different thickness depending on the distance from the trunk. There are lots of other options for drawing that you can try in java.awt.Graphics2D. https://docs.oracle.com/javase/7/docs/api/java/awt/Graphics2D.html and lots of on-line documentation and suggestions for its use. Moving in a different direction, you might experiment with making trees that distinctly different from the default. For instance, can you make a christmas tree like tree.
Immediately after Thanksgiving we will have an vote in class for the best tree. So everyone else will see your tree. A part of your grade will be based on that vote. I will post your trees outside my office. I will also make an attempt to take over the monitor in the hallway to show some trees being fractally built.
The code from class for tree building is in /home/gtowell/Public206/HW9/Tree.java. It is also on the class web site.
If you are really not connecting with trees (ouch) you may try try the snowflake code instead. It is on the class website
Part 2 -- Improving Quicksort
The quicksort code discussed in class is fast. Certainly. But it might be improved. In this part of the assignment you will attempt to do so. You improvement should take two forms:
- The partition method just uses the last item as the partition. This may be a very poor partitioner. A simple approach to getting a better partitioner is the "median of 3" trick. The idea is to look at the last 3 items and pick the middle value of those last 3 as the partitioner. Thus, you are far less likely to get a very bad partition.
- As we discussed in class, it can be quicker when the size of the subset to be sorted gets small, to use insertion sort rather than continuing to partition. (We applied insertion sort to mergesort in class. Code for this is on the class website.) Do the same for quicksort. (Note that adding insertion sort to quicksort is a little harder than for mergesort as quicksort is dealing with a portion of an array rather than a whole array. You will need to adapt insertion sort to deal with this issue.)
The code from class for tree building is in /home/gtowell/Public206/HW9/QuickSort.java. It is also on the class web site (within ST.java on Nov 14)
Electronic Submissions
Your program will be graded based on how it runs on the
department’s Linux server, not how it runs on your computer.
The submission should include the following items:
- README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
- Within the README file, include a brief (max 1 paragraph) reflection on what went well and/or poorly and why
- Instructions for making your "best" tree. The instructions may be as simple as "execute the class XXX ". If you have command line parameters or take input from the user be sure to say what that is.
- A summary of the results of your quicksort speedup efforts. You should include in this summary what the effect of each of the techniques above is independently and in combination. (You might find that one, the other or both result in a negative speedup.) Include instructions for replicating these results. The instructions could require simple code changes like commenting out some lines, etc.
- Source files: Every .java file used in the final version of every part of your project (including the imported files)
- Unique Data files used: If any (you might have a leaf image?)
- An image of your best tree. Perhaps the simplest way of doing so is to just take a picture of the screen. There are better ways.
DO NOT INCLUDE: Data files that are read from the class site.
The following steps for submission assume you are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/
- For this assignment N=9
- Put the README file into the project directory and your maze (/home/YOU/cs206/AssignmentN)
- Go to the directory /home/YOU/cs206
- Enter submit -c 206 -p N -d AssignmentN
For more on using the submit script click here