SIMS 255: Assignment 5

    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.)

    1. 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)?
    2. 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 node).
      • (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 returns "torrac".

    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:

    • Find the base case(s) -- this solves the subproblem right away
    • Then try to find recursive definition or dependence
    • When writing the code:
      • First test for base cases (and error cases)
      • Then perform the recursive call if necessary
      • The parameter(s) to the recursive call should be "closer" to base case than the parameters for the original call
      • You may need more than one recursive call (but not for this problem)
      • Your code usually operates on the results of the recursive call(s) to produce the final result.
      A General Framework for the code: 

        if ( error condition )
    return (error value);
if( base case 1)
    return (terminal value 1);
   .
   .
   .
if( base case x)
    return (terminal value x);
make recursive call(s) (closer to some base case)
operate on returned value(s) as necessary
return answer

    (C) Trees

    1. Answer these questions/write the requested code after looking at my implementation of BinaryTree:

      • This code is quite limited. What fundamental operations are missing?
      • 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.)

    2. 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.

    1. (a) Which tree traversal algorithm is best for the TOC view?
      (b) Which tree traversal algorithm is best for the Progressive view?

    2. 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 class called 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.