Due Tuesday October 29.
You may work with
another person on this, but you must be in the same room with them when
you work on it and you should follow pair programming
practices when writing code.
Read through the assignment in its entirety. The longest part is at
the very end; it requires you do a fair amount of programming.
Some other questions look long, but this is because I'm providing what
I hope is helpful information.
Turn in assignment as both a hardcopy in class (you do not need to
print out all the separate webpages for part D in this assignment,
however, please indicate the link to the resulting webpages somewhere
in your assignment writeup) and a zipped file, using this link to
cardea. Please have all your code as runnable .java files.
(A) Algorithm Analysis
Consider the case of inserting nodes into a Binary Search Tree.
(Notice that I am asking about the kind of tree in which the nodes are
organized according to the values of the keys, but I am not asking
about AVL trees. Also note that you do not need to write code to
do this problem.)
Assuming the keys are all positive integers, what is the running time
for inserting all of the nodes from a set of n nodes whose
key values range from 1 to n, if the
values of the keys for the nodes arrive in descending order (e.g.,
arrive as key n, then key n-1, then key n-2, ... 1)?
Consider a set of n nodes for which
the values for the keys of the nodes appear in such an order
that the final resulting tree is a perfectly balanced tree.
(a) Make up a set of numbers for the keys that could produce such a
tree, and show the order in which these keys appear in the input.
- (b) Show
a picture of such a tree that has at least 12 internal nodes (be sure
you label every node with the number of the key that appears in that
- (C) What is the running time for inserting all of the
nodes (for the general case of n, not for the example of 12 nodes!)?
(B) Recursion Practice
(1) Write a recursive method String reverseOrder(String s) that creates a reversed
version of s. For example, if s has the value "carrot", the method
Show the output of running this on examples.
(2) Optional Bonus Question
Write a method boolean isPalindrome(String s) that returns whether the
string s is a palindrome or not. Remember that a palindrome is a
string that reads the same forwards as backwards, for example noon,
racecar, madam. For simplicity, you may assume the string s has the
same capitalization throughout and no spaces or punctuation.
Show the output of running this on examples.
To help you with this question, here is advice on
how to write recursive functions:
- Answer these questions/write the requested code after looking at
my implementation of BinaryTree:
- This code is quite limited. What fundamental operations are
- Consider the method for DF Traversal (printDFS).
It assumes that the BinaryTree really is a tree, as opposed to a
general graph. What can happen when this method is run if the tree
structure assumption is violated?
- Write a method BFSearch, which operates on a BinaryTree and takes
as input a String to search for. This method should perform a breadth
first traversal over the Binary Tree, and if it finds a node whose
name attribute matches the input String, it returns the integer value
stored at that node. When it finds the matching name, it should stop
doing the breadth first traveral. If it does not find a matching
name, then it should return -1. (Optional -- if you want to make it
smarter about what to return if it doesn't find the searched-for name,
go ahead and do that.)
- Start with my implementation of a tree in which each node can
have an arbitrary number of children. I've called this class
FullTree.java. (This makes use of Queue.java which we worked on in class.)
- Write a recursive method DFTraversal, that does a depth first
traversal on the FullTree. Assume the order for the children should
correspond to the order in which they were inserted originally.
Include indentation (via spaces) that shows the level of the tree that
is being printed out (I did an example of this in the BFTraversal code in FullTree).
(D) Creating Web Pages from a Tree Data Structure
Consider the problem of presenting a category hierarchy (such as
found at Yahoo or Looksmart) on web pages. There are two main ways
you might want to lay this out for users to see. One way shows all
the categories at once on one page, with appropriate indentation.
Let's call this the Table-Of-Contents (TOC) view. The other way shows
the first level of the categories on the first page, with hyperlinks
to pages that contain subsequent levels of the hierarchy
(recursively). (For example, a link on the first page that reads
animals would link to a page that listed mammals, reptiles,
and birds. The mammals link would link to a page listing
cats, dogs, bears, etc. The reptiles link would link
to a page listing lizards, snakes, dragons, etc.)
Let's call this the Progressive view.
To help you visualize this, see this
sample output from Kaichi's implementation on ski resort data.
- (a) Which tree traversal algorithm is best for the TOC view?
(b) Which tree traversal algorithm is best for the Progressive view?
- Using the classes and methods that I provided in part (C) as a starting point,
write code to generate web pages in both the TOC view and the
Progressive view. The code has comments in it explaining how it works.
I have written a method called
buildFullTreeFromFile that reads in a file and produces a
FullTree, so you don't need to do that. I've also put together a
WebPage that gets you started on producing web
pages. Note that one of the two views must use hyperlinks and
create a set of pages to hyperlink to. You can use relative path
names in your hyperlinks if you like, so long as the code works.
You probably need to modify the FullTree code to include an
attribute for storing a hyperlink. You can modify it directly or
use the Java subclass mechanism to extend the FullTree class.
You need to start with some data for generating a hierarchy.
You may use real category labels from an existing hierarchy to
illustrate the results, or make up your own hierarchy. Your
hierarchy must contain at least 60 nodes and a height of at
least 3 (recall that the root is at level 0, so a tree of height
3 has 4 levels). If you like, you can instead use this hierarchy
of descriptions of ski resorts provided by Kaichi.
In your assignment writeup, be sure to give us links to the web
pages that you generate as a result of running the code.