Problem Set 9

due by 11:59 p.m. on Friday, December 4, 2020

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs112-staff@cs.bu.edu.

Part I

• 50 points total*

Creating the necessary file

Problems in Part I will be completed in a single PDF file. To create it, you should do the following:

1. Open the template that we have created for these problems in Google Docs: ps9_partI

2. Select File->Make a copy..., and save the copy to your Google Drive using the name ps9_partI.

3. Add your work to this file.

4. Once you have completed all of these problems, choose File->Download as->PDF document, and save the PDF file on your machine. The resulting PDF file (ps9_partI.pdf) is the one that you will submit. See the submission guidelines at this specification.

Important: Put your responses to each of the following problems in the appropriate section of the ps9_PartI template that you created on Google Drive.

Problem 1: Binary tree basics

14 pts. total; individual-only

Consider the following binary tree, in which the nodes have the specified integers as keys:

1. What is the height of this tree?

2. How many leaf nodes does it have? How many interior nodes?

3. If a preorder traversal were used to print the keys, what would the output be?

4. What would be the output of a postorder traversal?

5. What would be the output of a level-order traversal?

6. Is this tree a search tree? Explain briefly why or why not.

7. Is this tree balanced? Explain briefly why or why not.

Problem 2: Tree traversal puzzles

8 points total; 4 points each part

1. When a binary tree of characters (which is not a binary search tree) is listed in postorder, the result is ENIMOPTFRW. Inorder traversal gives IENWOMRPFT. Construct the tree by editing the diagram we have provided in section 4-1 of the part I template.

   • Click on the diagtam and then click the Edit link that appears below the diagram.

   • Edit the diagram. It includes the necessary nodes and edges, but you will need to move them into the appropriate positions and connect them.

   • When you have completed your edits, click the Save & Close button.

2. When a binary tree of characters (which is not a binary search tree) is listed in preorder, the result is TRMESBONVY. Postorder gives ESMRVYNOBT. Construct the tree by editing the second diagram in the part I template. (There is more than one possible answer in this case.)

Problem 3: Binary search trees

8 pts. total; 4 pts. each part; individual-only

Consider the following tree, which is a binary search tree.

1. Show the tree as it will appear if 25 is inserted, followed by 51 by editing the diagram that we have provided in 5-1 of the part I template.

2. Suppose we have the original tree and that 53 is deleted and then 35 is deleted, using the algorithm from the lecture notes. Show the second diagram.

Problem 4: Determining the depth of a node

12 points total; 4 points each part; individual-only

The code below represents one algorithm for finding the depth of a node in an instance of our LinkedTree class from lecture.

The recursive depthInTree() method takes two parameters – an integer key and the root of a tree/subtree – and it returns the depth in that tree/subtree of the node with the specified key. It is a private static method that can only be called from within the class.

The separate depth() method is a “wrapper” method that makes the initial call to depthInTree(), passing in the root of the tree as a whole and returning whatever value depthInTree() returns – which will be the depth in the entire tree of the node with the specified key.

If the key is not found, the methods return -1.

public int depth(int key) {
    if (root == null) {    // root is the root of the entire tree
        return -1;
    }

    return depthInTree(key, root);
}

private static int depthInTree(int key, Node root) {
    if (key == root.key) {
        return 0;
    }

    if (root.left != null) {
        int depthInLeft = depthInTree(key, root.left);
        if (depthInLeft != -1) {
            return depthInLeft + 1;
        }
    }

    if (root.right != null) {
        int depthInRight = depthInTree(key, root.right);
        if (depthInRight != -1) {
            return depthInRight + 1;
        }
    }

    return -1;
}

1. For a binary tree with n nodes, what is the time complexity of this algorithm as a function of n in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.

2. If the tree is a binary search tree, we can revise the algorithm to take advantage of the ways in which the keys are arranged in the tree. Write a revised version of depthInTree that does so. Your new method should avoid considering subtrees that couldn’t contain the specified key. Like the original version of the method above, your revised method should be recursive.

   Note: In the files that we’ve given you for Part II, the LinkedTree class includes the methods shown above. Feel free to replace the original depthInTree() method with your new version so that you can test its correctness. However, your new version of the method should ultimately be included in your part I template.

3. For a binary search tree with n nodes, what is the time complexity of your revised algorithm in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.

Problem 5: 2-3 trees and B-trees

8 points; 4 points each part; individual-only

Illustrate the process of inserting the key sequence

J, E, I, H, C, F, B, G, D, A

