Problem Set 4

due by 11:59 p.m. on Sunday, October 11, 2020

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

Part I

50 points total

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. Open the template that we have created for these problems in Google Docs: ps4_partI

2. Select File->Make a copy..., and save the copy to your Google Drive using the name ps4_partI.

3. Add your work to this file.

4. Once you have completed all of these problems, choose File->Download as->PDF document, and save the PDF file on your machine. The resulting PDF file (ps4_partI.pdf) is the one that you will submit. See the submission guidelines at this specification.

Important: Put your responses to each of the following problems in the appropriate section of the ps4PartI template that you created on Google Drive.

Problem 1: Rewriting a method

15 points; individual-only

Consider the following method, which uses iteration (a for loop) to search for an item in an array of integers. The method returns true if the item is found in the array, and false if it is not.

public static boolean search(int item, int[] arr) {
    // Always check for null references first!
    if (arr == null) {
        throw new IllegalArgumentException();
    }

    boolean found = false;
    for (int i = 0; i < arr.length && !found; i++) {
        if (arr[i] == item) {
            found = true;
        }
    }

    return found;
}

1. (5 points) In section 1-1 of ps4_partI (see above), rewrite this method so that it searches for an item an array that can contain any type of object. Change the types of the parameters accordingly, and make whatever changes are needed to the body of the method.

2. (10 points) In section 1-2, write a final version of this method. Like your solution to 1-1, this version of the method must search for an item in an array of arbitrary objects, but this version must use recursion instead of iteration. You will need to add a third parameter (call it start) that keeps track of where you are in the array. More precisely, start will specify the position in the array where the search for item should begin. For example, search("hello", arr, 0) should search for “hello” in the full array (beginning at position 0), whereas search("hello", arr, 2) should search for "hello" in the subarray that begins at position 2 and goes to the end of the array.

Problem 2: Using recursion to print an array in reverse order

15 points; individual only

Write a Java method called printReverse() that takes an array of type Object and uses recursion to print the contents of the array in reverse order. The array itself should not be reversed; it must be left in its original form.

Your method should have the following header:

public static void printReverse(Object[] arr, int i )

where arr is a reference to the array, and i is an integer parameter that you may use as you see fit.

You do not need to submit this as a .java source file — simply include your implementation with your other answers in ps4_partI. However, you are encouraged to write and test your solution.

For full credit, your printReverse() method should consider the first element of the array first — i.e., the first call to printReverse() should be the one that prints the first element, the second call should be the one that prints the second element, and so on. Half credit will be given for methods that consider the last element first. In either case, your method must be recursive; no credit will be given for methods that employ iteration.

Part II

70 points total

Problem 3: Set Class: Creating another Custom Data Type

45 points total; individual-only

Overview

In mathematics and computer science, a set is a collection in which order does not matter and there are no duplicates.

In this problem, we are going to to define a class which wil allow us to create an object to represent a set of integers. You will write a program Set.java to define the class Set. Each instance of the class Set will be an object representing a set of integers.

The only method of the class which will be static is the main method, which contains the testing code. All other methods written will be instance methods of the class.

The Set class will represent our sets using integer arrays of arbitrary size (but starting with size 10). The class will also maintain an index (i.e. pointer) next indicating the next available slot in the array:

private static final int SIZE = 10;   // default (inital) size of set
private int[] set;            // array holding the set
private int size;             // current physcal size of set
private int next;             // index of the next available slot in set

Thus, a set [ 2, 3, 7, -3 ] would be represented as follows:

and the empty set [] would be represented as:

The idea is that you can represent a set of up to SIZE integers, and they are stored, without duplicates, in the indices from 0 to next-1.

The Methods of the Set Class

public Set() -- Default constructor; initialize this set as an
   instance of the empty set.

public Set(int[] arr) -- Initialize this set consisting of exactly
   the elements of arr. Note that A is an array and not a set,
   so it may contain duplicate values.
   The array passed can be of arbitrary length (it may or may not be smaller than SIZE).

   (Hint: create an empty set and use insert(...) to add the
   elements, which may trigger a resize of the array.)

public Set clone() -- Return an exact copy of this set (**hint:
   use the previous constructor*).

public String toString() -- Return a string representation of this set,
   e.g., [2,3,7,-3]  or []; you may not use Array.toString(...) to do this;
   you may create a char array from the array S and use the String i
   constructor (which will accept a char array as initializer), or you may
   build up the String one character at a time using concatenation.

public int cardinality() -- Return the number of elements in this set.

public  boolean isEmpty() -- Return true if this is the empty set has
   no members and false otherwise.

