Problem Set 3 FAQ

Part I

1. For problem 3, I’m having trouble determining the time efficiencies. Do you have any suggestions?

   One way to do this is to make a table for each algorithm that records the approximate number of operations performed by each of the two methods calls (getItem and addItem) for each value of the loop variable i:

   i       # nodes accessed by getItem   # nodes accessed by addItem
   -----   ---------------------------   ---------------------------
   n - 1
   n - 2
   ...
   

   You won’t need to fill the table in entirely in order to see a pattern emerge for the total number of nodes accessed during a given iteration of the loop. Then you can use this pattern to determine an expression for the overall number of nodes accessed by the algorithm, and derive a big-O expression from it.

2. For problem 3, part 2, I’m having trouble thinking of ways to improve the efficiency. Do you have any suggestions?

   In lecture, we covered an example in which we improved the efficiency of a method like reverse() that is a client of the LLList class. One way to improve the efficiency of reverse() is to do something similar to what we did in that example.

   In addition to the technique that we used in lecture, it may also be possible to take other steps to improve the efficiency of the reverse() method.

Problems 5 and 6

1. In problems 5.1, 5.3, and 5.5, we have to write iterative versions of existing recursive methods of the StringNode class. Can you give us any general tips on converting recursive methods into iterative methods?

   In general, when writing iterative versions of these methods, a good starting point is the template for iterative traversal of a linked list given in lecture:

   StringNode trav = __________;   // add expression for first node in list
   while (trav != null) {
       // do something here
       trav = trav.next;           // advance to next node
   }
   

   Then decide what needs to be done inside the loop, and what (if any) special cases need to be handled outside the loop. Special cases that often need to be handled outside the main loop include an empty list, and a list with only one node; however, there are certainly instances where either or both of these cases can be handled within the loop itself.

   Make sure your methods handle these boundary cases of an empty list and a list with only one node correctly! It’s very easy to write a method that works fine with a list with at least two nodes, but fails with a null pointer exception or otherwise behaves incorrectly with smaller lists.

   You also need to think carefully about what local variables your iterative method will need, and how these locals should be initialized. For example, is a single “trav” reference sufficient, or do you need to use a trailing reference as well?

   See the numOccurrences() and read() examples from the section notes for two examples of a recursive to iterative conversion.

2. In problems 5 and 6, are we allowed to change the method headers in any way?

   No. You must use the method headers we have given you.

3. When writing recursive methods in problems 5 and 6, can we call a helper method to perform the recursion?

   No, the methods themselves must be recursive – i.e., they must call themselves. You should not need to write additional helper methods for these methods.

4. I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for problems 5 and 6. Do you have any hints on how to do this?

   One thing that can help is to consider what should happen for one or more concrete cases.

   For example, let’s say that you needed to write a recursive numOccur method for the StringNode class. As with many recursive methods that operate on linked lists, this method should make recursive calls on ever shorter linked lists – i.e., on the rest of the list. For example, let’s say that we wanted to do numOccur([linked list for "recur"], 'r')

   This would lead to the following sequence of method calls:

   numOccur([linked list for "recur"], 'r')
       numOccur([linked list for "ecur"], 'r')
           numOccur([linked list for "cur"], 'r')
               numOccur([linked list for "ur"], 'r')
                   numOccur([linked list for "r"], 'r')
                       numOccur(null, 'r')
   

   where [linked list for ...] represents a reference to the first node in the linked list for the specified string.

   Then, once you have the sequence of method calls, think about what each of these separate method calls should return, treating them as if they were independent of each other. For example, what should numOccur([linked list for "cur"], 'r') return – i.e., how many times does 'r' occur in "cur"? Based on these return values, you should be able to figure out how a given invocation of the method should use the return value from the recursive call to form its own return value.

5. One of my recursive methods for problems 5 and 6 is not working correctly. Do you have any suggestions?

   Try tracing through some concrete examples of cases in which your method is not returning the correct value. You might also want to try adding some temporary printlns to see if that helps you to diagnose the problem. In particular, you could print what the method will return before it actually returns it. That will allow you to see when the wrong value is being returned.

   In addition, if your method returns a value, make sure that you aren’t throwing away the return value of the recursive call. For example, consider this incorrect version of the recursive numOccur method from the provided StringNode class:

   public static int numOccur(StringNode str, char ch) {
       if (str == null) {
           return 0;
       }
   
       int numOcc = 0;
       numOccur(str.next, ch);
   
       if (str.ch == ch) {
           return 1 + numOcc;
       } else {
           return numOcc;
       }
   }
   

   This version of the method makes the correct recursive call – passing in a reference to the first node in the rest of the linked list – but it throws away the value that is returned.

   To avoid losing the return value of the recursive call, we can do one of two things:

   1. assign it to a variable, and then do something with that variable
   2. make the recursive call part of a return statement, if doing so makes sense. It may not always make sense – especially if the value that the current method call should return depends on the value that was returned by the recursive call.

