Problem Set 3 FAQ

Part I

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:

One way to do this is to make a table that records the approximate number of items/nodes processed by each of the two methods calls (getItem and addItem) for each value of the loop variable i:
```
i    # processed by getItem   # processed by addItem
--   ----------------------   ----------------------
0
1
2
...
```
You won’t need to fill the table in entirely in order to see a pattern emerge that you can use to determine an approximate expression for the total number of elements/nodes processed by the algorithm, and to derive a big-O expression from it.

Problems 5 and 6

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

Problem 7

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 rotate(), you should write code that directly manipulates the underlying array of items. When implementing the LLList version of rotate(), you should write code that directly manipulates the underlying linked list of items.
I’m having trouble knowing if my implementations of rotate() 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

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'
```