CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 8

To Be Turned In

Except where noted, these are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

  1. Don’t forget: You should be keeping an individual log about your team project work so that you can write a performance evaluation for each of your teammates. You do not need to turn in this log, but I wanted to remind you while I had your attention.
  2. (9 points) Draw expression trees representing each of the following expressions, assuming the standard Java (and Spreadsheet) precedence and assoicativity rules:
    1. 3.14 * 3.14 - 1/2
    2. LOG(218,2)
    3. A1 * A2 >= B1 * B2

  3. (11 points) Give the expression represented by the expression tree below. Include parentheses as necessary so that your expression matches the evaluation order implied by the tree.

  4. (15 points) This problem is based on Weiss Exercise 19.19, but I’m rewriting it here to clarify some things and eliminate part of the exercise. You may do this as a pencil-and-paper exercise, or you may try to get it working in code. If you do the latter, please turn in a print out of the code you write.

    Implement a static, factory method for BSTreeWithRank that takes two indices, low and high, and constructs an optimally balanced BSTreeWithRank that contains all the integers between low and high, inclusively. (The signature of the method is given below.) All leaves should be at the same level (if the tree size is 1 less than a power of 2) or on two consecutive levels. Your routine should run in linear time. No partial credit will be awarded for solutions that do not run in linear time.

    For example, calling BSTreeWithRank.buildRangeTree(4,12) would yield a tree with 9 nodes and root element 8. Calling findKth(0) on that tree would yield 4. Calling findKth(8) would yield 12.

    Assume the BSTreeWithRank and BNodeWithRank implementations that we developed in class and that were shared in the BSTWithRankSolution project in SVN.

    This method can be implemented using a recursive helper method. Below is the required method, plus a stub for the recursive helper method. You just need to give the details of the helper method. Be sure to show how the rank of each node is set, as well as how it is connected to the rest of the tree. 

    public static BSTreeWithRank<Integer> buildRangeTree(int low, int high) {
    BSTreeWithRank<Integer> result = new BSTreeWithRank<Integer>();
    result.root = recursivelyBuildRangeTree(low, high);
    return result;
}

private static BNodeWithRank<Integer> recursivelyBuildRangeTree(int low, int high) {
    // TODO Write the details
}