Problem Set 6

due by 11:59 p.m. on Tuesday, March 26, 2024

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs112-staff@cs.bu.edu.

Part I

50 points total

Creating the necessary folder

Create a subfolder called ps6 within your cs112 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

Problems in Part I will 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 ps6_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 in your ps6 folder. The resulting PDF file (ps6_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: More practice with sorting - Quicksort

4 points; individual-only

Important: When answering these questions, make sure to apply the versions of these algorithms that are in the Sort class we give you. The Java code for each algorithm can be found in our Sort class.

Given the following array:

{14, 7, 27, 13, 24, 20, 10, 33}

1. If the array were sorted using quicksort, what would the array look like after the third call to the partition method?

2. If the array were sorted using quicksort, what would the array look like after the fourth call to the partition method?

Problem 2: More practice with sorting - Mergesort

6 points; 2 points for each part; individual-only

Given the following array:

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

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

2. What would the array look like after the completion of the fourth call to the merge() method?

3. The initial call to the recursive mSort() method is made from within the mergeSort() “wrapper” method. This initial call to mSort() is not a recursive call, because the method is not calling itself. Rather, all recursive calls to mSort() are made from within mSort().

   Assuming that the array has at least two elements, the initial invocation of mSort() makes two recursive calls (which in turn lead to other recursive calls, and so on). Starting with the initial array above, what would the array look like after the completion of the first of these two recursive calls?

Problem 3: Counting unique values

10 points total; individual-only

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. (2 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 4: Improving the efficiency of an algorithm

7 points total; individual-only

1. (4 points) Create an alternative implementation of the numUnique method from the previous problem that has a better worst-case time efficiency than the original method. Like the original method, you may assume that arr is not null, and you may also assume that it has at least one element. Make your implementation as efficient as possible.

   Hint: Your new method should begin by calling the mergeSort method from our Sort class to sort the array.

2. (1.5 points) What is the worst-case time efficiency of your new method as a function of the length n of the array? Use big-O notation, and explain your answer briefly.

3. (1.5 points) We specified that your new method should have a better worst-case time efficiency than the original method. Is it also more efficient in the best case? Explain your answer briefly.

Problem 5: Practice with references

15 points total

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 "set".

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 's'.)

In addition to the list representing "set", the diagram shows an extra node containing the character 'a', and two reference variables: n, which holds a reference to the second node in the list (the 'e' node); and m, which holds a reference to the 'a' node. The diagram also shows memory addresses of the start of the variables and objects. For example, the 's' node begins at address 0x180.

1. (6 points) Complete the table that we have provided in ps6_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. (4 points) Write a Java code fragment that inserts the 'a' node between the 'e' node and the 't' node, producing a linked list that represents the string "seat". 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. You may assume that your code is part of the main method in the DNode class, and thus it has direct access to the private fields of the DNode objects.

   Make sure that the resulting doubly linked list has correct values for the next and prev fields in all nodes.

3. (5 points) Suppose you have a doubly linked list of DNode objects in which the prev references have the correct values but the next references have not yet been initialized.

   Write a static method called addNexts() that:

   • takes one parameter, a reference to the last node of the linked list

   • traverses the linked list from back to front, filling in the next references

   The method should not return a value.

   You may assume that there is at least one node in the list, and that the method is part of the DNode class.

   You do not need to code up this method as part of a class; simply include it in your ps6_partI file.

Problem 6: Printing the odd values in a list of integers

8 points total; 5 points each part; individual-only

Suppose that you have a linked list of integers containing nodes that are instances of the following class:

public class IntNode {
    private int val;
    private IntNode next;
}

1. Write a method named printOddsRecur() that takes a reference to the first node in a linked list of IntNode objects and uses recursion to print the odd values in the list (if any), with each value printed on a separate line. If there are no odd values, the method should not do any printing.

2. Write a method named printOddsIter() that uses iteration to perform the same task.

You may assume that the methods that you write are static methods of the IntNode class.

Submitting your work for Part I

Note: There are separate instructions at the end of Part II that you should use when submitting your work for that part of the assignment.

Submit your ps6_partI.pdf file using these steps:

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

2. Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 112.

3. Click on the name of the assignment (PS 6: Part I) 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.)

4. 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.

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

6. Once you have assigned pages to all of the questions 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

50 points total

Problem 5: Finding the union of two arrays

15 points; pair-optional

This is the only problem of the assign that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Getting started

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

2. Download our Sort class, making sure to save it in your ps6 folder.

3. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open your ps6 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 Problem5.java.

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

The required method

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

public static int[] union(int[] a1, int[] a2)

