Problem Set 5 FAQ

Problem 4
Problem 6
Problem 7

Problem 4

Could you define more precisely what constitutes a “pass” of the first three sorting algorithms?

A pass of selection sort consists of a single iteration of the for loop in the selectionSort() method:

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) {
        int j = indexSmallest(arr, i, arr.length-1);
        swap(arr, i, j);
    }
}

A pass of insertion sort consists of a single iteration of the outer for loop in the insertionSort() method:

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // statements inside outer for loop omitted
    }
}

A pass of bubble sort is a single iteration of the outer for loop in the bubbleSort() method:

public static void bubbleSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        // statements inside outer loop omitted
    }
}

I’m not sure how to figure out the order of the calls to mergesort. Any suggestions?

One thing that could help is to review the series of slides entitled “Tracing the Calls to Mergesort” in the lecture notes.

In addition, you could review the solutions to the exercise from Lab 5 in which we traced a method that makes multiple recursive calls.

Problem 6

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

As always, we strongly encourage you to consider what should happen for one or more concrete cases.

For example, recall the recursive removeVowels method. As with many recursive methods that operate on strings, this method makes recursive calls on ever smaller substrings. For example, let’s say that we wanted to do removeVowels("movies")

This would lead to the following sequence of method calls:
```
removeVowels("movies")
    removeVowels("ovies")
        removeVowels("vies")
            removeVowels("ies")
                removeVowels("es")
                    removeVowels("s")
                        removeVowels("")
```
(The last call might not be needed. It depends on which base cases you choose to include.)

Then, once you have the sequence of method calls, you should 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 removeVowels("ies") return – i.e., what string will result if the vowels in "ies" were removed? 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 the your method is not returning the correct value. You might 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 determines if a string is a palindrome – i.e., if it is a word like “radar” that reads the same in either direction:
```
public static boolean isPalindrome(String str) {  
    if (str == null || str.equals("")) {  
        return true;  
    }

    // recursive call -- the return value is thrown away
    isPalindrome(str.substring(1, str.length() - 1));

    char first = str.charAt(0);
    char last = str.charAt(str.length() - 1);
    if (first != last) {
        return false;
    } else {
        return true;
    }
}
```
This version of the method makes the correct recursive call – looking at the substring consisting of everything except the first and last characters – 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. However, 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.

Problem 7

I’m having trouble with the LetterSquare problem. Can you give us any hints on how to get started?

Think back to the lecture materials on recursive backtracking. The basic idea behind recursive backtracking is that you have a number of variables that can each take on a number of possible values. (How does this relate to this problem? What are the variables? How many variables do you need?) You want to find values for these variables that fit your constraints. (What are the constraints in this problem? What requirement do the values of the variables need to fulfill?)

A given invocation of the recursive-backtracking method uses a loop to consider all possible values for one of the variables. Once a value is successfully assigned to that variable, the method calls itself recursively, this time to consider all of the possible values for the next variable in the list (given the values of the variables they have already set). If you have successfully found values for all of the variables that fit the constraints, your terminating condition is met, and you can display the solution and return.

If a particular value for a variable violates a constraint, you should skip that value and keep trying other values. If you run out of values for a variable, you should backtrack to the previous level of the recursion and go back to trying values for the previous variable.
I am struggling to apply the backtracking template from the lecture notes to the LetterSquare problem. I’m confused about what n and val in the template should mean in the context of this problem.

As we said in the answer to the previous problem, recursive backtracking is a method for assigning values to a set of variables in light of a set of constraints. In the template, n tells you the variable that you’re currently trying to assign a value to, andval iterates over the set of possible values for that variable. (Note that n is not the variable itself - it is simply a parameter that allows you to determine the variable. For example, in the Queens problem, n was the number of row in which we were trying to place a queen, but we stored the actual values – i.e., the locations of the queens – in other data structures.)

