Problem Set 3

Due by 11:59 p.m. Eastern time on July 21, 2026.
See below for a summary of the policies regarding late submissions.

Preliminaries

Homework is due by 11:59 p.m. Eastern time on the stated due date. If it is submitted more than 10 minutes after that time, it will be considered a full day late. There will be a 10% deduction for submissions that are up to one day late, and a 20% deduction for submissions that are 2 or 3 days late. We will not accept any homework that is more than 3 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.

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 s22 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 Counting multiples in a 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;
}

You may assume that the integers in these nodes are always positive.

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), 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 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. A local events venue wants you to maintain its monthly list of events. The number of events is roughly the same each month. The events will be added in order by date from the beginning of the month to the end, and they will also be displayed in that order.

2. You are maintaining a list of information about runners in a marathon. Each runner is assigned a number between 1 and 3000, and you decide to use that id number as the index of the runner’s record in the list. Once the deadline for signing up for the race has passed, there are very few changes to the list. However, you need to frequently access the runner’s records during the race so that you can add the times at which they pass various mile markers. There is no guarantee about when a given runner will pass a given mile marker, and thus there is no guarantee about the order in which the records will be accessed.

3. You need to keep track of students who register for hackathons that you organize on a regular basis. For a given hackathon, you start with an empty list and add students when they register. To ensure that you have performed the necessary processing of the registrants, you regularly display the list, starting with the most recently added registrant and working backwards towards the least recently added one. The number of registrants varies significantly from one hackathon to another.

Problem 3 Analyzing and improving an algorithm

12 points total

The following method takes an integer factor and an instance of our ArrayList class from lecture that we assume contains integers, and it creates and returns an instance of our LLList class in which each integer from the original list has been multiplied by the specified factor.

public static LLList scale(int factor, ArrayList vals) {
    LLList scaled = new LLList();

    for (int i = 0; i < vals.length(); i++) {
        int val = (Integer)vals.getItem(i);
        scaled.addItem(val*factor, i);
    }

    return scaled;
}

Note that the original list is not altered, and the scaled version of the value at position i in the original list is in position i of the new list.

1. What is the running time of this algorithm 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. Rewrite this method to improve its time efficiency by improving the ways in which the method manipulates one or both of the lists. Your new method should have the same results as the original one, and it should not modify the original list in any way. Make the 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.

   Important: The revised method’s memory usage should be comparable to that of the original method. This means that it should not use an additional array or an additional instance of one of our collection classes. Instead, it should limit itself to the ArrayList that is passed in and the LLList that is being created.

   Note: In the ps3_partII.zip file that you will download for Part II, we have included a file called Problem3.java that contains the original version of the scale method and a main method with some preliminary test code. You are welcome to use that file to test the correctness of your new version of the method, although we encourage you to convince yourself of its correctness before you test it in VSCodium.

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

Problem 4 Working with stacks and queues

8 points; 4 points each part

1. Write a method containsStack(Stack<Object> stack, Object item) that takes a stack and an item, and that determines whether the stack contains at least one occurrence of that item. The method should return true if there is one or more occurrence of the item in the stack, and it should return false otherwise. In addition, the method must restore the contents of the stack, putting the items back in their original order.

   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, other than the array or linked list that is used to store the items in the stack or queue. When choosing between a stack or a queue, choose the one that leads to the more efficient implementation.

   • More generally, you should make your method as efficient as possible.

   • 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 for a static method.

2. Write a method containsQueue(Queue<Object> queue, Object item) that takes a queue and an item, and that determines whether the queue contains at least one occurrence of that item. The method should return true if there is one or more occurrence of the item in the queue, and it should return false otherwise. In addition, the method must restore the contents of the queue, putting the items back in their original order. The same guidelines that we specified for containsStack() 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 this archive, and you should find a folder named ps3_partII, and within it the files you will need for Part II.

Keep all of the files in the ps3_partII folder, and open that folder in VSCodium using the File->Open Folder menu option.

Note: When you compile the code, the compiler 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 charAt() 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 compareAlpha() 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 insertBefore() 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.

Remember: Draw diagrams to help you in your work!

Problem 6 More fun with the StringNode class

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

The guidelines for Problem 5 also apply here.

1. Add a new method with the following header:

   public static StringNode reverseInPlace(StringNode str)
   

   This method should use either recursion or iteration to reverse the string represented by str. It should not create a separate linked list that is the reverse of the original one. Rather, it should reverse the list “in place” – modifying the references in the original nodes so that they go in the reverse direction. For example, consider the following linked list of StringNode objects which represents the string "cat":

   

   After making a call to reverseInPlace in which the first node of this list is passed in as a parameter, the final result should be a list that looks like this:

   

   so that it now represents the string "tac".

   In addition to modifying the next fields of the nodes, your method should return a reference to the new first node of the linked list (the 't' node in the example above).

   If the parameter is null (representing an empty string), the method should return null.

2. Add a new method with the following header:

   public static int lastIndexOf(StringNode str, char ch)
   

   This method must use recursion to find and return the index of the last occurrence of the character ch in the string str, or -1 if ch does not appear in str. For example, if you run this test code:

   StringNode s4 = StringNode.convert("singing");
   System.out.println(StringNode.lastIndexOf(s4, 'n'));
   System.out.println(StringNode.lastIndexOf(s4, 'i'));
   System.out.println(StringNode.lastIndexOf(s4, 'x'));
   

   you should see the following output:

   5
   4
   -1
   

   If str is null (representing an empty string), the method should return -1, since an empty string does not have any characters.

Problem 7 Rotating the elements in a list

18 points

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, and one as part of the LLList class. Both classes can be found in the ps3_partII 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 the 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

12 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 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
• ArrayList.java
• LLList.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 both 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 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 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.