Assignment 1

 

  1. PART I: Pen-and-paper exercises (submit as PDF).
    1. Analyze the following code and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis. 
          void compute (int n, double[][] A, double[][] B, double[][] C)
    {
       for (int i=1; i <= n; i++) {
         for (int j=1; j <= n; j++) {
           int p = i, q = i;
           while ( (p < n) && (q < n) ) {
             A[i][j] += B[p][q] + C[p][q];
             p *= 2;
             q *= 2;
           }
         }
       }
    }
    2. Insert the nine (1-letter) keys "A B C D E F G H I" into an empty multiway tree of degree 2 and show the intermediate steps. Also, work out the insertion steps for a multiway tree of degree 3.
    3. Show the intermediate trees when the seven keys "D A C B E F G" get inserted into a self-adjusting binary tree. Remember that a newly inserted element is moved to the root so that every insertion will cause re-organization. Write down the which rotation case (e.g., Case 1(a), Case 3, etc) you are using with each diagram.
    4. Show the missing steps in inserting the remaining elements in getting from the first RL-tree diagram in Part-II below to the last one ("after remaining insertions ..."). That is, show the steps in adding 7 and then 6.
    5. Module exercise 3.2
    6. Module exercise 3.8
    7. Module exercise 3.14
    8. Who devised Mergesort and what is this person's role in the history of computer science?
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. PART II: Implement (1) a binary search tree, and (2) a new type of tree, which we will call a random-label (RL) tree.

    Recall that an ordinary binary tree can become highly imbalanced. For this purpose, several sophisticated trees (like AVL or red-black) have been devised. At the same time, also recall that simple randomization (as we did in randomly picking the partition element in Quicksort) is also effective. So, one approach to improving binary trees is to introduce some randomization. We'll define a random-label (RL) tree to be a binary tree with the following additional features:

    • Each node has, beyond the usual pointers, a label called the numeric label, which will store a random number between 0 and 1 (so the numeric label is a double).
    • Every node will satisfy the standard binary tree property: all nodes in its left subtree will have key value less than that of the node, and all nodes in the right will have value larger than that of the node.
    • Every node will ALSO satisfy a heap-like property: the numeric label of a node will be less than the numeric labels of each of its children.
    • When is the numeric label created? It is created at the time of insertion just before inserting it into the tree. The numeric label is randomly generated from a random number generator.
    • How can this work? Through rotations. When a new key is inserted, we insert in the normal binary tree fashion (wherever the search ends). At this time, it is quite possible that the new node's numeric label is smaller than its parent's label. In this case, we rotate the new node into its parent's position (the same rotations we used with AVL trees). Then, right after that rotation the new node will have a new parent and that new parent's numeric label may be larger, in which case we rotate our new node further up ... and so on. The new node might in fact go all the way to the root position.
    • All these rotations might not produce a balanced tree every time, but the hope is that it'll work on average.
    • For example, consider the keys 1, 3, 5, 7, 6 inserted in that order. And let's suppose that the random values (between 0.0 and 1.0) for these keys happen to be 0.7, 0.3, 0.2, 0.8 and 0.1. The steps in inserting the first three elements are shown here (without left-right pointers):

      After the remaining insertions, we get:

    • Note: in your PDF for the pen-and-paper part of the Assignment, show the steps between the first and second diagrams above.
    • Your binary search tree algorithm will need to implement the TreeSearchAlgorithm interface that itself extends the OrderedSearchAlgorithm interface.
    • Your RL-tree algorithm will also need to implement the TreeSearchAlgorithm interface.
    • For testing deletion, the OrderedSearchAlgorithm interface has a deletion method Note that the other operations are to find the successor and predecessor of a given key.
    • Implement insertion and search for both the binary search tree and the RL-tree. Implement deletion for only binary search trees.
    • Implement successor and predecessor for the binary tree, but not for the RL-tree.
    • Important: you will need to understand how to enumerate elements in a data structure before starting your assignment. In particular, we will be using Java's Enumeration interface. If you haven't done this before, please read through an example, perhaps the one in Module 7 of CS-2113. Here is another simple example: DataStructureWithEnumeration.java. Your own enumeration implementation can be very simple -- it does not have to be efficient.
    • Note that you will be building both trees using the TreeNode class.
    • For the binary tree, all you will need from TreeNode are the three fields left, right and parent. You may choose to use a constructor if you wish but do not have to since all these variables are public.
    • Make sure that your code properly sets the parent field for each tree node.
    • For the RL-tree, you will also need to store the random label in the numericLabel field. You can generate a random value between 0 and 1 by calling the uniform() method in UniformRandom.java.
    • As usual, you will need to include tests in your main method. In particular, include the example from Part I above.
    • Name your binary tree file MyBinarySearchTree.java.
    • Name your RL-tree file MyRLTree.java.
    • Suggested steps for implementation:
      • First, implement search and insertion for the simple binary search tree. This will get you comfortable with "tree" programming. Try to do this in the first week.
      • Next, get search and insertion working for RL-trees.
      • Then, implement deletion for binary search trees and test. You do NOT need to implement deletion for the RL-tree.
    • Update algtest by using this version: algtest.jar
    • Test your binary tree (just by itself) using a1.props.
    • Test your RL tree (just by itself) using a1.props2.
    • Compare the performance of the RL-tree with the binary search tree using a1.props3.
    • Test deletion in the binary tree using a1.props4.
    • You are advised to initially set testLarge=false and testPerformance=false while you are testing and debugging.
    • Relevant links:
      Algorithm interface
      SearchAlgorithm interface
      OrderedSearchAlgorithm interface
      TreeSearchAlgorithm interface
      TreeNode class
      ComparableKeyValuePair class
    • To summarize: you will need to provide empty implementations of setPropertyExtractor for both Binary and RL-trees, and empty implementations of successor, predecessor, delete for the RL-tree.

Submission: