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.
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.
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.
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?
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 intersection
method should also use indices to walk down the arrays, but
it should form the intersection, rather than the merge.
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 a “merging” loop that executes as
long as both arrays still have values. However, unlike
merge, you will not need additional loops that handle
any “leftover” values in the two arrays, since those leftover
values won’t be included in the intersection.
As the problem indicates, another key difference between
merge and intersection 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 appears in both
arrays and it has not already been included in the
result. As a result, your “merging” loop 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 a nested loop 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 21, 2026.