Problem Set 2

Due by 11:59 p.m. Eastern time on July 7, 2026.
See below for a summary of the policies regarding late submissions.

Preliminaries

Homework is due by 11:59 p.m. Eastern time on the stated due date. If it is submitted more than 10 minutes after that time, it will be considered a full day late. There will be a 10% deduction for submissions that are up to one day late, and a 20% deduction for submissions that are 2 or 3 days late. We will not accept any homework that is more than 3 days late. Plan your time carefully, and don’t wait until the last minute to begin an assignment. Starting early will give you ample time to ask questions and obtain assistance.

In your work on this assignment, make sure to abide by our policies on academic conduct.

If you have questions while working on this assignment, please come to office hours, post them on Ed Discussion, or email cscie22-staff@lists.fas.harvard.edu

Part I

55-65 points total

Creating the necessary folder

1. If you haven’t already created a folder named s22 for your work in this course, follow these instructions to do so.

2. Then create a subfolder called ps2 within your s22 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

The problems from Part I will all be completed in a single PDF file. To create it, you should do the following:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps2_partI.

4. Add your work for the problems from Part I to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file on your machine. The resulting PDF file (ps2_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Sorting practice

14 points; 2 points for each part

Given the following array:

{24, 3, 27, 13, 34, 2, 50, 12}

1. If the array were sorted using selection sort, what would the array look like after the third pass of the algorithm (i.e., after the third time that the algorithm performs a pass or partial pass through the elements of the array)?

2. If the array were sorted using insertion sort, on how many iterations of the outer loop would the inner do…while loop be skipped?

3. If the array were sorted using Shell sort, what would the array look like after the initial phase of the algorithm, if you assume that it uses an increment of 3? (The method presented in lecture would start with an increment of 7, but you should assume that it uses an increment of 3 instead.)

4. If the array were sorted using the version of bubble sort presented in lecture, what would the array look like after the fourth pass of the algorithm?

5. If the array were sorted using the version of quicksort presented in lecture, what would the array look like after the initial partitioning phase?

6. If the array were sorted using radix sort, what would the array look like after the initial pass of the algorithm?

7. If the array were sorted using the version of mergesort presented in lecture, what would the array look like after the completion of the fourth call to the merge() method—the method that merges two subarrays? Note: the merge method is the helper method; is not the recursive mSort method.

Problem 2: Counting comparisons

6 points total; 2 points each part

Given an already sorted array of 6 elements, how many comparisons of array elements would each of the following algorithms perform?

1. selection sort

2. insertion sort

3. mergesort

Give an exact number of comparisons for each algorithm, and explain each answer briefly.

Problem 3: Comparing two algorithms

6 points total; 3 points each part

The Fibonacci sequence begins as follows:

1, 1, 2, 3, 5, 8, 13, 21, ...

The first two elements in the sequence are both 1, and all other elements are the sum of the previous two elements. For example:

2 = 1 + 1
3 = 1 + 2
5 = 2 + 3
8 = 3 + 5

Below are two algorithms for printing the first n numbers in this sequence:

Algorithm A:

public static void printFibA(int n) {
    for (int i = 0; i < n; i++) {
	int prev = 0;
	int curr = 1;

	for (int j = 0; j < i; j++) {
	    int next = prev + curr;
	    prev = curr;
	    curr = next;
	}

	System.out.print(curr + " ");
    }
}

Algorithm B:

public static void printFibB(int n) {
    int prev = 0;
    int curr = 1;

    for (int i = 0; i < n; i++) {
	System.out.print(curr + " ");
	int next = prev + curr;
	prev = curr;
	curr = next;
    }
}

1. What is the worst-case time efficiency of algorithm A in terms of the parameter n? Make use of big-O notation and explain your answer briefly.

2. What is the worst-case time efficiency of algorithm B in terms of the parameter n? Make use of big-O notation and explain your answer briefly.

Problem 4: Counting unique values

12 points total

Let’s say that you want to determine the number of unique values in an unsorted array of n elements. For example, consider the following array:

{10, 6, 2, 5, 6, 6, 8, 10, 5}

It has 9 elements but only 5 unique values: 10, 6, 2, 5 and 8.

Here’s one possible method for solving this problem:

// Note: we assume that arr is not null.
public static int numUnique(int[] arr) {
    int count = 0;

    for (int i = 0; i < arr.length; i++) {
        // does arr[i] also appear somewhere "after" 
        // (i.e., to the right) of position i?
        boolean appearsAfter = false;

        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] == arr[i]) {
                appearsAfter = true;
                break;
            }
        }

        // only count arr[i] if it doesn't appear 
        // anywhere to the right of position i
        if (! appearsAfter) {
            count++;
        }
    }

    return count;
}

