Problem Set 6

due by 11:59 p.m. on Tuesday, April 7, 2026

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.

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

2. Select File->Make a copy..., and save the copy to your Google Drive using the name ps6_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 (ps6_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I!

Problem 1: First Practice with references

9 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 "ran".

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 'r'.)

In addition to the list representing "ran", the diagram shows an extra node containing the character 'i', and two reference variables: n, which holds a reference to the third node in the list (the 'n' node); and x, which holds a reference to the 'i' node. The diagram also shows memory addresses of the start of the variables and objects. For example, the 'r' node begins at address 0x360.

1. (6 points) Complete the table that we have provided in ps6_partI, 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.

2. (3 points) Write a Java code fragment that inserts the 'i' node between the 'a' node and the 'n' node, producing a linked list that represents the string "rain". 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.

Problem 2: IntNode

10 points total; individual-only

Suppose that you have a linked list of integers containing nodes that are instances of the following class:

public class IntNode {
    private int val;
    private IntNode next;
}

1. Write a method named printOddsRecur() that takes a reference to the first node in a linked list of IntNode objects and uses recursion to print the odd values in the list (if any) in order, with each value printed on a separate line. If there are no odd values, the method should not do any printing.

2. Write a method named printOddsIter() that uses iteration to perform the same task.

You may assume that the methods that you write are static methods of the IntNode class.

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

12 pts. total; individual-only

The LLList.java source file can be found here: LLList.java

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.

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 ps6_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your ps6_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

50 points total

Getting started

1. If you haven’t already done so, create a folder named ps6 for your work on this assignment. You can find instructions for doing so here.

2. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open your ps6 folder. (Note: You must open the folder; it is not sufficient to simply open the file.)

Problem 5: Rewriting linked-list methods

50 points; individual-only

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. Begin by downloading the StringNode class, storing it in your ps6 folder.

   In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open your ps6 folder. (Note: You must open the folder; it is not sufficient to simply open the file.)

   The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with the name of the downloaded file. Click on the name of the file to open an editor window for it.

1. Rewrite the length() 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 printReverse() method so that it uses iteration. This method is easy to implement using recursion–as we have done in StringNode.java–but it’s more difficult to implement using iteration. Here are two possible iterative approaches, either of which will receive full credit:

   • reverse the linked list before printing it: This approach is the trickier of the two, but we recommend it because it uses less memory, and it will give you more practice with manipulating linked lists. Remember that you may not use the toString() method for this or any other method. In addition, you should not use the print() method. Finally, don’t forget to restore the linked list to its original form!

   • use an array: Create an array of type char that is large enough to hold all of the characters in the string and use it to help you with the problem.

4. Rewrite the removeFirst() 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 insertSorted() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

7. Test your methods thoroughly.

   • There is existing test code in the main() method. Leave that code intact, and use it to test your new versions of the methods.

   • You are also strongly encouraged to add other tests to this method, although doing so is not strictly required.

   • As mentioned in the guidelines at the start of the problem, the provided toString() method means that you can print a StringNode s in order to see the portion of the linked-list string that begins with s.

   • Another useful method for testing is the convert() method, which converts a Java String object into the corresponding linked-list string.

   • You may also find it helpful to download the following file into your ps6 folder: StringNodeOrig.java.

     It contains the original version of the StringNode class, so that you can compare the behavior of the original methods to the behavior of your revised methods.

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 the following file for the PS6 submission portal:

• StringNode.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 6: 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.

Last updated on March 31, 2026.