It should take two arrays of integers a1 and a2, and it should use an approach based on merging to create and return a new array containing the union of the values in a1 and a2 – i.e., all values that are found in one or both of the original arrays. The result should be in sorted order, and it should not include any duplicate values. For example, the following test code:

int[] a1 = {10, 5, 7, 5, 9, 4};
int[] a2 = {7, 5, 15, 7, 7, 9, 10};
int[] result1 = union(a1, a2);
System.out.println("result1: " + Arrays.toString(result1));

int[] a3 = {0, 2, -4, 6, 10, 8};
int[] a4 = {12, 0, -4, 8};
int[] result2 = union(a3, a4);
System.out.println("result2: " + Arrays.toString(result2));

should display:

result1: [4, 5, 7, 9, 10, 15, 0, 0, 0, 0, 0, 0, 0]
result2: [-4, 0, 2, 6, 8, 10, 12, 0, 0, 0]

(Note that we end up with extra 0s at the end of both of these result arrays for reasons that are discussed below.)

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

Required approach

1. Begin by creating a new array for the union, giving it a length that is the sum of the lengths of the two original arrays.

2. Use one of the more efficient sorting algorithms from our Sort class to sort both of the original arrays. If you have downloaded our Sort class into the same folder as your Problem5 class (see the Getting started section above), you should be able to make method calls to an appropriate method in the Sort class from within your union method.

3. Find the union of the two arrays by employing an approach that is similar to the one that we used to merge two sorted subarrays (i.e., the approach taken by the merge method in Sort.java)—using indices to “walk down” the two original arrays and copy their values into the array that you created for the union.

   Important notes:

   • One important difference between merging and finding the union is that the union should not include any duplicates. In other words, a given number that appears in one or both of the original arrays should appear exactly once in the union. As a result, you will need to include code that skips over duplicate values as needed as you walk down the original arrays.

   • Your algorithm should be as efficient as possible. In particular, you should perform at most one complete pass through each of the arrays.

4. At the end of the method, return a reference to the array containing the union.

5. Add test code for your method to a main method. Recall that that you can use the Arrays.toString() method to convert an array to a string; import the java.util. package to gain access to the Arrays class. In addition to the cases shown above, you should include at least one other test case that you create.

Notes:

• Because we don’t include duplicates in the result, the number of values in the union (call it x) can be smaller than the length of the results array (which should be the sum of the lengths of the original arrays). In such cases, you should end up with extra 0s at the end of the results array as shown in both of our test cases above.

  If 0 appears in one or both of the original arrays, it will also show up earlier in the results array as part of the union, as it does in our second example above.

• If either a1 or a2 is null, the method should throw an `IllegalArgumentException.

Problem 6: Rewriting linked-list methods

35 points; individual-only

We will complete the material needed for this problem during the week of March 20.

In lecture, we’ve been looking at linked lists of characters that are composed of objects from the StringNode class. The class includes a variety of methods for manipulating these linked lists, and many of these methods provide functionality that is comparable to the methods found in Java String objects.

Some of the existing StringNode methods use recursion, while others use iteration (i.e., a loop!). In this problem, you will rewrite several of the methods so that they use the alternative approach.

0. Begin by downloading the StringNode class, storing it in your ps6 folder.

   In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open your ps6 folder. (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 downloaded file. Click on the name of the file to open an editor window for it.

1. Rewrite the indexOf() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

2. Rewrite the toUpperCase() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

3. Rewrite the isPrefix() method so that it uses iteration. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

4. Rewrite the insertAfter() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

5. Rewrite the copy() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

6. Rewrite the removeAllSpaces() method so that it uses iteration. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

7. Test your methods thoroughly.

   • There is existing test code in the main() method. Leave that code intact, and use it to test your new versions of the methods.

   • You are also strongly encouraged to add other tests to this method, although doing so is not strictly required.

   • As mentioned in the guidelines at the start of the problem, the provided toString() method means that you can print a StringNode s in order to see the portion of the linked-list string that begins with s.

   • Another useful method for testing is the convert() method, which converts a Java String object into the corresponding linked-list string.

   • You may also find it helpful to download the following file into your ps6 folder: StringNodeOrig.java.

     It contains the original version of the StringNode class, so that you can compare the behavior of the original methods to the behavior of your revised methods.

Submitting your work for Part II

You should submit only the following files:

• Problem5.java
• StringNode.java

Make sure that you do not try to submit a .class file or a file with a ~ character at the end of its name.

Here are the steps:

1. Login to Gradescope as needed by clicking the link in the left-hand navigation bar, and then click on the box for CS 112.

2. Click on the name of the assignment (PS 5: Part II) 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.)

3. Add your 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.

4. Click the Upload button.

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

6. 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 for at least some of the problems 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.

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

8. 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 the files contain the code that you want us to grade.