6. I tried using Java Tutor to step through one of my StringNode methods, but it says that the code has too many steps to execute. Do you have any suggestions?

   Yes. You should use a stripped-down version of the StringNode class in which you take out almost all of the methods and just leave only the following:

   • the fields
   • the constructor
   • the method you are trying to trace
   • a main method in which you manually build a simple linked list and then call your method to process it.

   Note that manually building the linked list is better than using the convert method because convert requires a lot of steps. Here’s a simple example in which we build a linked list for the string "cat":

   StringNode s1 = new StringNode('t', null);
   s1 = new StringNode('a', s1);
   s1 = new StringNode('c', s1);
   

   Note that we start with the node for the last character and work backwards towards the node for the first character, so that each node’s next field can be made to point to the node that comes after it.

   You can find an example of using this approach to test the original version of the toUpperCase method here.

   Here’s how to use Java Tutor:

   1. Go to Java Tutor.

   2. Remove the provided code and replace it with your stripped-down version of StringNode – something like our example.

   3. Click the Visualize Execution button below the code, which will eventually bring you to a separate page.

   4. Use the Next button below the code to trace through the program. As you do so, you should see the stack frames and the StringNode objects displayed on the right-hand side of the window. (Note: Stack frames labeled <init> are for calls to the StringNode constructor.)

7. I’m stuck on the iterative version of the copy method. Any suggestions?

   A good model for this method is the convert method found in the original StringNode class.

   convert takes a Java String object and uses iteration to build a linked list containing the characters from that string. Your iterative copy method will also build a new linked list, but the characters will come from an existing linked list instead of from a Java String.

   The overall approach needed to build the new linked list will be very similar to the approach taken by convert. In particular, it will be helpful to maintain a number of different references to nodes in the new linked list (firstNode, prevNode and nextNode), just as convert does.

   Note that convert is able to use a for loop because it can easily and efficiently get the length of the Java string s by using s.length(), and thus it can know exactly how many repetitions are needed. Your copy method should use a while loop instead, because you don’t know how many nodes are in the original linked list, and it doesn’t make sense to call the StringNode.length() method since it would need to make an extra traversal of the linked list.

8. Do you have any hints for the nthIndexOf method (problem 6, part 2)?

   The first hint is to realize that the value of the first parameter (n) will sometimes need to change when you make the recursive call – but not always! This means that you will probably need more than one recursive call: one for when the first parameter is modified, and one for when it is not modified.

   The second hint is that your code will need to behave differently when an nth occurrence of the character is not present in the string than it will when an nth occurrence is present. As a result, it probably makes sense to store the return values of the recursive calls in a variable, so that you can then determine which value the current call of the method should return.

Problem 7

1. In Problem 7, do we need to use an iterator?

   No, and we don’t recommend using one.

   Iterators can be useful when you are writing code that is a client of a collection class – i.e., a method or program that is outside the class and that uses an instance of the class in some way.

   In this problem, you aren’t writing client code. Rather, you are adding non-static methods to the collection classes themselves. Because these new methods are inside their respective classes, they have access to the private fields of their class, and thus an iterator is not needed.

   Rather, when implementing the ArrayList version of removeAll(), you should write code that directly manipulates the underlying array of items. When implementing the LLList version of removeAll(), you should write code that directly manipulates the underlying linked list of items.

2. In Problem 7, can our removeAll() methods call the existing non-static methods (e.g., getItem())?

   In theory, yes. However, for full credit, you will need to make sure that your use of these other methods still allows your removeAll() methods to execute in linear (i.e., O(n)) time.

3. I haven’t been able to figure out how to make the ArrayList version of removeAll() have a runtime of O(n). Any suggestions?

   This is indeed a tricky problem. Try drawing a concrete array on paper that includes multiple occurrences of a given value v, and think about how you could efficiently reorder the elements so that all occurrences of v are removed. In order to do so in linear time, a given element of the array should move at most once or twice.

4. I’m having trouble knowing if my implementations of removeAll() have a linear runtime (O(n)). Do you have any general guidelines?

   In order for the ArrayList version to run in linear time, each element of the array should move at most a fixed number of times (e.g., at most once or at most twice) – regardless of how many items are in the list. For example, even if the list has 1000 items, each item should move at most once or twice.

   In order for the LLList version to run in linear time, your code should traverse (i.e., walk down) the list at most once or twice – regardless of how many items are in the list.

Problem 8

1. How can I know that a given character is a letter of the alphabet?

   Because char values are essentially integers, you can compare them just as you would compare integers. This means that you can use a condition that looks like this:

   ch >= 'a' and ch <= 'z'
   

Last updated on October 14, 2025.