Problem Set 7

due by 11:59 p.m. on Tuesday, April 16, 2024

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 folder

Create a subfolder called ps7 within your cs112 folder, and put all of the files for this assignment in that folder.

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. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps7_partI.

4. Add your work for the problems from Part I to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps7 folder. The resulting PDF file (ps7_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Choosing an appropriate list implementation

9 points total; 3 points each part; individual-only

In lecture, we considered two different implementations of the list ADT: ArrayList and LLList. For each of the following applications, decide which list implementation would be better for that particular application. Your should consider both time efficiency and space efficiency, and you should assume that both implementations have an associated iterator like the LLListIterator that we discussed in lecture. Explain your answers.

1. You need to keep track of the orders placed to your online store. At the start of each month, you start with an empty list; as orders are made, you add them to the list. The number of orders varies greatly from month to month. You regularly display the list of orders, starting with the most recent order and working backwards towards the least recent one.

2. The ERC wants you to maintain its weekly list of workshops. The number of workshops is fairly consistent from week to week. The workshops will be added to the list in chrological order, and they will also be displayed in that order.

3. You are maintaining a list of information about all of the courses that are being offered in the Fall. Each course has an id number between 1 and 5000, and you decide to use that id number as the position of the course’s record in the list. Once the list of courses is created, there are very few additions or removals. However, you need to frequently access the items in the list during the course registration period. Every time that a student registers for a course, you need to access that course’s record in the list so that you can increment the course’s count of enrolled students.

Problem 2: Switching from one list implementation to another

10 points total; individual-only

The following method takes an instance of our ArrayList class from lecture, and it “converts” it into an LLList object that contains the same values. More precisely, it creates and returns an LLList that contains the same values at the same positions as the original ArrayList.

public static LLList convert_AtoL(ArrayList vals) {
    LLList converted = new LLList();

    for (int i = vals.length() - 1; i >= 0; i--) {
        Object item = vals.getItem(i);
        converted.addItem(item, 0);
    }

    return converted;
}

Note that the original list is not altered.

1. In order to be as efficient as possible, the method processes the original ArrayList in reverse order: beginning with the last item and working backwards towards the first item. To see why it does so, begin by determining the running time of the above method as a function of the length n of the original list. Don’t forget to take into account the time efficiency of the underlying list operations, getItem() and addItem(). Use big-O notation, and explain your answer briefly.

2. Now let’s consider what the time efficiency would be if the method processed the original list from front to rear, as we usually do:

   public static LLList convert_AtoL_v2(ArrayList vals) {
       LLList converted = new LLList();
   
       for (int i = 0; i < vals.length(); i++) {  // note the changes!
           Object item = vals.getItem(i);
           converted.addItem(item, i);    // note the change!
       }
   
       return converted;
   }
   

   What is the running time of this version of the method as a function of the length n of the original list? Use big-O notation, and explain your answer briefly. How does it compare to the efficiency of the original version of the method?

3. Write a method called convert_LtoA that performs the opposite “conversion”: taking an instance of our LLList class from lecture, and “converting” it into an ArrayList object that contains the same values. More precisely, it should create and return an ArrayList that contains the same values at the same positions as the original LLList.

   Make your new method as efficient as possible. You should assume that this method is client code that does not have direct access to the fields of either object. In addition, it should not modify the original list in any way.

   Important: Your method should not use an additional array or an additional instance of one of our collection classes. Instead, it should limit itself to: the LLList that is passed in, the ArrayList that is being created, and (optionally) one of the iterators associated with our LLList class, as discussed in lecture.

   Note: In the ps7.zip file that you will download for Part II, we have included a file called Problem2.java that contains the original methods listed above and a main method with some preliminary test code. You are welcome to use that file to test the correctness of your convert_LtoA method, although we encourage you to convince yourself of its correctness before you test it in VS Code.

4. What is the running time of your convert_LtoA method? Use big-O notation, and explain your answer briefly.

Problem 3: Working with stacks and queues

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

1. Write a method doubleAllStack(Stack<Object> stack, Object item) that takes a stack and an item, and that doubles – i.e., adds an extra copy – of all occurrences of that item in the stack. After the doubling, the original items should still be in the same order with respect to each other. For example, if you have a stack that contains (from top to bottom) {5, 2, 7, 2, 10}, if you use the method to double all occurrences of 2, the resulting stack should contain (from top to bottom) {5, 2, 2, 7, 2, 2, 10}.

   Important guidelines:

   • Your method may use either another stack or a queue to assist it. It may not use an array, linked list, or other data structure. When choosing between a stack or a queue, choose the one that leads to the more efficient implementation.

   • You should assume that the method does not have access to the internals of the collection objects, and thus you can only interact with them using the methods in the interfaces that we discussed in lecture.

   • Although you aren’t writing this method as part of a class, you should use appropriate Java syntax. The methods should be static and should not return a value.

2. Write a method doubleAllQueue(Queue<Object> queue, Object item) that takes a queue and an item, and that doubles – i.e., adds an extra copy – of all occurrences of that item in the queue. After the doublings, the original items should still be in the same order with respect to each other. For example, if you have a queue that contains (from front to rear) {5, 2, 7, 2, 10} and you use the method to double all occurrences of 2, the resulting queue should contain (from front to rear) {5, 2, 2, 7, 2, 2, 10}. The same guidelines that we specified for doubleAllStack() also apply here.

Problem 4: Binary tree basics

11 points total; individual-only

We will complete the material needed for this problem during the week of April 10.

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 5: Tree traversal puzzles

6 points total; 3 points each part

We will complete the material needed for this problem during the week of April 10.

1. When a binary tree of characters (which is not a binary search tree) is listed in postorder, the result is IKHAFLMBCQ. Inorder traversal gives IAKHQCFLBM. Construct the tree by editing the diagram we have provided in section 5-1 of ps7_partI.

   • Click on the diagram 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 BAFCIDGEHJ. Inorder traversal gives FCAIBGHEJD. Construct the tree by editing the diagram that have provided in section 5-2 of ps7_partI.

Problem 6: Binary search trees

6 points total; 3 points each part; individual-only

We will complete the material needed for this problem during the week of April 10.

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

1. Show the tree as it will appear if 33 is inserted and then 60 is inserted. Show the resulting tree by editing the diagram that we have provided in section 6-1 of ps7_partI.

2. Suppose we have the original tree and that 42 is deleted and then 26 is deleted, using the algorithm from the lecture notes. Show the resulting tree by editing the diagram that we have provided in section 6-2 of ps7_partI.

Submitting your work for Part I

Note: There are separate instructions at the end of Part II that you should use when submitting your work for that part of the assignment.

Submit your ps7_partI.pdf file using these steps:

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

2. Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 112.

3. Click on the name of the assignment (PS 7: Part I) 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.)

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

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

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

