Problem Set 2 FAQ

Problem 1

For problem 1, 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 1 is a single iteration of the outer while loop that controls the sequence of increments. For problem 1, we are interested in the initial iteration of this loop (the “phase” in which incr equals 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
    }
}
```
- A “pass” of radix sort is the complete process of distributing values into separate bins based on the value of the current element in the sequence (e.g., current digit, current character, etc.), and then reassembling them back together into the original array after distribution.
- To get a sense of the order in which the calls to merge() happen in mergesort, see the series of slides entitled “Tracing the Calls to Mergesort” in the sorting lecture notes.

Problem 2

For problem 2 (“counting comparisons”), do you want the exact number of comparisons performed by each algorithm, or a big-O expression for the number of comparisons?

You should give the exact number of comparisons that would be performed by each algorithm for an already-sorted array of length 6.

Problem 6

In problem 6, when we’re calculating the addresses of the various fields within each node, do we need to perform addition in base-16 (hexadecimal), or is base-10 (decimal) addition okay?

We will accept either. For example, if you had a DNode located at address 0x109 and you wanted to determine the address of the next field within that node (at an offset of 2 bytes from the start address of the node), we would accept either 0x10B (using base-16 addition) or 0x111 (using base-10 addition) for the answer to 0x109 + 2.
For problem 6, should we assume that the private instance variables ch, next, and prev have corresponding public getter and setter methods?

No, you should assume that the code you’re writing has direct access to the private instance variables — either because the code is within the DNode class, or because it’s within a class that has the DNode class as a nested class. Therefore, you won’t need getter and setter methods for this problem.

Problem 7

Do you have any hints for problem 7 (turning an array into a set)?

This problem asks you to turn an array into a set by eliminating any repeated values.

It recommends that you start by sorting the array by using an appropriate algorithm from the Sort class. You can do so by prepending the name of the class:
```
Sort.methodName(arr);
```
Then, you need to take only O(n) steps to turn the sorted array into a set, with the remaining elements in the leftmost positions of the array, and any unused array locations filled with 0s.

To do this, each element in the sorted array can move at most once.

For example, the problem set gives us this possible original array:
```
{12, 5, 2, 12, 5, 5, 10}
```
The sorted version of this array looks like this:
```
{2, 5, 5, 5, 10, 12, 12}
```
The remaining code in the method needs to change it to look like this:
```
{2, 5, 10, 12, 0, 0, 0}
```
To get a O(n) algorithm, the 10 and 12 should be moved only once.

This problem is somewhat like insertion sort, in that you want to consider the elements from left to right and potentially “insert” each element arr[i] somewhere in the subarray that goes from arr[0] to arr[i].

However, the problem is different from insertion sort in that you don’t need to perform a backwards pass in which you figure out where an element should go while shifting other elements to the right.

Instead, you should be able to use an index to keep track of where the next “insertion” (if any) should occur. Also, the “insertions” are really just moves, in which an element arr[i] is copied into a position originally occupied by another element, without sliding other elements over.

Let’s consider how we would process the sorted array given above:
```
{2, 5, 5, 5, 10, 12, 12}
```
We consider the elements of the array from left to right, beginning with element 1 (the first 5).
- Element 1 (the first 5): does it need to move? No, because there are no repeated values to its left.
- Element 2 (the second 5): does it need to move? No, because it’s a repeated value.
- Element 3 (the third 5): does it need to move? No, because it’s a repeated value.
- Element 4 (the 10): does it need to move? Yes, because it’s not a repeated value, and there are repeated values to its left.
- Element 5 (the first 12): does it need to move? Yes, because it’s not a repeated value, and there are repeated values to its left.
- Element 6 (the second 12): does it need to move? No, because it’s a repeated value.
Given this example, here are some questions to ask yourself as you design your implementation of this method:
- What tests do you need to perform to determine whether an element should be moved?
- How will you keep track of the position where the next element to be moved should go?
- When should this position be updated?

Problem 8

Do you have any hints for problem 8 (finding the median)?

Here are a few:
- Rather than focusing on where the median value or values are, focus on where they need to end up.
- Try tracing through some concrete cases (partitioning the array, then looking at the resulting subarrays, and so on) to see if you can determine the logic. When you do so, keep in mind what you have learned about how partitioning works, and the degree to which values can move after a partition has occurred.
- Make sure that you continue to check for subarrays of length 1, just as the standard quicksort algorithm does.