public boolean member(int n) -- Return true if n is in the set and false
   otherwise.

   (Hint: where might you want to use this method to help out?)

public boolean subset(Set T) -- Returns true if this set is a subset of T,
   that is, every member of this set is a member of T, and false
   otherwise. (Hint: use member.)

public boolean equal(Set T) --  Returns true if this set and T have
   exactly the same members. (Hint: use subset.)

public void insert(int k) -- If the integer k is a member of the set
   already, do nothing, otherwise, add to the set; if this would cause an
   ArrayOutOfBoundsException, call resize() (provided in template code) to
   increase size of array before doing insertion.

   This method is key to correctly implementing all your other methods
   without duplicating a lot of code!

public void delete(int k) -- If the integer k is not a member, do nothing;
   else remove it from the set; you must shift all elements which occur
   after k in the array to the left by one slot.

public Set union(Set T) -- Return a new set consisting of all of the
   elements of this set and T combined (without duplicates). (Hint: make a
   clone of this set, and insert all elements of T into the clone.)

public Set intersection(Set T) -- Return the intersection of this set and T.
   (Hint: make a new empty set, and for every element of this set, if it
   also occurs in T, insert it into the new set.)

public Set setdifference(Set T) -- Return the setdifference of this set and T.
   (Hint: make a new empty set, and for every element of this set, if it does
   NOT occur in T, insert it into the new set.)

Completing your Solution

Begin by downloading the template: Set.java. As with BigInt, this template will also not compile because of the dummy return statements just for that purpose; again you will need to change these when you add your code to implement the methods as specified above. You can also download the file DriverForSet.java which contains a main program that you can use as a guide to incrementally test the methods of your set class.

Problem 4: Recursion and strings revisited

25 points total; individual-only

In a file named StringRecursion.java, implement the methods described below, and then create a main() method to test these methods.

Here are the methods:

1. public static void printReverse(String str)
   This method should use recursion to print the individual characters in the string str in reverse order. For example, printReverse("Terriers") should print

   sreirreT
   

   The method should not return a value.

   Special cases: If the parameter is null or the empty string (""), the method should not print anything.

2. public static String trim(String str)
   This method should take a string str and use recursion to return a string in which any leading and/or trailing spaces in the original string are removed. For example:

   • trim(" hello world    ") should return the string "hello world"
   • trim("recursion  ") should return the string "recursion"

   The String class comes with a built-in trim() method that does the same thing as the method that we’re asking you to write; you may not use that method in your solution!

   Special cases:

   • If the parameter is null, the method should return null.

   • If the parameter is the empty string, the method should return the empty string.

3. public static int find(char ch, String str)

   This method should use recursion to find and return the index of the first occurrence of the character ch in the string str, or -1 if ch does not occur in str. For example:

   • find('b', "Rabbit") should return 2
   • find('P', "Rabbit") should return -1

   The method should return -1 if the empty string ("") or the value null is passed in as the second parameter. Remember that you may not use any built-in String methods except charAt, length, equals, and substring.

4. public static String weave(String str1, String str2)

   This method should use recursion to return the string that is formed by “weaving” together the characters in the strings str1 and str2 to create a single string. For example:

   System.out.println( weave("aaaa", "bbbb") );
   >> abababab
   
   System.out.println( weave("hello", "world") );
   >> hweolrllod
   

   If one of the strings is longer than the other, its “extra” characters — the ones with no counterparts in the shorter string — should appear immediately after the “woven” characters (if any) in the returned string. For example, weave("recurse", "NOW") should return the string “rNeOcWurse”, in which the extra characters from the first string — the characters in “urse” — come after the characters that have been woven together.

   This method should not do any printing; it should simply return the resulting string. If null is passed in for either parameter, the method should throw an IllegalArgumentException. If the empty string (“”) is passed in for either string, the method should return the other string. For example, weave("hello", "") should return “hello” and weave("", "") should return “”.

5. public static int indexOf(char ch, String str)

   This method should use recursion to find and return the index of the first occurrence of the character ch in the string str, or -1 if ch does not occur in str. For example:

   System.out.println( indexOf('b', "Rabbit") ); 
   >> 2
   
   System.out.println( indexOf('P', "Rabbit") );
   >> -1
   

   The method should return -1 if the empty string (“”) or the value null is passed in as the second parameter. The String class comes with a built-in indexOf() method; you may not use that method in your solution!

Submitting Your Work

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• ensured that the signature of the methods specified in the assignment have not been changed.
• You have verified that your programs satisfy all the performance tests in the templates;

Submitting your work for Part I

Submit your ps4_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download as->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 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.

Submitting your work for Part II

You should submit only the following files:

• Set.java
• StringRecursion.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 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.

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

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