Problem Set 7

due by 11:59 p.m. on Sunday, November 8, 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

40 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: More Practice with references

15 points total; individual-only

A doubly linked list consists of nodes that include two references: one called next to the next node in the linked list, and one called prev to the previous node in the linked list. The first node in such a list has a prev field whose value is null, and the last node has a next field whose value is null.

The top portion of the diagram below shows a doubly linked list of characters that could be used to represent the string "cat".

Each of the nodes shown is an instance of the following class:

public class DNode {
    private char ch;
    private DNode next;
    private DNode prev;
}

(In the diagram, we have labeled the individual fields of the DNode object that contains the character 'c'.)

In addition to the list representing "cat", the diagram shows an extra node containing the character 'h', and two reference variables: y, which holds a reference to the second node in the list (the 'a' node); and x, which holds a reference to the 'h' node. The diagram also shows memory addresses of the start of the variables and objects. For example, the 'c' node begins at address 0x400.

1. (6 points) Complete the table below, filling in the address and value of each expression from the left-hand column.

   You should assume the following:

   • the address of the ch field of a DNode is the same as the address of the DNode itself

   • the address of the next field of a DNode is 2 more than the address of the DNode itself

   • the address of the prev field of a DNode is 6 more than the address of the DNode itself, which means that it is also 4 more than the address of the next field.

   You should fill in the following table in your ps7_partI.pdf file:

   expression         address       value
   ------------------ ------------- -----------
   x
   x.ch
   y.prev
   y.next.prev
   y.prev.next
   y.prev.next.next
   

2. (4 points) Write a Java code fragment that inserts the 'h' node between the 'c' node and the 'a' node, producing a linked list that represents the string "chat".

   Your code fragment should consist of a series of assignment statements. You should not make any method calls, and you should not use any variables other than the ones provided in the diagram. You may assume that your code is part of the main method in the DNode class, and thus it has direct access to the private fields of the DNode objects.

   Make sure that the resulting doubly linked list has correct values for the next and prev fields in all nodes.

3. (5 points) Suppose you have a doubly linked list of DNode objects in which the prev references have the correct values but the next references have not yet been initialized.

   Write a static method called initNexts() that:

   • takes one parameter, a reference to the last node of the linked list

   • traverses the linked list from back to front, filling in the next references

   • returns a reference to the first node of the linked list.

   You may assume that there is at least one node in the list.

   You do not need to code up this method as part of a class; simply include it in the same file as your other problems for this question. You may assume that the method is part of the DNode class.

Problem 2: Choosing an appropriate implementation

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

In lecture we will look 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. 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.

To fully answer this question, you should wait until we cover these two implementations, however, the question is asking you to think about the difference between using an array or a linked list as an underlying datastructure.

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 3: Improving the efficiency of an algorithm

13 pts. total; individual-only

Consider the following method which takes in an instance of the LLList class This method creates and returns a new list that is a reverse of the original list:

public static LLList reverse(LLList list) {
    LLList rev = new LLList();

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


    return rev;
}

Note that the original list is not altered.

1. What is the worst-case running time of this algorithm? 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.

The following two tasks have been moved to the next problem set. You are not responsible for answering them as part of ps7.

2. Rewrite this method to improve its time efficiency by improving the ways in which the method manipulates the LLList objects. Your new method should not modify the original list in any way. Make the new method as efficient as possible. You should assume that this method is not part of the LLList class, and therefore it doesn’t have direct access to the fields of the LLList objects. In addition, you may assume that the LLList objects include support for the list-iterator functionality discussed in lecture.

3. What is the worst-case running time of the improved algorithm? Use big-O notation, and explain your answer briefly.

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

60 points total

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 Problem 5 of Part II. Make sure that you keep all of the files in the same folder.

Important: When you compile the code in this folder, you may see one or more warnings labeled “unchecked cast”. You can safely ignore them.

Problem 4: Rewriting linked-list methods

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

In lecture, we’ve been looking at linked lists of characters that are composed of objects from the StringNode class. The class includes a variety of methods for manipulating these linked lists, and many of these methods provide functionality that is comparable to the methods found in Java String objects.

Some of the existing StringNode methods use recursion, while others use iteration (i.e., a loop!). In this problem, you will rewrite several of the methods so that they use the alternative approach.

0. Before you get started, we recommend that you put a copy of the original StringNode class in a different folder, so that you can compare the behavior of the original methods to the behavior of your revised methods.

1. Rewrite the indexOf() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

2. Rewrite the toUpperCase() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

3. Rewrite the isPrefix() method so that it uses iteration. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

4. Rewrite the insertAfter() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

5. Rewrite the copy() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

6. Rewrite the removeAllSpaces() method so that it uses iteration. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

Remember: Drawing diagrams will be a great help as you design your revised methods!

Problem 5: Removing all occurrences from a list

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

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

 boolean removeAll(Object item)

This method takes an item, and it should removes all occurrences of that item from the list. If one or more occurrences of the item are removed, the method should return true. If there were no occurrences of the item to begin with, it should return false.

Create two implementations of this method: one as part of the ArrayList class, and one as part of the LLList class. Both classes can be found in the ps7 folder.

Important: For full credit, both methods should:

• run in O(n) time, where n is the number of items in the list
• use no more than a constant (O(1)) amount of additional memory.

In addition, you should make sure that your ArrayList

version of the method doesn’t leave any extraneous references to objects in the items array. For example, let’s say that you have 9 items in the ArrayList. If a call to removeAll() removes 3 of them, you should end up with an array in which the first 6 elements hold references to actual items, and all of the remaining elements are null.

To facilitate testing, we have added a constructor to both classes that takes an array of type Object containing the initial contents of the list. Given these constructors, test your methods. For example:

String[] letters = {"a", "b", "c", "a", "c", "d", "e", "a"};
ArrayList list1 = new ArrayList(letters);
System.out.println(list1);
System.out.println(list1.removeAll("a"));
System.out.println(list1);
System.out.println(list1.removeAll("c"));
System.out.println(list1);
System.out.println(list1.removeAll("x"));
System.out.println(list1);

would output:

{a, b, c, a, c, d, e, a}
true
{b, c, c, d, e}
true
{b, d, e}
false
{b, d, e}

And,

LLList list2 = new LLList(letters);
System.out.println(list2);
System.out.println(list2.removeAll("a"));
System.out.println(list2);
System.out.println(list2.removeAll("x"));

would output:

{a, b, c, a, c, d, e, a}
true
{b, c, c, d, e}
false

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:

• StringNode.java
• your updated version of ArrayList.java
• your updated version of 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 5: 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.