Part II

50 points total

Preparing for Part II

Begin by downloading the following zip file: ps7.zip

Unzip this archive, and you should find a folder named ps7, and within it the files you will need for Part II.

Keep all of the files in the ps7 folder, and open that folder in VS Code using the File->Open Folder or File->Open menu option.

Note: VS Code will show an “Unchecked cast” warning for the lines in the ArrayStack and ArrayQueue constructors that create the array for the items field and cast it to be of type T[]. You can safely ignore these warnings.

Problem 7: Rotating the elements in a list

14 points; individual-only

Assume that we want list objects to support the following method:

void rotate(int k)

This method should modify the internals of the list so that the elements are “rotated” k times, where k is an integer between 0 and the length of the list.

Rotating a list involves moving the last item in the list to the front of the list. After k rotations, the k last items in the original list should now be the k first items. For example, if vals represents the following list:

{a, b, c, d, e, f}

the call vals.rotate(4) should make vals represent the list

{c, d, e, f, a, b}

Create two implementations of this method: one as part of the ArrayList class in the ps7 folder, and one as part of the LLList class in that same folder.

Important: For full credit, both methods should:

• have a worst-case time efficiency of O(n), where n is the number of items in the list
• use as little additional memory as possible, and no more than O(n).

In order to do so, your methods will need to manipulate the internals of the list (i.e., the underlying array or linked list) themselves, and they will need to do so as efficiently as possible.

Notes:

• If k is negative or greater than the length of the list, the methods should throw an IllegalArgumentException. If k is 0 or equal to the length of the list, the list should be left unchanged.

• The ArrayList version of the method should not make any calls to the other methods of its class. Rather, it should make the necessary changes to the array on its own.

