Problem Set 5 FAQ

Problem 3
Problem 4
Problem 5
Problem 6

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

Problem 3

In Problem 3.3, does the linked list have a dummy head node?

No. These linked lists are comparable to the StringNode linked lists. There is no dummy head node, and there is no object that represents the list as a whole.

Problem 4

In Problems 4.1-4.3, how many big-O expressions do we need, and what should they look like?

All of your big-O expressions should be functions of t, the number of terms in the polynomial, or m, the maximum exponent in the polynomial, or both.

For 4.1, you need two big-O expressions: one for each implementation.

For 4.2 and 4.3, you need to consider six separate cases:
- the best, average, and worst cases for the array implementation
- the best, average, and worst cases for the linked-list implementation.
Make sure to explain each answer briefly.
In Problem 4.3, can you clarify what you mean by evaluating a polynomial?

Evaluating a polynomial involves determining its value for a particular value of x. For example, when we evaluate 6 + 5x + 3x⁵ for x = 2, we get:

6 + 5·2 + 3·2⁵
= 6 + 10 + 3·32
= 6 + 10 + 96
= 112
In Problem 4.3, I’m confused about how to determine the efficiency. Do you have any suggestions?

For each case (best, average, and worst) of each implementation, you should start by determining separate big-O expressions for two key components in the process of the evaluating the polynomial:
- The steps involved in traversing the data structure used for the polynomial. (Note that this big-O expression will also take care of any single-step operations that are performed for each term – e.g., adding the value of a term to the sum – and therefore you won’t need a separate big-O expresion for those operations.)
- The steps involved in evaluating the powers. As the problem indicates, you should assume that both implementations use a helper method that takes O(n) steps to compute x to the nth power. In cases in which more than one power is computed, you will need to determine a big-O expression that combines the steps required for each individual power.
Then, once you have a big-O expression for each of these key components, you should combine them into a single big-O expression for the case/implementation in question.

Problem 5

For Problem 5, you mention that we should use a merge-based approach. Does this mean that we should be dividing up the arrays and then merging them somehow, as in mergesort?

Your approach should be based on the merge() helper method used by mergesort, not on mergesort itself. The merge() method uses indices to walk down the arrays and merge them; it doesn’t do any dividing up of the arrays. Your intersect method should also use indices to walk down the arrays, but it should form the intersection, rather than the merge.

Problem 6

In Problems 6.1, 6.3, and 6.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.

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?
I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for Problem 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 the recursiveindexOf method given in 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 doindexOf([linked list for "recurse"], 's')

This would lead to the following sequence of method calls:
```
indexOf([linked list for "recurse"], 's')
    indexOf([linked list for "ecurse"], 's')
        indexOf([linked list for "curse"], 's')
            indexOf([linked list for "urse"], 's')
                indexOf([linked list for "rse"], 's')
                    indexOf([linked list for "se"], 's')
```
where [linked list for ...] represents a reference to the first node in the linked list for the specified string. Note that we stop the recursion when the first node contains the character for which we are searching.

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 indexOf([linked list for "rse"], 's') return – i.e., what is the index of the first occurrence of 's' in "rse"? 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 Problem 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 a recursive method that copies a linked-list string:
```
public static StringNode copy(StringNode str) {
    if (str == null) {
        return 0;
    }

    StringNode copyFirst = new StringNode(str.ch, null);

    // recursive call -- the return value is thrown away
    copy(str.next);

    return copyFirst;
}
```
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.