Problem Set 7

Due by 11:59 p.m. Eastern time on Tuesday, April 22, 2025

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: ps7_partI

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

3. Add your work to this file.

4. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file on your machine. 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 implementation

9 pts. total; 3 pts. each part; individual-only

In lecture we looked at 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. You 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 store information about the gardening tools that you sell in your online store. To do so, you maintain a list of product records, each of which contains information about a single type of product, including how many copies of it you have in stock. You don’t tend to change the types of tools that you sell, and thus items are seldom added or removed from the list. However, you need to update a product’s record whenever your inventory of that product changes (e.g., because someone purchases one!). A product’s position in the list is also its product ID, and therefore updating a record involves using the product ID to get the corresponding record and modifying its contents.

2. You need to maintain a list of tweets that are made by government officials in the current week. The number of tweets can vary widely from week to week in a way that is hard to predict. You start with an empty list at the start of the week, and as tweets are made you add them to the list. You need to frequently display the tweets in reverse chronological order – from most recent to least recent.

3. You are responsible for maintaining a monthly list of events for an online arts calendar. The number of events is fairly consistent from month to month. Events are added to the list in chronological order, and you need to display them in that same order.

Problem 2: Improving the efficiency of an algorithm

12 pts. total; individual-only

The LLList.java source file can be found in the following zip folder: ps7.zip

Consider the following method, which takes two unsorted lists, list1 and list2 – both instances of class LLList – and creates a third list containing the intersection of list1 and list2:

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();

    for (int i = 0; i < list1.length(); i++) {
        Object item1 = list1.getItem(i);
        for (int j = 0; j < list2.length(); j++) {
            Object item2 = list2.getItem(j);
            if (item2.equals(item1)) {
                inters.addItem(item2, inters.length());
                break;   // move onto the next item from list1
            }
        }
    }

    return inters;
}

The lists are unsorted, so we take a nested-loop approach in which each item in list1 is compared to the items in list2; if a match is found in list2, the item is added to the intersection and we break out of the inner loop. (Note that this method will include duplicate values in the intersection when list1 itself has duplicates; doing so is acceptable for the purposes of this problem.)

1. (3 points) What is the worst-case running time of this algorithm as a function of the length m of list1 and the length n of list2? 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. (6 points) Rewrite this method to improve its time efficiency. Your new method should not modify the existing lists in any way, and it should use no more than a constant (O(1)) amount of additional memory. In othee words, your solution should not use additional lists other than the lists used in the solution above. Make the new method as efficient time-wise as possible, given the constraints on memory usage. You should assume this method is not part of the LLList class, and therefore it doesn’t have direct access to the private LLList members.

3. (3 points) What is the worst-case running time of the improved algorithm? 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: Using a queue to search a stack

8 points; individual-only

Suppose that you have a stack S, and you need to determine if it contains a given item I. Because you are limited to the operations that a stack supports, you can’t just iterate over the items in S to look for I. However, you can remove items from S one at a time using the pop() method and later return them using the push() method.

Use either pseudocode or Java code to define an algorithm that uses an initially empty queue Q to search for an item I in the stack S. Your algorithm should return true if the item is found and false otherwise. In addition, your algorithm must restore the contents of S, putting the items back in their original order.

You algorithm may use S, Q, and a constant number of additional variables. It may not use an array, linked list, or any other data structure. You may assume that the stack S supports the operations in our Stack<T> interface, that the queue Q supports the operations in our Queue<T> interface, and that both S and Q are able to store objects of any type.

Note: This approach to the problem of searching a stack is not the most efficient way to solve the problem! However, taking this approach will allow you to practice using both types of data structures to solve a problem.

Problem 5: Binary tree basics

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

6 points total; 3 points each part

1. When a binary tree of characters (which is not a binary search tree) is listed in inorder, the result is SKBPCJRDME. Preorder traversal gives PSBKRJCMDE. Construct the tree by editing the diagram we have provided in section 4-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 postorder, the result is IBGOZKHNSL. Preorder gives LOGIBSHKZN. Construct the tree by editing the diagram that have provided in section 6-2 of ps7_partI. (There is more than one possible answer in this case.)

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 on your machine.

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 9: Implementing the Bag ADT using a linked list

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

Earlier in the course, we worked with the ArrayBag class. This class can be seen as an implementation of the Bag abstract data type, which we can specify in Java using the following interface:

public interface Bag {
    boolean add(Object item);
    boolean remove(Object item);
    boolean contains(Object item);
    int numItems();
    Object grab();
    Object[] toArray();
}

In the ps7 folder, we have included:

• the Bag interface (Bag.java)
• a version of the ArrayBag class that includes an implements clause in its header to specify that it implements this interface.

