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

Problems 5 and 6

1. In problem 5, 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, 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. For problem 7, part 2 (pairSumsImproved), our algorithm needs to run in O(n log n) 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 pairSumsImproved() method?

   Yes! This means that you need to choose a sorting algorithm that runs in O(n log n) 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.

2. Do you have any hints for problem 7, part 2 (pairSumsImproved)?

   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 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 union method should also use indices to walk down the arrays, but it should form the intersection, rather than the merge.

2. I’m stuck on problem 8? Do you have any hints?

   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?

Last updated on July 22, 2025.