Problem Set 4 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

Could you define more precisely what constitutes a “pass” or “phase” of each of the 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 “phase” of Shell sort in the sense used in problem 3 is a single iteration of the outer while loop that controls the sequence of increments. For problem 3, we are interested in the initial iteration of this loop (the “phase” in which incr == 3):
```
while (incr >= 1) {
    // statements omitted
    incr = incr/2;
}
```

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
    }
}

Problem 4

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

The basic idea behind recursive backtracking is that you have a number of variables that can each take on a number of possible values, and you are trying to assign values to the variables subject to a set of constraints.

In the Sudoku problem, what are the variables? What are the possible values for each variable? What are the constraints – i.e., the requirements that 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 that have already been 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 Sudoku 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, and val 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 n-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.)

Our template mentions that you might sometimes want to have additional parameters for the recursive-backtracking method. For this problem, you will need to decide how many parameters you want to use in your solveRB() method, and what they will mean. There is more than one correct choice for the number and meaning of the parameters. All that matters is that your parameter or parameters allow you to specify which variable the current method call is responsible for.

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 parameter(s) that you decide to use for your method, you may need to modify it/them in some other way when you make the recursive call. The important thing is that the new parameter value(s) should reflect the subproblem that you’re trying to solve by making the recursive call, and the parameter(s) should eventually reach a base case of the recursion.
Based on some temporary debugging statements that I have added to my code, my solveRB() method seems to be working more or less as expected. However, I end up either caught in an infinite loop, or getting back a final return value of false instead of true. Do you have any suggestions?

One thing worth checking is how you are handling the cells that have fixed values. You should be checking for a fixed-value cell before you begin the for loop, because you do not want to try to assign any values to these cells.

Instead of entering the for loop for these cells, you should instead do two things:
- make a recursive call to move onto the next cell
- return whatever value is returned by that recursive call.
Taking this approach will allow you to pass back to the invocation for the previous cell the result of processing the subsequent cells.
I’m not sure if my constraint-checking method is working correctly. Is there an easy way to check it?

One thing you could do is to add to your Sudoku class a non-static helper method called test() that looks like this:
```
public void test() {
    System.out.println(this.isValid(...));
    System.out.println(this.isValid(...));
    // add other similar lines here
}
```
Replace each ... with parameters for a single call to your constraint-checking method (which we’re assuming you have called isValid, but you can adjust the name here if you called it something else).

Choose the parameters of the calls based on one of the puzzles that we have given you. For example, you could base your calls on puzzle1.txt:
```
-------------------------------------
|   | 4 |   |   |   | 3 | 7 |   |   |
-------------------------------------
|   | 8 | 9 | 7 |   |   | 1 |   |   |
-------------------------------------
|   |   |   |   |   | 4 | 2 |   |   |
-------------------------------------
|   |   |   |   |   |   |   |   | 1 |
-------------------------------------
| 6 |   |   | 5 | 1 | 8 |   |   | 9 |
-------------------------------------
| 2 |   |   |   |   |   |   |   |   |
-------------------------------------
|   |   | 5 | 3 |   |   |   |   |   |
-------------------------------------
|   |   | 6 |   |   | 1 | 9 | 4 |   |
-------------------------------------
|   |   | 1 | 2 |   |   |   | 6 |   |
-------------------------------------
```
Given this puzzle, possible tests could include:
- testing if it is valid to put a 4 in the upper-left hand corner; your method should say that it isn’t, because there is already a 4 in that row
- testing if it is valid to put a 9 in the upper-left hand corner; your method should say that it isn’t, because there is already a 9 in that 3x3 subgrid
- testing if it is valid to put a 5 in the upper-left hand corner; your method should say that it is, because there isn’t a 5 in that row, column, or 3x3 subgrid.
Once you have created this test() method, add a temporary call to it in the main() method – calling it after the puzzle is read in but before the solve method is called:
```
...
puzzle.test();    // temporary call to new test method

if (puzzle.solve()) {
    ...
```
Then, run the program and specify puzzle1.txt as the desired puzzle, and see whether you get the expected return values from your test calls.

Problem 5

For part 2 (findPairSumsFaster), our algorithm needs to run in O(nlogn) time in the average case, and we need to begin by sorting the array using one of the sorting algorithms from the Sort class. Does the time complexity of the sorting algorithm we choose count towards the overall time complexity of our findPairSumsFaster() method?

Yes! This means that you need to choose a sorting algorithm that runs in O(nlogn) time or better, in the average case. Once the array is sorted, you should perform only O(n) additional steps to find all the pairs that sum to k.
Do you have any hints for part 2 (findPairSumsFaster)?

You might want to draw some inspiration from the approach quicksort takes in its partition() method – starting with two indices outside the array, and moving them gradually towards the center.

Problem 6

Do you have any guidelines for determining time efficiency by experiment in part 2?

Be sure that you include both some kind of table showing the results of your experimental runs of the algorithm (including at least 10 runs for each value of n: 1000, 2000, 4000, 8000 and 16000, first with random, then with fully sorted data), and a few paragraphs containing your analysis of the time complexity of the algorithm in each case.

Your time analysis should include six big-O expressions: three for the comparisons, moves, and overall time complexity of shubbleSort with random data, and three for the comparisons, moves, and overall time complexity of shubbleSort with fully sorted data. You also need to justify each of these big-O expressions using your experimental data. If the algorithm does not appear to fall neatly into one of the standard efficiency classes, explain your reasons for that conclusion, and state the two efficiency classes that it appears to fall between.