In a file named LLBag.java, write a class called LLBag that implements the Bag interface using a linked list instead of an array. You may use a linked list with or without a dummy head node.

In designing your implementation, you may find it helpful to compare the LLList class, our linked-list implementation of the List ADT, to the ArrayList class, our array-based implementation of that same ADT. In the same way that LLList uses a linked list instead of an array to implement a list, your LLBag class should use a linked list instead of an array to implement a bag.

Notes:

• Make sure that your class explicitly indicates that it implements the Bag interface. To allow your new class to compile, you will need to put it in the ps7 folder with Bag.java.

• Like the LLList class, your LLBag class should use a private inner class called Node for the nodes in the linked list.

• In addition to the methods in the Bag interface, your LLBag class should also have a toString() method that overrides the default toString() method inherited from the Object class. Consult the ArrayBag toString() method to see what the string returned by this method should look like.

• One of the benefits of using a linked list is that there is no need to specify a maximum size—the bag can effectively grow without limit. Therefore, you will not need to provide a constructor that specifies a maximum size, and your add() method can always return true.

• Because the order of the items in a bag doesn’t matter, you can add items to either end of the linked list; however, make sure that your method adds items in O(1) time.

• In general, you should make your methods as efficient as possible. For example, when implementing the remove() method, you should make sure that you don’t traverse the list more than once.

• Copy over the main() method from the ArrayBag class, and make whatever modifications are necessary to allow it to test your LLBag class.

  Important: If you compare the results that you obtain from testing the two classes, you may see that the items are not in the same order in both sets of tests. That is to be expected, and it’s not a problem because items in a bag do not have a position!

Problem 10: Palindrome tester

15 points total; individual only

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 11: Improving the efficiency of our LLList class

15 points; individual-only

If you haven’t already done so, complete the steps above to prepare for this and the remaining problems in Part II.

In our LLList class from lecture, the worst case for the addItem method occurs when adding an item to the end of the list. addItem is O(n) in that case because we need to walk down the entire linked list before we can add the new item.

As discussed in lecture, we can optimize the case of adding an item to the end of the list if we add an extra field to LLList objects that stores a reference to the last node in the linked list. Here is an example of what this modified version of LLList would look like:

Because the new field – which we have called last in the diagram above – holds a reference to the last node, it can used to avoid the need to walk down the linked list to get to the last node, and thus we can add an item to the end of the list in O(1) steps.

In the version of LLList provided in the ps7 folder, we have included a field called last in the fields of the LList class, but that field is not yet being used or fully maintained by the methods of the class.

Your job is to add the code needed to maintain this field, and to use it to improve the efficiency of the class.

Here are the steps that you should take:

1. Revise the second LLList constructor – the one that takes an array of objects – so that the last field is assigned a reference to the last node in the newly constructed linked list. For full credit, the code that you add to assign a value to this field should only require O(1) steps.

   To facilitate testing, we have added a method called getLastItem that can be used to obtain the item in the node to which the last field refers. For example, after you make the necessary changes to the second constructor, the following code:

   String[] letters1 = {"a", "b", "c"};
   LLList list1 = new LLList(letters1);
   System.out.println(list1);
   System.out.println(list1.getLastItem());
   

   should print:

   {a, b, c}
   c
   

2. Revise the getNode helper method so that it takes advantage of the last field in cases in which it needs to get the last node in the linked list. In such cases, getNode should not need to walk down the linked list.

3. Revise the addItem and removeItem methods so that each of them:

   • updates the value of the last field when the last node in the linked list changes; for full credit, the code that you add to update the value of this field should only require O(1) steps

   • takes advantage of the last field when doing so would improve the efficiency of the method.

   After you have made the necessary changes:

   String[] letters2 = {"a", "b", "c", "d", "e"};
   LLList list2 = new LLList(letters2);
   
   // Add two items to the end of the list.
   list2.addItem("f", 5);
   list2.addItem("g", 6);
   System.out.println(list2.getLastItem());
   
   // Remove three items from the end of the list.
   list2.removeItem(6);
   list2.removeItem(5);
   list2.removeItem(4);
   System.out.println(list2.getLastItem());
   

   should print the following:

   g
   d
   

Notes:

• Take advantage of the fact that addItem and removeItem each call getNode. This should allow you to reduce the amount of code that you need to add.

  For example, consider the getItem method. Because this method uses getNode to do most of the necessary work, we don’t need to modify getItem at all in order to optimize the case of getting the last item in the list. Rather, that case should already be optimized by the changes that you make to getNode.

• In an empty list, the last field should refer to the dummy head node. We have included code that initializes the field accordingly in the first LLList constructor. The code that you add should maintain this relationship between last and the dummy head node in any empty list.

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:

• LLBag.java
• Palindrome.java
• LLList.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.