1. (2 points) Describe the worst case for this algorithm. When does it occur?

2. (4 points) Derive an exact formula for the number of times that the line comparing arr[j] to arr[i] is executed in the worst case as a function of the length n of the array.

3. (2 points) In the worst case, what is the big-O expression for the algorithm’s overall time efficiency as a function of the length n of the array? Explain your answer briefly.

4. (2 points) Describe the best case for this algorithm. When does it occur?

5. (2 points) In the best case, what is the big-O expression for the algorithm’s overall time efficiency as a function of the length n of the array? Explain your answer briefly.

Problem 5: Improving numUnique()

10 points total; required for grad-credit students; may be completed for “partial” extra credit by others.

1. (7 points) Create an alternative implementation of the numUnique() method that has a better worst-case time efficiency than the method from Problem 4. Hint: Begin by sorting the array, which you can do by calling the sorting method from our Sort class with the best worst-case time efficiency. Make your implementation as efficient as possible. Put your code in your ps2_partI file.

2. (3 points) What is the wost-case time efficiency of your alternative implementation as a function of the length n of the array? Use big-O notation, and explain your answer briefly.

Problem 6: Practice with references

17 points total

As discussed in lecture, a doubly linked list consists of nodes that include two references: one called next to the next node in the linked list, and one called prev to the previous node in the linked list. The first node in such a list has a prev field whose value is null, and the last node has a next field whose value is null.

The top portion of the diagram below shows a doubly linked list of characters that could be used to represent the string "cat".

Each of the nodes shown is an instance of the following class:

public class DNode {
    private char ch;
    private DNode next;
    private DNode prev;
}

(In the diagram, we have labeled the individual fields of the DNode object that contains the character 'c'.)

In addition to the list representing "cat", the diagram shows an extra node containing the character 'h', and two reference variables: y, which holds a reference to the second node in the list (the 'a' node); and x, which holds a reference to the 'h' node. The diagram also shows memory addresses of the start of the variables and objects. For example, the 'c' node begins at address 0x400.

1. (12 points) Complete the table we have provided in ps2_partI, filling in the address and value of each expression from the left-hand column. You should assume the following:

   • the address of the ch field of a DNode is the same as the address of the DNode itself

   • the address of the next field of a DNode is 2 more than the address of the DNode itself

   • the address of the prev field of a DNode is 6 more than the address of the DNode itself, which means that it is also 4 more than the address of the next field.

2. (5 points) Write a Java code fragment that inserts the 'h' node between the 'c' node and the 'a' node, producing a linked list that represents the string "chat". Your code fragment should consist of a series of assignment statements. You should not make any method calls, and you should not use any variables other than the ones provided in the diagram. Make sure that the resulting doubly linked list has correct values for the next and prev fields in all nodes.

   Testing your code fragment
   You should start by convincing yourself on paper that your code is correct. Draw the necessary diagrams and trace through your code, making sure that it works correctly.

   Once you have checked your work on paper, you can make use of a simple version of the DNode class that we have created.

   To use it, you should click on this link and save the file in your ps2 folder.

   Open the ps2 folder in VSCodium, and you should see a simple DNode class that includes:

   • the definitions of the fields

   • a DNode constructor

   • a convert method that can be used to convert a Java String object to a doubly-linked list of DNode objects

   • a toString() method that allows us to print a DNode object and see the corresponding string

   • a main method with some initial test code – including code that sets up the initial diagram that we have provided above.

   To test your code fragment, you can add your lines of code to the specified section of the main method, and compile and run the program to see if you get the correct result.

   The output of the program that we have provided should be:

   before changes to list: cat
   after changes to list: chat
   

