Problem Set 3 — CS 112, Boston University CS 112 Summer-I 2022 Home Syllabus Schedule Lectures Labs Problem Sets Staff Office Hours Resources Collaboration Policies Blackboard Piazza Gradescope Problem Set 3 due by 11:59 p.m. on Sunday, June 12, 2022 Preliminaries Part I Creating the necessary folder Creating the necessary file Problem 1: A class that needs your help Problem 2: Static vs. non-static Problem 3: Understanding and using inheritance Problem 4: Inheritance and polymorphism Problem 5: Memory management and the ArrayBag class Problem 6: Using recursion to print an array Problem 7: A method that makes multiple recursive calls Submitting your work for Part I Part II Programming Problems Problem 8: Set Class: A Custom Data Type to represent a set of integers Problem 9: Recursion and strings revisited Problem 10: Recursion and Arrays Submitting Your Work for Part II 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 instructor. Make sure to follow the instructions outlined at the end of Part I and Part II when submitting your assignment. Part I 80 points total Creating the necessary folder If you haven’t already created a folder named cs112 for your work in this course, follow these instructions to do so. Then create a subfolder called ps3 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: Access the template that we have created by clicking on this link and signing into your Google account as needed. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive. Select File->Rename, and change the name of the file to ps3_partI. Add your work for the problems from Part I to this file. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps3 folder. The resulting PDF file (ps3_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I. Problem 1: A class that needs your help 10 points total; individual-only Consider the following class, which is intended to serve as a blueprint for objects that encapsulate two pieces of data: an odd integer and a positive real number: public class ValuePair {
int a;
double b;
public double product() {
return this.a * this.b;
}
}
(6 points) This class does not employ appropriate encapsulation. In section 3-1 of ps3_partI, revise the class to prevent direct access to the internals of a ValuePair object while allowing indirect access through appropriate methods. Your revised version should include: whatever steps are needed to prevent direct access to the fields accessor methods that can be used to obtain the value of each field mutator methods that can be used to change the value of each field. These methods should ensure that a is always odd, and that b is greater than 0.0. Attempts to assign an invalid value should produce an IllegalArgumentException. a constructor that takes values for a and b and initializes the fields using those values. Attempts to assign an invalid value should produce an IllegalArgumentException. Take advantage of the error-checking code that is already present in the mutator methods that you defined for changing the values of the fields. No other methods are required. (4 points) Now imagine that you’re writing client code for your revised ValuePair class – i.e., code in a different class that uses ValuePair objects. For each of the following tasks, write a single line of client code to accomplish the task: Construct a ValuePair object for the pair (7, 15.5), and assign it to a properly declared variable named vp1. Change the integer value in the ValuePair object that you created in part (a), giving it a value of 25. You should not create a new object; you should change the internals of the existing object. Important: As a result of your changes from part 1, clients no longer have direct access to the fields in a ValuePair object. As a result, you will need to make a method call to change the appropriate field. Get the real-number value in the ValuePair object that you created in part (a), and assign it to a properly declared variable named b1. Here again, you will need to make an appropriate method call. Now imagine that you are given a second ValuePair object that has been created by someone else and that has been assigned to the variable vp2. Change the integer value in vp2, giving it a value that is 2 more than its current value. Problem 2: Static vs. non-static 10 points total; individual-only When designing a blueprint class, we have seen that we can include both static and non-static variables. Static variables (also known as class variables) belong to the class as a whole. Non-static variables (also known as instance variables or fields) belong to individual objects of the class; each object gets its own copy of those variables. We have also seen that a blueprint class can include both static and non-static methods. A non-static method (also known as an instance method) is required if the method must have access to the fields of a particular called object. However, if a method doesn’t need a called object – i.e., if all of the information that it needs is supplied by its parameters or by the static variables of the class – then we typically make it static. In the same way that static variables are also known as class variables, static methods are sometimes referred to as class methods. Whether a method is static or non-static has an impact on how we call it. Non-static methods must be called on an object of the class (e.g., r1.area(), where r1 is a reference to a Rectangle object). Static methods may be called on an object of the class, but it is better style to call them using the name of the class instead. Imagine that we are defining a class called Grade that will serve as a blueprint for objects that encapsulate the raw score and the possible late penalty associated with a given grade. For example, to create a Grade object that represents a grade with a raw score of 85.5 and a late penalty of 20%, we would write: Grade g = new Grade(85.5, 20);
An initial implementation of this class can be found here. (4 points) Imagine that we want to modify the existing Grade class so that each Grade object has an associated category — a String that is either "assignment", "quiz", or "exam". In addition, we want to keep track of how many Grade objects have been created for each of the three categories. What variables (static and/or non-static) would we need to add to the Grade class as part of our implementation of these changes? In section 3-2 of ps3_partI, we have included a table that you should complete to describe the necessary variables. For each of your proposed variables, you should specify: its type and name (make it descriptive!) whether it will be static or non-static a brief description of its purpose, and why it needs to be static or non-static. As an example, we have filled in the first row of the table to describe the existing rawScore field. You should add the descriptions of your proposed new variables. You may not need all of the rows in the table. (2 points) Now let’s say that we want to add a method called setCategory that takes in a category string and uses it to change the category of the called Grade object. What type of method should setCategory be — static or non-static? Explain briefly. Assume we have a Grade object whose current category is "quiz". The professor who assigned the grade has decided to make the associated test worth more, so we need to call setCategory to change the grade’s category to "exam". During that method call, what changes will the method need to make to the values of the variables that you proposed above? Be as specific as possible. The remaining sections of this problem consider two other new methods for the Grade class – methods that do not involve the grade’s category. (2 points) Now let’s say that we want to add a method called waiveLatePenalty. It takes no parameters, and it sets the late penalty of a Grade object to 0. What type of method should waiveLatePenalty be — static or non-static? Explain briefly. Give an example of how you would call this method from outside the Grade class. If you need a Grade object to call the method, assume that the variable g represents that object, and that the object has already been created. However, you should only use g if doing so is absolutely necessary. (2 points) Finally, let’s say that we want to add a new method called computeRaw. It takes two parameters — a double called pct and an int called possiblePoints — and it computes and returns the raw score that would be obtained if a student earned pct percent of the points represented by possiblePoints. In other words, it converts a percentage grade to a raw score. For example, if pct is 80.0 and possiblePoints is 50, the method should return 40.0, because 40 is 80 percent of 50. What type of method should computeRaw be — static or non-static? Explain briefly. Give an example of how you would call this method from outside the Grade class. If you need a Grade object to call the method, assume that the variable g represents that object, and that the object has already been created. However, you should only use g if doing so is absolutely necessary. Problem 3: Understanding and using inheritance 10 points total; individual-only Imagine that you wanted to capture information about a collection of different types of vehicles (cars, trucks, motorcycles, etc.). To do so, you could use inheritance to create a collection of related classes whose inheritance hierarchy looks like this: We have provided an implementation of most of these classes in this folder, and we encourage you to review the provided files. They include: a class called Vehicle that defines the state (fields) and behavior (methods) that are common to all vehicles; it does not explicitly extend another class a class called Motorcycle that can be used to create objects that represent motorcycles; it inherits all of its fields and methods from Vehicle, with the exception of its own constructor a class called Automobile that can be used to create objects that represent cars; it also inherits fields and methods from Vehicle, but it adds some new fields and methods that are only needed by cars, and it overrides the inherited toString() method with its own version a class called Truck that can be used to create objects that represent trucks; it also inherits fields and methods from Vehicle, but it adds some new fields and methods that are only needed by trucks, and it overrides the inherited toString() method with its own version a class called Taxi that can be used to create objects that represent cars; it inherits its fields and methods from Automobile, but it adds some new fields and methods that are only needed by taxis, and it overrides the inherited toString() method with its own version a class called TractorTrailer that can be used to create objects that represent tractor trailors; it inherits its fields and methods from Truck, but it adds some new fields and methods that are only needed by tractor trailers, and it overrides the inherited getNumAxles() method with its own version. The hierarchy diagram above includes a Limousine class and a MovingVan class, but we have not defined those classes yet. In the appropriate section of your ps3_partI document (see above), answer the following questions: (1 point) Which of the classes that are shown in the diagram above are a superclass of the TractorTrailer class? (1 point) If we have a TractorTrailer object that has been assigned to a properly declared variable t, is it possible to make the following call? t.getMileage()
Explain briefly why or why not. Write a definition for the Limousine class that takes full advantage of inheritance. A Limousine object should have all of the same state and behavior as an Automobile object. In addition, it should maintain additional state that keeps track of: whether the limousine has a sun roof (true or false) how many bottles of champagne it can chill (a non-negative integer) When a Limousine object is printed, we should see its make, its model, and the number of seats available to customers, which is two fewer than the total number of seats. For example, if the Limousine is a Cadillac XTS-L with a total of 8 seats, printing it should produce the following output: Cadillac XTS-L (seats up to 6 customers)
Note that the output mentions 6 seats, because only 6 of the 8 seats are available for customers. In your ps3_partI file, add a definition of this class that includes the following: (1 point) a class header that sets up the appropriate inheritance (2 points) whatever new fields are needed to capture the state of a Limousine object. Make sure that you take inheritance into account when deciding which fields to include. (2 points) a constructor that takes as parameters the make, model, year, and total number of seats, as well as a boolean value indicating whether the limo has a sun roof and an integer indicating how many bottles of champagne it can chill. The constructor should ensure that the object is not put in an invalid state (throwing an exception as needed), and it should take whatever steps are needed to initialize the object. (3 points) any necessary methods. It should be possible for a client to obtain the value of any of the fields, and to change the value of any field that can be changed in an Automobile object. However, you should assume that the portion of the state specifying whether there is a sun roof and how many champagne bottles can be chilled will never change, and thus mutator methods are not needed for those fields. You also don’t need to define an equals method for this class. Problem 4: Inheritance and polymorphism 18 points total; individual-only Imagine that you have a set of related classes that have been defined using inheritance. Here are the key facts about these classes: Class Zoo doesn’t explicitly extend a class (i.e., it doesn’t have an extends clause in its class header). Its class members (i.e., its fields and methods) include: an integer field called a a String field called b a non-static method called one() that takes an integer and returns a double a non-static method called two() that takes no inputs and returns an integer its own equals() method that overrides the inherited one. Class Woo extends Zoo. In addition to the members that it inherits, it has: integer fields called x and y its own method called two() that overrides the inherited one its own toString() method that overrides the inherited one. Class Too extends Zoo. In addition to the members that it inherits, it has: integer fields called t and u its own method called two() that overrides the inherited one its own method called three() that takes a double and returns a boolean an equals() method that overrides the inherited one. Class Yoo extends Woo. In addition to the members that it inherits, it has: a String field called c its own method called one() that overrides the inherited one. In addition, you should make the following assumptions: All of the classes employ appropriate encapsulation. Each class has a constructor that takes no parameters and initializes the newly created object’s fields with their default values. Each class includes an appropriate accessor method for each field that is declared in that class. For example, the Zoo class would have accessor methods called getA() and getB(). Each class includes an appropriate mutator method for each field that is declared in that class. For example, the Zoo class would have mutator methods called setA() and setB(). Answer the following questions in light of the above information about these classes. Before you begin, you may find it helpful to draw an inheritance hierarchy for the classes, although doing so is not required. (2 points) The information above states that the Zoo class has its own equals() method that overrides the inherited one. Where does the equals() method that Zoo overrides come from? Be as specific as possible, and explain your answer briefly. (2 points) List all of the fields in a Yoo object – both the ones that it declares and the ones (if any) that it inherits. (5 points) Consider the following code fragment: Yoo y1 = new Yoo();
System.out.println(y1.one(10));
System.out.println(y1.two());
System.out.println(y1.three(12.5));
System.out.println(y1.equals(y1));
System.out.println(y1);
Each of the println statements in this code fragment displays the result of a method call. (This includes the fifth println statement, in which the Java interpreter calls a method on our behalf.) However, it is possible that one or more of these methods calls would fail to compile because the necessary method is neither defined in the Yoo class nor inherited from a superclass of Yoo. In the appropriate section of ps3_partI, we have included a table that you should complete with appropriate information about each of these method calls. We have filled in the first row for you, and you should complete the remaining rows. (3 points) Now imagine that you want to add a non-static method to the Too class. It should be called avg(), it should take no parameters, and it should return the average of all of the integer fields in the called Too object. Add a full definition of that method to the appropriate section of your ps3_partI file. Make sure to take into account the fact that the classes employ proper encapsulation. Make the average as precise as possible. (6 points) For each of the following assignment statements, indicate whether it would be allowed according to the rules of polymorphism, and explain briefly why or why not. Woo w = new Too(); Zoo z = new Woo(); Zoo z = new Yoo(); Too t = new Zoo(); Problem 5: Memory management and the ArrayBag class 12 points total; individual-only In this problem, you will draw a series of memory diagrams that illustrate the execution of a program that operates on objects of the ArrayBag class from lecture. Consider the following Java program: public class ArrayBagTest {
public static void main(String[] args) {
ArrayBag b1 = new ArrayBag(3);
ArrayBag b2 = new ArrayBag(3);
ArrayBag b3 = b2;
// part 1: what do things look like when we get here?
// part 2: what do things look like at the start of
// this method call?
b1.add("hello");
b2.add("world");
b3.add("hello");
// part 3: what do things look like when we get here?
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
}
}
In the appropriate section of ps3_partI, we have given you the beginnings of a memory diagram. On the stack (the region of memory where local variables are stored), we have included a frame for the main method. On the heap (the region of memory where objects are stored), we have included the ArrayBag object to which the variable b1 refers and its items array. As usual, we have used arrows to represent the necessary references. Complete the provided memory diagram so that it shows what things look like in memory just before the call b1.add("hello"). To do so, you should: Click on the diagram and then click the Edit link that appears below the diagram. Make whatever changes are needed to the diagram. Below the thick horizontal line, we have given you a set of extra components that you can use as needed by dragging them above the thick line and putting them in the correct position. These components include String objects representing the strings "hello" and "world". You may not need all of the provided components. You can also edit any of the values in a field or array by clicking on the corresponding cell and editing the text that is inside the cell. Once you have made all of the necessary changes, click the Save & Close button. In the appropriate section of ps3_partI, we have given you the beginnings of a memory diagram that you should complete to show what things look like in memory at the start of the execution of b1.add("hello")—just before the first statement of that method is executed. Note: To save time, it should be possible to select and copy some of the components of your diagram for 3-1 and paste them into your diagram for 3-2. In the appropriate section of ps3_partI, we have given you the beginnings of a memory diagram that you should complete to show what things look like in memory after all of the calls to add have returned—just before the print statements execute in main(). Note: We have included a method frame for add, but it may or not be needed in this diagram; you should delete it if you determine that it would no longer be present in memory. What would be printed by this program? You may find it helpful to consult the toString method of the ArrayBag class. Problem 6: Using recursion to print an array 10 points; individual-only Consider the following method, which uses iteration (a for loop) to print the integers stored in the array arr “vertically”, one number per line: public static void print(int[] arr) {
// Always check for null references first!
if (arr == null) {
throw new IllegalArgumentException();
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
(5 points) In the appropriate section of ps3_partI (see above), rewrite this method so that it uses recursion instead of iteration. You will need to add a second parameter (call it start) that keeps track of where you are in the array. More precisely, start will specify the start of the portion of the array that the current call is focused on. For example, to print the entire array arr, a client would make the call print(arr, 0). To print the portion of the array that begins at position 3, a client would make the call print(arr, 3). If start is negative, the method should throw an IllegalArgumentException. If start is too big given the length of the array, the method should simply return without printing anything. (4 points) Now write a method that uses recursion to print an array of integers arr in reverse order – from the end of the array back to the beginning – one value per line. For example, if arr represents the array {2, 5, 7, 4, 1}, the method should print: 1
4
7
5
2
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(int[] arr, int i)
where arr is a reference to the array, and i is an integer parameter that you should use as you see fit. For full credit, your printReverse() method should consider the first element of the array first — i.e., the first call toprintReverse() 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. (1 point) Based on your implementation of printReverse, what is the initial call that a client would make to print the entire array arr in reverse order? Problem 7: A method that makes multiple recursive calls 10 points; individual-only A number of the algorithms that we consider in CS 112 involve recursive methods in which a given invocation of the method may make two or more recursive calls. To understand how this type of algorithm works, it helps to draw a call tree for a given set of initial parameters. In this problem, you will draw such a call tree to illustrate the execution of a simple recursive method that operates on integers. You may find it helpful to review our solutions to the similar problem in Lab 5 problem before continuing. Here is the method you will trace: public static int foo(int x, int y) {
if (y == 1) {
return x + 1;
} else if (x >= y) {
return y + 2;
} else {
int result1 = foo(x - 1, y - 2);
int result2 = foo(x + 1, y - 1);
return result1 + result2;
}
}
Assume that we begin with the following initial call to this method: foo(4, 7)
Construct a call tree that shows each invocation of the method, and that uses lines to connect a given invocation to the recursive calls that it makes (if any). Follow the same format that we use in our solutions for Lab 3. In the appropriate section ps3_partI, we have given you an initial diagram. You should take the following steps to complete it: Add each subsequent call with its parameters to the call tree in the appropriate place. If a given call is a base case, simply put its return value under the call, as we do in our Lab 5, Task 2 solution for calls to fib(1) and fib(0). If a given call is not a base case, use lines composed of / or \ characters to connect the call to the recursive call(s) that it makes. Precede each call with a number that indicates the overall order in which the calls were made. Underneath your call tree, list the order in which the calls return, as well as their return values. When you refer to a given call in this part of the problem, use its number from the call tree. For example, the initial call always returns last, so the last line in this part of the problem should look like this: call 1 (foo(4,7)) returns ...
where you replace the ... with its return value. See our solution for Lab 3 for another example of what this part of your solution should look like. 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 ps3_partI.pdf file using these steps: If you still need to create a PDF file, open your ps3_partI file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps3 folder. Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 112. Click on the name of the assignment (PS 3: 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.) 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. 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. 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. Important It is your responsibility to ensure that the correct version of every file is on Gradescope before the final deadline. We will not accept any file after the submission window for a given assignment has closed, so please check your submissions carefully using the steps outlined above. If you are unable to access Gradescope and there is enough time to do so, wait an hour or two and then try again. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs112-staff@cs.bu.edu Part II Programming Problems 20 points total Problem 8: Set Class: A Custom Data Type to represent a set of integers 5 points total; This is the only problem of the assignment 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. Overview In mathematics and computer science, a set is a collection in which order does not matter and there are no duplicates. There are several well-defined operations which can be performed on sets, namely: union, intersection, and difference. Additionally, when working with sets you often want to know the cardinality of the set, whether or not it is an empty set, and whether one set is a subset of another set. Example, given two sets A and B: A = {5,4,3,2,1}
B = {3,2,7,9}
A union B = {5,4,3,2,1,7,9}
A intesection B = {3,2}
A difference B = {5,4,1}
B difference A = {7,9}
{} is the empty set
{3,4,5} is a subset of {1,2,3,4,5} because all the elements in the first set exist in the second
{3,4,5,6} is not a subset of {1,2,3,4,5} because the element 6 of the first set is not int the second set
In this problem, you are gong to write a class named Set which will allow us to create an object to represent a Set of integers. Each instance of the class will represent one Set and the integers that make-up the set (i.e. the elements of the set) will be stored in an array of type int. You will also implement as methods all the operations that can be performed on sets. These are the members that need to be declared in your Set class. The array that stores the elements of the set should be initially created using the default SIZE static variable. However, as elements are added to the set, you can use the resize method (which has been provided) to grow the array to store additional elements. 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: Do not confuse the static variable SIZE and the data member size. The first is a class level variable used to create the initial array set. As a final variable, the value will remain fixed. The latter is an instance variable and indicates the physical size of the array set. The instance variable size will be initialized to the class level variable when the set is first created, however, the value of this variable can change if the array is resized to allow for more elements to be added to the set. Also do not confuse size with next. The member size will only change when the array is resized. The member next will increment as a new element is added to the set. The cardinality of the set is represented by member next, and the total number of elements that the set can hold is represented by member size. The idea is that you can represent a Set of up to size integers, and they are stored in the array set, without duplicates, in the indices from 0 to next-1. The cardinality of the set is reprsented by variable next. The Methods of the Set Class public Set() -- No argument constructor; initialize this set as an
instance of the empty set.
public Set(int[] arr) -- Initialize this set consisting of exactly
the elements of the array arr. Note that the array referenced by
arr may contain duplicate values, but the array representing the
set should not. The array passed can be of arbitrary length
(i.e. it may or may not be smaller than SIZE). Therefore,
you may need to *grow* the set to store all the elements.
public Set clone() -- Return an exact copy of this set
(Hint: Consider how you can use the previous constructor to help.)
public String toString() -- Return a string representation of this set,
e.g., [2,3,7,-3] or [] for the empty set;
you may not use `Array.toString` to do this, you must build the
resulting string.
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: consider how you can use this method to help simplify your
implementation of other methods.)
public boolean subset(Set S) -- Returns true if this set is a subset of S,
that is, every member of this set is a member of S, and false
otherwise.
public boolean equal(Set S) -- Returns true if this set and S have
exactly the same members.
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.
(Hint: This method is key to correctly implementing all many of the 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 S) -- Return a new set consisting of all of the
elements of this set and S combined (without duplicates). Example:
public Set intersection(Set S) -- Return a new set consisting of the elements
that are common to both this set and S (without duplicates). Example:
public Set setdifference(Set S) -- Return a new set consistng of all the
elements of this set that are not present in S.
Completing your Solution Begin by downloading the template: Set.java. This template has most of the methods commented out. Begin by implementing the constructors and any other method which may help you correctly insert new elements into the set. You can uncomment each method one at a time as you implement it. 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. Notes and Guidelines: Do not alter the variables that have been declared in the starter file. The values from next to set.length-1 do not matter – they do not need to be 0. The methods union, intersection and difference should make and return new sets, and NOT modify the input sets in any way! The methods insert and delete are mutator methods and will modify the set. Look for opportunities to reuse your own code by implementing methods by using other, simpler methods. For example, equals can be implemented simply (one line of code) using two calls to subset, and setdifference is VERY similar to intersection! We will be using array resizing to handle the problem of overflow – A method resize() has been provided in the template and specified when it should be used (in insert). Use the method descriptions above as a guide to write a comment block before each of the methods. You may add tests to the main method as you develop your code, but remove them before submission. Remove any debugging code in the methods specified above before submission. Do not alter the signature of the methods or they may fail the automatic test. You should examine the method stubs and write appropriate code to implement the functionality described above. Problem 9: Recursion and strings revisited 5 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. Important guidelines The methods that you write must be purely recursive. The use of iteration (i.e., for, while, or do-while loops) is not allowed. The only built-in String methods that you may use are charAt, length, equals, and substring. No use of other String methods is allowed. In addition, make sure to follow any additional restrictions specified in the problem. Do not use any static variables — i.e., variables that are declared outside of a method. Use the headers specified for the methods without changing them in any way. Limit yourself to writing the methods specified below. Do not write any additional “helper” methods that assist the required methods; rather, the methods listed below should provide all of their required functionality by themselves. Here are the methods: 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. 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. 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. 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 “”. 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! Problem 10: Recursion and Arrays 10 points total; individual-only In a file named ArrayRecursion.java, implement the methods described below, and then create a main() method to test these methods. Important guidelines The methods that you write must be purely recursive. The use of iteration (i.e., for, while, or do-while loops) is not allowed. The only built-in String methods that you may use are charAt, length, equals, and substring. No use of other String methods is allowed. In addition, make sure to follow any additional restrictions specified in the problem. Do not use any static variables — i.e., variables that are declared outside of a method. Use the headers specified for the methods without changing them in any way. Limit yourself to writing the methods specified below. Do not write any additional “helper” methods that assist the required methods; rather, the methods listed below should provide all of their required functionality by themselves. Here are the methods: (4 points) Consider the following method, which uses iteration (a for loop) to search for an item of type int 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;
}
Rewrite this method so that it uses recursion instead of iteration to search for an item which can be of any reference type (i.e. String, Integer, etc) in an array of said reference types. You will need to add a third parameter (i.e. 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 with each recursive call. 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. The method header should be: public static boolean search(_______ item, _______[] arr, int start)
(6 points) Write a Java method called reverseArrayToString() that uses recursion to create a string of all the elements in an array, but in reverse order. The elements of the array itself should not be reversed; it must be left in its original form. Your method should have the following header: public static String reverseArrayToString(________[] arr, int index )
where arr is a reference to the array, and index is an integer parameter that you may use as you see fit. The method should create and return a string representation of all the elements of the array but in reverse order. It is important that the string is created to show the elements in proper array form. For example: String a[] = { "abc", "def", "ghi", "klm", "nop", "qrs" };
System.out.println(reverseArrayToString(a, 0));
should produce the output: [qrs, nop, klm, ghi, def, abc]
If a null value is passed to the method instead of a valid reference to an array, the method should return the empty string. Submitting Your Work for Part II Note: There are separate instructions at the end of Part I that you should use when submitting your work for that part of the assignment. Pair-optional problem If you chose to work on Problem 8 with a partner, both you and your partner should submit your own copy of your joint work, along with your individual work on Problem 4. You should submit only the following files: Set.java StringRecursion.java ArrayRecursion.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: Login to Gradescope as needed by clicking the link in the left-hand navigation bar, and then click on the box for CS 112. Click on the name of the assignment (PS 3: 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.) 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. Click the Upload button. You should see a box saying that your submission was successful. Click the (x) button to close that box. 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. 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. 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. Important It is your responsibility to ensure that the correct version of every file is on Gradescope before the final deadline. We will not accept any file after the submission window for a given assignment has closed, so please check your submissions carefully using the steps outlined above. If you are unable to access Gradescope and there is enough time to do so, wait an hour or two and then try again. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs112-staff@cs.bu.edu Last modified on June 6, 2022.
