Problem Set 6 FAQ

Problem 1
Problem 2
Problem 3
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 1

For Problem 1, I’m having trouble distinguishing between the best case and the worst case. Can you help?

The method in Problem 1 uses a nested loop. The outer loop performs a number of repetitions that is based solely on the length of the array that is passed in – and not on its contents (i.e., the values that are found in the array).

When it comes to the inner loop, however, the number of repetitions that it performs does depend on the contents of the array – because executing the break statement that is found in the inner loop will end the inner loop early. As a result, the time efficiency of the algorithm will also depends on the contents of the array – and that’s why we end up with a best case and a worst case.

Given the statements that are found in the body of the inner loop, what characteristics would the contents of the array need to have to cause the inner loop to perform the fewest number of repetitions? What characteristics would the contents of the array need to have to cause the inner loop to perform the largest number of repetitions?
For Problem 1-2, I’m having trouble deriving an exact formula. How can I get started?

When analyzing the efficiency of selection sort, we came up with an exact formula for the number of comparisons that it performs. You will need to perform a similar analysis here.

Problem 2

For Problem 2, I’m having trouble coming up with a more efficient implementation. How can I get started?

Start by considering one or more concrete cases on paper.

For example, consider the following array:
```
{10, 6, 2, 5, 6, 6, 8, 10, 5}
```
The hint in the problem indicates that your new implementation should start by calling mergeSort to sort the array. Doing so would produce the following array:
```
{2, 5, 5, 6, 6, 6, 8, 10, 10}
```
Now that the array is sorted, it should be possible to determine the number of unique values using a single pass through the array. Try simulating on paper a single pass through the array above. When would you increment your count of the number of unique values?

Note: Because we tell you that the array is guaranteed to have at least one value, you also know that it has at least one unique value: the element in position 0. As a result, you could safely initialize your count to 1 and begin your pass with the second element in the array.
When determining the efficiency of our new implementation, do we need to include the steps taken by mergeSort?

Yes! The total number of steps taken by the algorithm is equal to the steps taken by mergeSort plus the steps taken by the rest of your implementation.

Problem 3

For Problem 3, parts 1 and 2, do you have any suggestions on how to get started?

This problem is similar to exercises that we covered in lecture and to Tasks 1 and 2 from Lab 8, so you could start by reviewing that material. Note that even though those exercises involved singly-linked lists and Problem 3 deals with doubly-linked lists, the underlying principles are the same.
For Problem 3, is there any way to test the code that we write?

You should start by convincing yourself on paper that your code is correct. Draw the necessary diagrams and trace through your code, making sure that it works correctly.

Once you have checked your work on paper, you can make use of a simple version of the DNode class that we have created.

To use it, you should click on this link and save the file in your ps6 folder.

Open the file in VSCode, and you should see a simple DNode class that includes:
- the definitions of the fields
- a DNode constructor
- a convert method that can be used to convert a Java String object to a doubly-linked list of DNode objects
- a toString() method that allows us to print a DNode object and see the corresponding string
- a removeNexts() method that can be used to create a scenario like the one envisioned for the addNexts() method that you need to write for Problem 3-3
- a skeleton for the addNexts() method that you will write
- a main method with some initial test code – including code that sets up the initial diagram that we have provided in Problem 3.
To test your answer for part 2, you can add your lines of code to the specified section of the main method and run the program to see if you get the correct result.

To test your answer for part 3, you can fill in the skeleton of addNexts() with your implementation of the method, and see if you get the correct results for the test that we have included in main and any additional tests that you include in main.

If you add your code for parts 2 and 3 and it works correctly, the output of the program that we have provided should be:
```
before changes for 3-2: set
after changes for 3-2: seat

initial str2: terriers
after setting next fields to null: t
after calling addNexts(): terriers
```
For Problem 3-3, do you have any suggestions for how to get started?

We recommend that you use an iterative traversal with a “trailing” reference that stays one node behind the trav reference that is being used to perform the traversal. We discussed trailing references in lecture, and one example of using one can be found in the insertSorted method of the StringNode class.

The DNode method that we have provided for testing (see above) includes another example of a trailing reference in the method called removeNexts(). That methods traverses a doubly-linked list from front to back, setting the next fields in every node to null. Your addNexts() method will need to traverse the list in the reverse direction – from the last node back to the first node – making the next fields point to the appropriate nodes.

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 union method should also use indices to walk down the arrays, but it should form the union, rather than the merge.
I’m stuck on problem 5? Do you have any hints?

Here again, we strongly encourage you to consider one or more concrete cases on paper.

For example, consider the following arrays:
```
a1: {10, 5, 7, 5, 9, 4}
a2: {7, 5, 15, 7, 7, 9, 10}
```
Once you have sorted them, you will have the following:
```
a1: {4, 5, 5, 7, 9, 10}
a2: {5, 7, 7, 7, 9, 10, 15}
```
Then you will need to take an approach similar to the one taken by the merge method.

Like merge, you will need several different loops:
- one that executes as long as both arrays still have values
- one that takes care of any “leftover” values in a1
- one that takes care of any “leftover” values in a2
As the problem indicates, one key difference between merge and union is that merge needs to write all of the elements in both arrays to the results array, whereas you only want to write a value if it is unique. As a result, each of your three loops will need to include code that skips over duplicate values – i.e., values that have already been included in the results. And because there may be multiple duplicates of a given value in a given array, you will need to use nested loops to skip over the duplicates.

Try simulating on paper how you would process the above arrays. When should you increment each of your indices? When should you write a value to the results array?

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; 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?

To see an example of this type of conversion, see the solutions to Lab 8, Task 4. In those solutions, we have included an iterative version of the numOccur method. The original version – the one that was provided for PS 6 – was recursive.
In problems 6.2, 6.4, and 6.6, we have to write recursive versions of existing iterative methods of the StringNode class. Can you give us any suggestions for that type of conversion?

Task 4 of Lab 8 involves converting the original iterative version of the convert method to a recursive version, and it discusses a strategy for doing so. You can see the resulting recursive method in the solutions to Lab 8, Task 4.
When writing recursive methods in problem 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 problem 6. Do you have any hints on how to do this?

As always, 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 recursivenumOccur 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 donumOccur([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 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;
    }

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

    return new StringNode(str.ch, null);
}
```
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. We reviewed this method in Lab 8.

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.