Submitting your work for Part I

Submit your ps1_partI.pdf file by taking the following steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file on your machine.

2. Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Part II

45 points total

Problem 7: Turning an array into a set

25 points

Getting started

1. If you haven’t already done so, create a folder named ps2 for your work on this assignment. You can find instructions for doing so here.

2. Download our Sort class from lecture, making sure to save it in your ps2 folder:
   Sort.java

   Make sure to put the file in your ps2 folder. If your browser doesn’t allow you to specify where the file should be saved, try right-clicking on the link above and choosing Save as… or Save link as…, which should produce a dialog box that allows you to choose the correct folder for the file.

3. In VSCodium, select the File->Open Folder menu option, and use the resulting dialog box to find and open your ps2 folder. (Note: You must open the folder; it is not sufficient to simply open the file.)

4. Select File->New File, which will open up an empty editor window.

5. Select File->Save, and give the new file the name Problem7.java.

6. In the new file, create a class called Problem7.

Your tasks

1. A mathematical set is not allowed to have any repeated values – i.e., values that appear more than once.

   In your Problem7 class, implement a method with the following header

   public static int makeSet(int[] arr)
   

   It should take an arbitrary array of integers, and it should turn that array into a set by eliminating any repeated values. The remaining elements should occupy the leftmost positions of the array. Any array locations that are unused after the repeated values are removed should be filled with zeroes.

   In addition to making the necessary adjustments to the array, the method should return an integer that specifies the number of repeated values that were removed.

   For example, if you add the following test code to a main method in Problem7:

   int[] a1 = {12, 5, 2, 12, 5, 5, 10};
   int numRepeats = makeSet(a1);
   System.out.println(Arrays.toString(a1));
   System.out.println(numRepeats);
   

   it should display something like this:

   [2, 5, 10, 12, 0, 0, 0]
   3
   

   For full credit, your method must be as efficient as possible. See below for more details.

   Important notes:

   • Your method should have an average-case running time of O(nlogn), where n is the length of the array. In order to achieve this efficiency, you should begin by sorting the array using an appropriate method from our Sort class, which you should have downloaded above. Once you have done so, only O(n) additional steps should be needed to turn the array into a set.

   • In addition, your method should use O(1) additional memory—i.e., it should not create and use a second array.

   • One inefficient approach would be to scan through the sorted array from left to right, and, whenever you encounter a repeated value, to shift all of the remaining elements left by one. The problem with this approach is that elements can end up being shifted multiple times, and thus the algorithm will end up with a worst-case running time that is O(n²). Your method should move each element at most once. This will ensure that the steps taken after sorting the array will execute in O(n) time. Only half credit will be given for methods that move elements more than once.

   • If arr is null, the method should throw an IllegalArgumentException.

   • If arr is an array of length 0 or 1, the method should simply return 0.

2. Include a main method with code that tests your new method. In order to use the Arrays.toString() method as we did in the example above, you will need import the java.util package by adding the following line of code before your class header:

   import java.util.*;
   

   In addition to the case shown above, you should include at least one other test case that you create.

Problem 8: Finding the median

20 points

Getting started

1. If you haven’t already done so, create a folder named ps2 for your work on this assignment.

2. Download the following file:
   Problem8.java

   Make sure to put the file in your ps2 folder. If your browser doesn’t allow you to specify where the file should be saved, try right-clicking on the link above and choosing Save as… or Save link as…, which should produce a dialog box that allows you to choose the correct folder for the file.

3. In VSCodium, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open the folder that you created for this assignment. (Note: You must open the folder; it is not sufficient to simply open the file.)

   The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with the name of the Problem8.java file that you downloaded above.