into an initially empty 2-3 tree and an initially empty B-tree of order 2.

1. Insert this sequence into an initially empty 2-3 tree by editing the diagram that we have provided in the part 1 template. Show the tree after each insertion that causes a split of one or more nodes, and the final tree.

   We have given you a sample diagram that includes nodes of different sizes. Make copies of the diagram so that you can use separate diagrams for the results of each insertion that causes a split, and for the final tree. Note that you do not need to keep the shape of the tree that we have given you. Rather, you should edit it as needed: deleting or adding nodes and edges, replacing the Xs with keys, adding or removing keys, and making whatever other changes are needed.

Because we are not fully covering B-trees this semester, you are not responsible for answering 5-2. You can leave that section blank in your copy of ps9_partI.

2. Insert this sequence into an initially empty B-tree of order 2 by editing the diagram that we have provided in the part I template. Show the tree after each insertion that causes a split of one or more nodes, and the final tree. Here again, you should make copies of the diagram that we have given you and edit them as needed. In both cases, show the tree after each insertion that causes a split of one or more nodes, and the final tree.

Part II

50 points total

Preparing for Part II

Begin by downloading the following zip file: ps9.zip

Unzip this archive, and you should find a folder named ps9, and within it the files you will need for Part II. Make sure that you keep all of the files in the same folder.

Problem 6: Palindrome tester

20 points; individual-only

1. As you know a palindrome is a string like "radar", "racecar", and "abba" that reads the same in either direction. To enable longer palindromes, we can ignore spaces, punctuation, and the cases of the letters. For example:

   "A man, a plan, a canal, Panama!"
   

   is a palindrome, because if we ignore spaces and punctuation and convert everything to lowercase we get

   "amanaplanacanalpanama"
   

   which is a palindrome.

   In the file Palindrome.java that we’ve included in the ps9 folder, add a static method called isPal() that takes a String object as a parameter and determines if it is a palindrome, returning true if it is and false if it is not.

   A string of length 1 and an empty string should both be considered palindromes. Throw an exception for null values.

   Although we can implement solutions to this problem using recursion or an appropriately constructed loop that manipulates the String object directly, your method must use an instance of one or more of the following collection classes from the ps9 folder:

   • ArrayStack
   • LLStack
   • ArrayQueue
   • LLQueue

   You must not use any other data structure, including arrays or linked lists other than the ones that are “inside” instances of the above collections. Rather, you should put individual characters from the original string into an instance of one or more of the above collections, and use those collection object(s) to determine if the string is a palindrome.

   For full credit, you should:

   • Write your method so that spaces, punctuation, and the cases of the letters don’t prevent a string from being a palindrome. To put it another way, make sure that your method only considers characters in the string that are letters of the alphabet and that it ignores the cases of the letters. See our example above.

   • Make your method as efficient as possible. In particular:

     • You should perform only one iteration over the original String object. After that one iteration, any additional manipulations of the characters should be done using the collection object(s) that you have chosen to use.

     • Because we want to avoid unnecessary scanning, you may not use any of the built-in String methods except charAt() and length().

   Hints:

   • When constructing the collection object(s) that you decide to use, you will need to specify the appropriate data type for the items in the collection. Because char values are primitives, you should use the corresponding “wrapper” class, which is called Character.

   • You may also find it helpful to use the Character.toLowerCase() or Character.toUpperCase() method.

   • Remember that char values are essentially integers, so you can compare them just as you would compare integers.

2. For professional programmers, writing well-formatted units tests is an extremely important part of their work. In the main() method of Palindrome.java, we’ve given you an example of what such a unit test should look like.

   Add five additional unit tests for your isPal() method to the main() method. Your unit tests must follow the same format as our example test. In particular, the output of each of your unit tests should include:

   • a header that specifies the test number and a description of what is being tested
   • the actual return value that you get from that test
   • the expected return value
   • whether the actual return value matches the expected return value.

   Put each test in the context of a try-catch block so that you can handle any exceptions that are thrown. Leave a blank line between tests.

Problem 7: Adding methods to the LinkedTree class

30 points; individual-only

Make sure to begin by following the instructions given above under Preparing for Part II.

In the file LinkedTree.java, add code that completes the following tasks:

