Classwork 6 - Potpourtree

Definition

This Classwork will give you some wonderful practice analyzing the complexity of source code, as well as with recursive functions on trees!

Asymptotic Runtime Analysis

Definition

For each of the following prompts, analyze the worst-case asymptotic (Big-O, O(g(n))) runtime complexity of each specified method in the context of its class. For some, you’ll need to specify the value of n (i.e., the size of the input / problem).

Toolkit

You are expected to show your work in making these conclusions by annotating the source code directly in the skeleton provided. Your annotations should include:

• At the top of the function: assumptions about the worst-case performance, stated in plain English.
• Statements which consistent only of primitive operations that are constant cost should be assigned some unique identifier (c_i). If multiple constant cost statements occur on the same line (like with a for-loop), you may summarize those into a single (c_i).
• To the right of each statement in the source, in a comment, denote the cost of that statement, as well as its number of times repeated as a function of the size of the input / problem n.
• Remember to use the rule of composition where appropriate: methods that call other methods should assess the costs of helpers as well (annotated in the same way).
• At the very end, provide a total cost summary (T(n) = \sum_{c_i}), which is then bounded by some function (O(g(n))).

Example

Here’s an example of expected depth of annotation on the IntArrayList’s checkAndGrow method:

/*
 * Assumptions:
 *   - Let n = items.length, the size of the current ArrayList
 *   - Worst case performance = The items array is full and must be
 *     copied into a larger array
 */
private void checkAndGrow () {                             // Cost:
    if (this.size < this.items.length) {                   // c_1
        return;
    }
 
    int[] newItems = new int[this.items.length * 2];       // c_2
 
    for (int i = 0; i < this.items.length; i++) {          // c_3 * n
        newItems[i] = this.items[i];                       // c_4 * n
    }
 
    this.items = newItems;                                 // c_5
}
 
/*
 * Total Cost Analysis:
 * T(n) = c_1 + c_2 + c_5 + (c_3 + c_4) * n // OR you can simplify to:
 *      = O(1) + O(1) * n
 *      = O(n)
 */

Note: once this analysis has been done, in any other method wherein checkAndGrow has been called, you may simply substitute (O(n)) for that statement’s cost.

Remark

Complete each of the following exercises in the skeleton under the doc folder — a templated document has been made for you!

Find the worst-case asymptotic runtime cost of the uniqueWords method from Classwork 1 with the following assumptions:

• Let (n =) the number of words in the input sentence
• Assume that each word in the sentence is no longer than some constant (k)
• With the above, make reasoned assumptions for the costs of any methods that are called internal to uniqueWords.

/**
 * Returns the number of unique, unrepeated words that are found
 * in the given sentence sent
 * NOTE: This solution is not very good!!! It can be simplified
 * by using ArrayLists, but even those aren't the best choice here!
 * @param sent The sentence in which to count unique words
 * @return The number of unique, unrepeated words in sent
 */
public static int uniqueWords (String sent) {
    String[] words = sent.split(" ");
    String currWord, compWord;
    int count = 0;
 
    // Compare each pair of words (again, warning: not great)
    for (int i = 0; i < words.length; i++) {
        boolean repeatFound = false;
        currWord = words[i];
        if (currWord.equals("")) { continue; }
 
        for (int j = 0; j < words.length; j++) {
            compWord = words[j];
            if (currWord.equals(compWord) && i != j) {
                repeatFound = true;
                break;
            }
        }
 
        // Only increment the count for the first occurrence of each match
        count += (repeatFound) ? 0 : 1;
    }
 
    return count;
}

Suppose we are working on a method to reverse the contents of an ArrayList and come up with two possible implementations.

For each of the following 2 implementations, find the worst-case asymptotic runtime cost with the following assumptions:

• Let (n =) the size of the input ArrayList.
• Being able to lookup the ArrayList documentation and knowing the runtime costs associated with their operations, you can make claims about the costs associated with the ArrayList operations in what follows.

