Problem Set 2 FAQ

Problem 1

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

1. 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 5.

Problem 6

1. In problem 6, part 1, 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.

2. For problem 6, part 2, 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

1. Do you have any hints for problem 7 (removing duplicates)?

   This problem asks you to remove duplicates from an already sorted array using an algorithm that requires O(n) steps. To do this, each element can move at most once.

   For example, the problem set says that if we are given the array:

   { 2,  5,  5,  5, 10, 12, 12}
   

   we need 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 example from the problem set:

   { 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 duplicates to its left.

   • Element 2 (the second 5): does it need to move? No, because it’s a duplicate.

   • Element 3 (the third 5): does it need to move? No, because it’s a duplicate.

   • Element 4 (the 10): does it need to move? Yes, because it’s not a duplicate, and there are duplicates to its left.

   • Element 5 (the first 12): does it need to move? Yes, because it’s not a duplicate, and there are duplicates to its left.

   • Element 6 (the second 12): does it need to move? No, because it’s a duplicate.

   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

1. For problem 8, 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.

Last updated on September 30, 2025.