4. Click on the name Problem8.java, which will open an editor window for that file.

Overview

The median of an array of integers is the value that would belong in the middle position of the array if the array were sorted. For example, consider the following array:

int[] arr = {4, 18, 12, 34, 7, 42, 15, 22, 5};

The median of this array is 15, because that value would end up in the middle position if the array were sorted:

int[] arr = {4, 5, 7, 12, 15, 18, 22, 34, 42};

If an array has an even number of elements, the median is the average of the elements that would belong in the middle two positions of the array if the array were sorted.

In this problem, you will implement a recursive method that can be used to determine the median of an array of integers by using an approach that is similar to the partitioning approach taken by quicksort. However, for the sake of efficiency, you should not sort a subarray if it could not contain the median. More detail is provided below.

Reviewing the provided code

In Problem8.java, we have given you the following:

• copies of the swap() and partition() methods from our Sort class. The recursive method that you will write should call the partition() method to process the necessary portions of the array (see below). You should not change these methods in any way.

• skeletons of the two methods that you will implement. See below for more detail.

• a main() method that you should fill with code that tests your median-finding algorithm. See below for more detail.

Your tasks

1. In the Problem8 class, implement the private method called findMed whose header we have provided:

   private static void findMed(int[] arr, int first, int last)
   

   This is the recursive method that will be at the heart of the your median-finding algorithm. It should take the steps needed so that the median value (or values, in the case of an even-length array) end up in the middle position of the array (or the two middle positions, in the case of an even-length array). The method should not return anything, which is why it has a return type of void.

   Your method should use an algorithm that is similar to one used by the recursive qSort() method in our Sort class. However, you will need to modify the algorithm so that it only sorts as much of the array as is necessary to determine the median value or values. For full credit, you must avoid calling partition() on subarrays that could not possibly contain a median value.

   See the hints provided below for additional details about the approach that you should take.

2. Implement the public method called findMedian whose header we have provided:

   public static void findMedian(int[] arr)
   

   You should not change the header of this method in any way.

   This method should serve as a “wrapper” method around your recursive findMed method, just as the quickSort() method in our Sort class serves as a wrapper around the recursive qSort() method. It should make an appropriate initial call to your recursive method.

   Special cases: If the parameter arr is null or is a reference to an array of length 0 or 1, findMedian should simply return.

3. Add tests to the main() method that we have provided. We have included sample definitions of odd- and even-length arrays that you can use as you see fit. Make sure that your main() method calls the wrapper method (findMedian), rather than calling the recursive findMed method directly.

   Once you have processed a given array, your main() method should then find and print the median value by looking at the value(s) in the middle position(s) of the array.

   For full credit, you should include at least two test cases.

Hints

• As mentioned above, your recursive findMed method should be similar to our qSort() method. However, after it calls partition(), it should determine whether to make recursive call(s) to process just the left subarray, just the right subarray, or both subarrays, depending on whether each subarray could contain the median value (or, in the case of an even-length array, at least one of the two median values). When making this decision, remember that after a call to partition(), everything in the left subarray is less than or equal to everything in the right subarray. Given this fact, and given the location(s) where the median value(s) must ultimately end up, you should be able to determine whether the method should make a recursive call on a particular subarray. Tracing through some concrete examples should help you to discover the logic.

  (Note: Rather than checking to see whether a given recursive call is needed, it is also possible to defer this checking to the start of the next invocation of the method. In other words, the recursive method could begin by checking to see if the current subarray could contain one or more of the median values, and, if it could not, the method could return without doing anything.)

• You should be able to accomplish this task with only 4-10 lines worth of changes/additions to the standard quicksort algorithm. If your modifications to the code in qSort() are substantially longer than this, you are likely on the wrong track.

Submitting your work for Part II

You should submit only the following files:

• Problem7.java
• Problem8.java

You do not need to submit Sort.java.

Here are the steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add both files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that you see the code that you want us to grade.