Another detail of the template that can vary is the way that the parameters to the method are modified in the recursive call. In the template, n is incremented by 1 to indicate that the recursive call will focus on the next variable. However, depending on the parameters that you decide to use for your method, you may need to modify them in some other way when you make the recursive call. The important thing is that the new parameters should reflect the subproblem that you’re trying to solve by making the recursive call, and the parameters should eventually reach one of the values that constitute a base case of the recursion.
How can I test my isValid method to make sure that it is working?

The best way to do this is to add some temporary test code to the beginning of the main method in LetterSquare.

For example, the problem set describes some cases involving isValid that are based on the puzzle shown at the start of the problem (the one with sides {"tae", "nih", "omk", "lys"}).

You could test these cases by adding temporary code that looks like the following to the start of main:
```
String[] testSides = {"tae", "nih", "omk", "lys"};
LetterSquare test = new LetterSquare(testSides);
test.words[0] = "time";

// to test cases involving the second or third word,
// assign strings to other positions in test.words

// should get true
System.out.println(test.isValid("l", 0, 4));

// should get false
System.out.println(test.isValid("a", 0, 4));

// other tests go here

// exit the program after testing
System.exit(0);
```
To test other scenarios, you can change the strings in the testSides array and/or the strings assigned to the positions in the test.words array.

We strongly encourage you to thoroughly test your isValid method to ensure that it works in all cases!
I think my solveRB follows the template, but it isn’t finding a solution. Any suggestions?

First, make sure that you have thoroughly tested your isValid method as described above, since a faulty isValid will prevent your solveRB from working.

Once you have a working isValid, trying adding temporary print statements to solveRB to see if you can figure out where things are going wrong.

You can speed up testing by using temporary lines of code at the start of main. For example:
```
String[] testSides = {"qxz", "hkl", "def", "uvw"};
LetterSquare test = new LetterSquare(testSides);

// start by just limiting things to a 2-word solution
test.solveRB(0, 0, 2);

// exit the program after testing
System.exit(0);
```
Two notes about our code above:
- We have deliberately used a set of side strings that has very few possible words! This will limit the amount of output from your temporary print statements and make it easier to see if things are working correctly.
- We have made a call to solveRB with a maxWords parameter of 2. This will also limit the amount of output. There isn’t a two-word solution to this puzzle – in fact, there isn’t even a ten-word solution! – but that’s okay. Our temporary print statement(s) should still allow us to see if we are correctly building up the individual words and if we are correctly making the transition from the first word to the second word when needed.
One good starting point is to add the following print statement to the very beginning of your solveRB method:
```
System.out.println(wordNum + " " + charNum + " " + Arrays.toString(this.words));
```
Note that we print the wordNum and charNum parameters, along with the current contents of this.words. If this is the only temporary print statement that you add, and if you run the test code provided above, you should see something similar to the output in this file.

It’s possible that you will get different output if you consider the letters in a different order than our solution does. But you should still get something comparable. In particular, each element of thewords array should be either a valid full word or a valid prefix of a full word, and the letters in the words should observe all of the constraints of the puzzle.

If you don’t see appropriate output, see if you can narrow down your issue by adding temporary print statements elsewhere in your code.
My solveRB is finding and printing a solution, but it doesn’t stop after it does so. Instead, it goes on and continues looking for other solutions. What am I doing wrong?

As indicated in the problem description, your solveRB should include two different recursive calls: one to expand the current word, and one that will sometimes be used to move onto the next word. If either of these calls returns true, you must immediately return true. Otherwise, solveRB will continue looking for other solutions.
My solveRB is finding and printing a valid solution, but it has more words than the optimal solution. What am I doing wrong?

Make sure that you have included a base case that checks for cases in which wordNum is too big, given the value of maxWords.
I’ve done some debugging, but I’m still not getting a valid solution. Any suggestions?

Make sure that you are following the recursive-backtracking template from the lecture notes, but with the key differences noted in the problem description.

In addition, you should check the following:
- The base case that checks whether you have a solution should be checking that all letters are used and that the current word is full word of at least three letters.
- Both of your recursive calls should come in between the call that you make to add a new letter and the call that you make to remove that letter.
- You should only make the second recursive call if the current word is a full word of at least three letters.