• The LLList version of the method is allowed to make two calls to the getNode helper method. Other than those two calls, it should not make any other calls to the methods of the class. Rather, it should make any necessary changes to the nodes of the linked list and the fields of the called LLList object on its own.

• Make sure to test your methods. For example:

  String[] letters3 = {"a", "b", "c", "d", "e", "f"};
  ArrayList list3 = new ArrayList(letters3);
  System.out.println(list3);
  list3.rotate(4);
  System.out.println(list3);
  

  should print the following:

  {a, b, c, d, e, f}
  {c, d, e, f, a, b}
  

  You should obtain the same results if you replace ArrayList with LLList in the test code.

Problem 8: Palindrome tester

15 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

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

1. (10 points) 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 ps7 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 ps7 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. (5 points) 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. Print a blank line between tests.

Problem 9: Adding methods to the LinkedTree class

21 points; individual-only

We will complete the material needed for this problem during the week of April 10.

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

1. Write a non-static depth() 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.

   Your 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, if we run the following test code:

   LinkedTree tree = new LinkedTree();
   System.out.println("empty tree: " + tree.depth(13));
   
   int[] keys = {37, 26, 42, 13, 35, 56, 30, 47, 70};
   tree.insertKeys(keys);
   System.out.println("depth of 13: " + tree.depth(13));
   System.out.println("depth of 37: " + tree.depth(37));
   System.out.println("depth of 47: " + tree.depth(47));
   System.out.println("depth of 50: " + tree.depth(50));
   

   we should see:

   empty tree: -1
   depth of 13: 2
   depth of 37: 0
   depth of 47: 3
   depth of 50: -1
   

   To help you visualize the tree, it’s worth noting that we’re using an array of keys that produces the following binary tree:

   

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

   • a private static method called countEvensInTree() that takes a reference to a Node object as its only parameter; it should use recursion to find and return the number of even-valued keys in the binary search tree or subtree whose root node is specified by the parameter. Make sure that your method correctly handles empty trees/subtrees – i.e., cases in which the value of the parameter root is null.

   • a public non-static method called countEvens() that takes no parameters and that returns the number of even-valued keys in the entire tree. This method should serve as a “wrapper” method for countEvensInTree(). 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.

   If we run the following test code:

   LinkedTree tree = new LinkedTree();
   System.out.println("empty tree: " + tree.countEvens());
   
   int[] keys = {4, 1, 3, 6, 5, 2};
   tree.insertKeys(keys);
   System.out.println("tree with keys from 1 to 6: " + tree.countEvens());
   

   we should see:

   empty tree: 0
   tree with keys from 1 to 6: 3
   

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. Your method should assume that the tree is a binary search tree.

   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, if we run the following test code (which again involves building the tree shown above for the depth method):

   LinkedTree tree = new LinkedTree();
   System.out.println("empty tree: " + tree.deleteMax());
   System.out.println();
   
   int[] keys = {37, 26, 42, 13, 35, 56, 30, 47, 70};
   tree.insertKeys(keys);
   tree.levelOrderPrint();
   System.out.println();
   
   System.out.println("first deletion: " + tree.deleteMax());
   tree.levelOrderPrint();
   System.out.println();
   
   System.out.println("second deletion: " + tree.deleteMax());
   tree.levelOrderPrint();
   

   we should see:

   empty tree: -1
   
   37
   26 42
   13 35 56
   30 47 70
   
   first deletion: 70
   37
   26 42
   13 35 56
   30 47
   
   second deletion: 56
   37
   26 42
   13 35 47
   30
   

   Note that first we delete 70, because it is the largest key in the original tree. Next we delete 56, because it is the smallest remaining key. As a result of these deletions, 47 moves up a level in the tree.

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

   • We have given you the beginnings of a test for part 1 that you should complete.

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

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

Submitting your work for Part II

Note: There are separate instructions at the end of Part I that you should use when submitting your work for that part of the assignment.

You should submit only the following files:

• ArrayList.java
• LLList.java
• Palindrome.java
• LinkedTree.java

Make sure that you do not try to submit a .class file or a file with a ~ character at the end of its name.

Here are the steps:

1. Login to Gradescope as needed by clicking the link in the left-hand navigation bar, and then click on the box for CS 112.

2. Click on the name of the assignment (PS 7: Part II) 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.)

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

4. Click the Upload button.

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

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

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

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