public static ArrayList<String> reverse_A (ArrayList<String> arr) {
    ArrayList<String> result = new ArrayList<String>();
    for (int i = 0; i < arr.size(); i++) {
        result.add(0, arr.get(i));
    }
    return result;
}
 
public static ArrayList<String> reverse_B (ArrayList<String> arr) {
    ArrayList<String> result = new ArrayList<String>();
    for (int i = arr.size() - 1; i >= 0; i--) {
        result.add(arr.get(i));
    }
    return result;
}

While performing runtime analysis, sometimes our notion of input size is not clear cut. In particular:

• We might have multiple data structures whose sizes may be different, but on which an algorithm’s runtime depends separately.

As such, consider the following isSubset method which (pretty poorly) determines if, for two input arrays of ints, all elements of the first array appear somewhere in the second.

Provide, once again, the worst-case asymptotic runtime analysis for this method with the following assumptions:

• Let n = a1.length and m = a2.length.

/**
 * Returns true iff all of a1's elements are found
 * within a2
 * @param a1 An array of ints
 * @param a2 An array of ints
 * @return Whether all elements of a1 are somewhere in a2
 */
public static boolean isSubset (int[] a1, int[] a2) {
    for (int i = 0; i < a1.length; i++) {
        boolean contained = false;
        for (int j = 0; j < a2.length; j++) {
            if (a1[i] == a2[j]) {
                contained = true;
                break;
            }
        }
        if (!contained) {return false;}
    }
    return true;
}

Trees and Recursion

The following section will help you understand Tree-based algorithms, which are typically recursive in nature.

In class, we examined the BinaryTreeNode class, which we will add to now (and is provided in the skeleton).

For each method below:

• Implement a recursive solution, thinking carefully about what the base and recursive cases are for the task at hand.
• Method signature not in the format you want it? Have the public method call a private helper of your choosing, which can better serve you in designing the recursion.

Design a levels method that returns how many levels the tree rooted at the calling node has. A level is defined as a depth containing at least 1 node.

=== Examples ===
  A       - The tree rooted at A has 3 levels because
 / \        it has 3 depths with at least 1 node each
B   C     - The tree rooted at B has 2 levels because
 \          it has 2 depths with at least 1 node each
  D       - The tree rooted at C or D has but 1 level
            because each are single-node trees

Implement the doubleTree method that modifies a binary tree rooted at the calling instance of BinaryTreeNode by performing the following:

1. Duplicates every node in the original tree, placing the duplicate at the left child of the original.
2. The relative structure of the tree is preserved such that if any node has a left child before the duplication, that previous child is now the left child of the duplicate.

=== Example 1 ===
This tree:
  2
 / \
1   3
 
Is doubled to this tree:
       2
      / \
     2   3
    /   /
   1   3
  /
 1
 
=== Example 2 ===
This tree:
  2
 / \
1   3
   /
  4
 
Is doubled to this tree:
       2
      / \
     2   3
    /   /
   1   3
  /   /
 1   4
    /
   4

Definition

I’ve given you all of the tests you’ll need to pass for this assignment — get that Tree practice in!

GitHub Classroom + Skeleton

Definition

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

Assignment

Classwork 6 - GitHub Classroom

---

Submission

Definition

You will be submitting your assignments through GitHub Classroom!

What

Complete all classes that accomplishes the specification above, in the project structure given in the skeleton above.

Your asymptotic analysis will be saved in the doc folder of the skeleton, and your tree-related problems in the src/tree/binary folder.

How

To clone this assignment (if you need a refresher), consult the guide here:

Assignment

GitHub Classroom Tutorial

To submit this assignment:

• Simply push your final, submission copy to the GitHub Classroom repository associated with you or your group.
• If you worked in a group (3 individuals maximum), ensure that your GitHub Classroom group includes all members, and place all group members’ names at the top of all submitted files (in appropriate JavaDoc commenting fashion) AND in the accompanying readme file.

---