1. Write a non-static depthIter() method that takes takes an integer key as its only parameter and that uses uses iteration to determine and return the depth of the node with that key. Like the recursive method that you wrote for Problem 4, your iterative method should take advantage of the fact that the tree is a binary search tree, and it should avoid considering subtrees that couldn’t contain the specified key. It should return -1 if the specified key is not found in the tree.

   Note: There are two methods in the LinkedTree class that can facilitate your testing of this method and the other methods that you’ll write:

   • The insertKeys() method takes an array of integer keys, and it processes the array from left to right, adding a node for each key to the tree using the insert() method. (The data associated with each key is a string based on the key, although our tests will focus on just the keys.)

   • The levelOrderPrint() method performs a level-order traversal of the tree and prints the nodes as they are visited; each level is printed on a separate line. This method doesn’t show you the precise shape of the tree or the edges between nodes, but it gives you some sense of where the nodes are found.

   For example, below are some tests of depthIter(). To help you visualize the tree, it’s worth noting that we’re using an array of keys that produces the binary search tree shown in Problem 5. For example:

   LinkedTree tree = new LinkedTree();
   System.out.println( tree.depthIter(48) );
   

   should output:

   -1
   

   and,

   int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   tree.insertKeys(keys);
   tree.levelOrderPrint();
   

   should output:

   44 
   35 53 
   23 48 62 
   28 57 80
   

   and,

   System.out.println( tree.depthIter(48) );
   System.out.println( tree.depthIter(28) );
   System.out.println( tree.depthIter(44) );
   System.out.println( tree.depthIter(30) );
   

   should output:

   2
   3
   0
   -1
   

2. Write two methods that together allow a client to determine the number of even keys in the tree:

   • a private static method called numEvenKeysRec() that takes a reference to a Node object as its only parameter; it should use recursion to find and return the number of even keys in the binary search tree or subtree whose root node is specified by the parameter.

   • a public non-static method called numEvenKeys() that takes no parameters and that returns the number of even keys in the entire tree. This method should serve as a “wrapper” method for numEvenKeysRec(). It should make the initial call to that method – passing in the root of the tree as a whole – and it should return whatever value that method returns.

   For example:

   LinkedTree tree = new LinkedTree();
   System.out.println( tree.numEvenKeys() );
   

   should output:

   0
   

   and,

   int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   tree.insertKeys(keys);
   System.out.println( tree.numEvenKeys() );
   

   should output:

   5
   

3. Write a non-static method deleteMax() that takes no parameters and that uses iteration to find and delete the node containing the largest key in the tree; it should also return the value of the key whose node was deleted. If the tree is empty when the method is called, the method should return -1.

   Important: Your deleteMax() method may not call any of the other LinkedTree methods (including the delete() method), and it may not use any helper methods. Rather, this method must take all of the necessary steps on its own – including correctly handling any child that the largest node may have.

   For example:

   LinkedTree tree = new LinkedTree();
   tree.deleteMax()
   

   should output:

   -1
   

   and,

   int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   tree.insertKeys(keys);
   tree.levelOrderPrint();
   

   should output:

   44 
   35 53 
   23 48 62 
   28 57 80
   

   and,

   System.out.println( tree.deleteMax() );
   tree.levelOrderPrint();
   

   should output:

   80
   44 
   35 53 
   23 48 62 
   28 57
   

   likewise,

   System.out.println( tree.deleteMax() );
   tree.levelOrderPrint();
   

   should output:

   62
   44 
   35 53 
   23 48 57
   28
   

   Note that first we delete 80, because it is the largest key in the original tree. Next we delete 62, because it is the largest remaining key. As a result of these deletions, 57 moves up a level in the tree, because it is now the child of 53.

4. In the main() method, add at least two unit tests for each of your new methods.

   • For part 2 (numEvenKeysRec()/numEvenKeys()), your unit tests only need to call numEvenKeys(), since doing so will also call numEvenKeysRec().

   • Use the same unit-test format that we specified in Problem 6.

   • We have given you a model unit test in main() that tests the depth()/depthInTree() methods from Problem 4. Note that these methods are distinct from the depthIter() method that you are writing for this problem.

Submitting Your Work

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• ensured that the signature of the methods specified in the assignment have not been changed.
• You have verified that your programs satisfy all the performance tests in the templates;

Submitting your work for Part I

Submit your ps9_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download as->PDF document, and save the PDF file on your machine.

2. Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the questions in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Submitting your work for Part II

You should submit only the following files:

• Palindrome.java
• your modified LinkedTree.java file containing your work on Problems 7 if you worked with a partner on Problem 7, make sure that you each submit a copy of your joint work on that problem, and that you include comments at the top of each file specifying the name and email of your partner

Here are the steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.