Problem Set 3

Due before the start of lecture on March 31, 2026.
See below for a summary of the policies regarding late submissions.

Preliminaries

Homework is due prior to the start of lecture. If it is submitted more than 10 minutes after the start of lecture, it will be considered a full day late. There will be a 10% deduction for late submissions that are made by 11:59 p.m. on the Sunday after the deadline, and a 20% deduction for submissions that are made after that Sunday and before the start of the next lecture. We will not accept any homework that is more than 7 days late. Plan your time carefully, and don’t wait until the last minute to begin an assignment. Starting early will give you ample time to ask questions and obtain assistance.

Revised: Because PS 3 overlapped the midterm, we are waiving the usual late penalties for submissions made by 11:59 p.m. on the Sunday after the deadline, and we are reducing the usual 20% late penalty to 10%. If you submit during the usual 10% late window, Gradescope will still mark your submission as late, but we will not apply a late penalty.

In your work on this assignment, make sure to abide by our policies on academic conduct.

If you have questions while working on this assignment, please come to office hours, post them on Ed Discussion, or email cscie22-staff@lists.fas.harvard.edu

Part I

40 points total

Creating the necessary folder

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

Creating the necessary file

The problems from Part I will all 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 ps3_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 on your machine. The resulting PDF file (ps3_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Modifying a linked list of integers

8 points total; 4 points each part

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 doubleIter(first, n) that takes a reference first to the first node in a linked list of IntNode objects and an integer n, and that uses iteration to find and double all occurrences of the value n (if any) in the list. For example, if first is a reference to the first node in a linked list representing the list {5, 2, 7, 2, 10}, after calling doubleIter(first, 2), the list should be {5, 4, 7, 4, 10}.

2. Write a method named doubleRecur(first, n) that uses recursion to perform the same task.

You do not need to code up these methods (or any method from Part I) as part of a class. Simply put the methods in your ps3_partI file. You may assume that the methods you write are static methods of the IntNode class.

Problem 2: Choosing an appropriate list implementation

12 points total; 4 points each part

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 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: Analyzing and improving an algorithm

12 points total

Consider the following method, which is a new constructor for the LLList class that takes a reference to an ArrayList as its only parameter and constructs an LLList object that represents the same list as the ArrayList – with same items in the same positions in the list.

public LLList(ArrayList aList) {
    // initialize an empty list
    this.head = new Node(null, null);     // dummy head node
    this.length = 0;

    // add the items from aList to this list
    for (int i = 0; i < aList.length(); i++) {
        Object item = aList.getItem(i);
        this.addItem(item, i);
    }
}

1. What is the running time of this constructor as a function of the length n of the 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. Rewrite this constructor to improve its time efficiency by improving the ways in which the method manipulates the ArrayList and LLList objects. Your new method should not modify the original ArrayList in any way. Make the new method as efficient as possible.

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

Problem 4: Working with stacks and queues

8 points; 4 points each part

We will cover the material needed for this problem in lecture on March 11.

1. Write a method reverseStack(Stack<Object> stack) that takes a stack and reverses its contents. For example, if you have a stack that contains (from top to bottom) {5, 2, 7, 3, 10}, after using the method, the resulting stack should contain (from top to bottom) {10, 3, 7, 2, 5}.

   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 reverseQueue(Queue<Object> queue) that takes a queue and reverses its contents. For example, if you have a queue that contains (from front to rear) {5, 2, 7, 3, 10}, after using the method, the resulting queue should contain (from front to rear) {10, 3, 7, 2, 5}. The same guidelines that we specified for reverseStack() also apply here.

Submitting your work for Part I

Submit your ps3_partI.pdf file by taking the following steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->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 problems 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-70 points total

Preparing for Part II

Begin by downloading the following zip file: ps3_partII.zip

Unzip/extract the contents of the file.

Depending on your system, after extracting the contents you will either have:

• a folder named ps3_partII that contains all of the files that you need for Part II

• an outer folder called ps3_partII that contains an inner folder named ps3_partII that contains all of the files that you need.

Take the ps3_partII folder that actually contains the necessary files and drag it into your ps3 folder so that you can easily find and open it from within VS Code.

Keep all of the files in that ps3_partII folder, and open that folder in VS Code using the File->Open Folder or File->Open menu option. (Note: You must open the folder; it is not sufficient to simply open one of the Java files in the folder.)

The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with a list of all of its contents.

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 5: Rewriting linked-list methods

30 points

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

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

Remember: Draw diagrams to help you in your work!

Problem 6: More fun with StringNodes

10 points; required of grad-credit students; “partial” extra credit for others

The guidelines for Problem 5 also apply here.

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

2. Add a new method with the following header:

   public static StringNode replace(StringNode str, char oldChar, char newChar)

   It must use recursion to create and return a new linked-list string in which all occurrences of the character oldChar in the string represented by str are replaced by the character newChar.

   The method must be fully recursive, and it must not change the original linked list. For example, if you run this test code:

   StringNode s1 = StringNode.convert("banana");
   StringNode s2 = StringNode.replace(s1, 'a', 'o');
   System.out.println(s2);
   System.out.println(s1);   // original should be unchanged
   

   you should see the following output:

   bonono
   banana
   

Problem 7: Implementing a bag using a linked list

18 points

Earlier in the course, we worked with the ArrayBag class.

In a file named LLBag.java, write a class called LLBag that has the same basic functionality as an ArrayBag, but that uses a linked list instead of an array to store the items. 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:

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

• Unless stated otherwise in the notes below, your LLBag class should have its own version of all of the methods from our original ArrayBag class, which we have included in the ps3_partII folder.

• 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, your LLBag class:

  • will only need one constructor, because you will not need a constructor that specifies a maximum size.

  • will not need the DEFAULT_MAX_SIZE constant

  • will have an add() method that always returns true.

• One other difference from ArrayBag is that the containsAll method in your LLBag class should take an LLBag object as its parameter.

• Because the order of the items in a bag doesn’t matter, your add() method 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 8: Palindrome tester

12 points

We will cover the material needed for this problem in lecture on March 11.

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 Problem8.java that we’ve included in the ps3_partII folder, implement the static method called isPal() whose header we have provided. This method should take a String object as a parameter and determine 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 this problem could be solved 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 ps3_partII 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.

  • You may not use the equals() method from the String class to compare two strings. Rather, you should only compare individual characters (i.e., individual values of type char) using the == operator.

  • More generally, 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.

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

Submitting your work for Part II

You should submit only the following files:

• StringNode.java
• LLBag.java
• Problem8.java

You do not need to submit any of the other files.

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 all three 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 file. 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 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 you see the code that you want us to grade.

Last updated on March 14, 2026.