Problem Set 5

due by 11:59 p.m. on Tuesday, March 22, 2022

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 ps5 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 ps5_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 ps5 folder. The resulting PDF file (ps5_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: 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]);
    }
}

1. (5 points) In section 1-1 of ps5_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.

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

3. (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 2: 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)

1. 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 5, Task 2.1-2.2.

   In section 2-1 of ps5_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.

2. 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 5, Task 2.1-2.2 for another example of what this part of your solution should look like.

Problem 3: Sorting practice

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

We will finish our coverage of sorting during the week after spring break.

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

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

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, what would the array look like after the fourth iteration of the outer loop of the algorithm?

3. If the array were sorted using bubble sort, what would the array look like after the second pass of the algorithm?

4. If the array were sorted using the version of quicksort presented in lecture, what would the array look like after the first call to the partition method?

5. If the array were sorted using the version of quicksort presented in lecture, what would the array look like after the second call to the partition method?

6. If the array were sorted using the version of mergesort presented in lecture, what would the array look like after the completion of the third 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 4: Practice with big-O

12 points total; 4 pts. each part; individual-only

1. Determine the appropriate big-O expression for each of the following functions, and put your answer in the table we have provided in section 2-1 of ps5_partI. We’ve included the answer for the first function. (Note: We’re using the ^ symbol to represent exponentiation.)

   1.     a(n) = 5n + 1
   2.     b(n) = 2n^3 + 3n^2 + nlog(n)
   3.     c(n) = 10 + 5nlog(n) + 10n
   4.     d(n) = 4log(n) + 7
   5.     e(n) = 8 + n + 3n^2

2. In the following code fragment, how many times is the count() method called as a function of the variable n? Use big-O notation, and explain your answer briefly.

   for (int i = 0; i < 2*n; i++) {
       for (int j = 0; j < n - 1; j++) {
           count();
       }
   }
   

3. In the following code fragment, how many times is the count() method called as a function of the variable n? Use big-O notation, and explain your answer briefly.

   for (int i = 0; i < 5; i++) {
       for (int j = 0; j < n; j++) { 
           for (int k = n; k > 0; k = k/2) {
               count();
           }
       }
   }
   

Problem 5: Comparing two algorithms

6 points; individual-only

Suppose you want to find the largest element in an unsorted array of n elements. Below are two possible algorithms for doing so:

Algorithm A:

public static int findMaxA(int[] arr) {
    Sort.mergesort(arr);
    return arr[arr.length - 1];
}

Algorithm B:

public static int findMaxB(int[] arr) {
    int largest = arr[0];

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > largest) {
            largest = arr[i];
        }
    }

    return largest;
}

What is the worst-case time efficiency of algorithm A in terms of the length n of the array? What is the worst-case time efficiency of algorithm B? Use big-O notation, and explain your answers briefly.

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 ps5_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your ps5_partI file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps5 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 5: 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 6: Recursion and strings

25 points total; individual-only

Getting started

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

2. In VS Code, 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.

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

4. Select File->Save, and give the new file the name StringRecursion.java.

5. In the new file, create a class called StringRecursion. In that class, implement the recursive methods described below.

6. In addition, we highly recommend adding a main method to your class that makes test calls to your methods.

Here are the methods:

1. public static void printWithSpaces(String str)
   This method should use recursion to print the individual characters in the string str, separated by spaces. For example, printWithSpaces("space") should print

   s p a c e
   

   where there is a single space after the e. The method should not return a value.

   Special cases: If the value null or the empty string ("") are passed in as the parameter, the method should just print a newline (by executing the statement System.out.println();) and return.

2. public static String reflect(String str)
   This method should take a string str and use recursion to create and return a “reflected” version of the string in which the original string is followed by the characters of the string in reverse order. For example:

   • reflect("method") should return "methoddohtem"
   • reflect("abc") should return "abccba"

   This method should not do any printing; it should return the appropriate string.

   Special cases: If the value null or the empty string ("") are passed in as the parameter, the method should just return an empty string.

3. public static int numDiff(String str1, String str2)
   This function should take two strings str1 and str2 and use recursion to determine and return the number of differences between the two strings – i.e., the number of positions at which the two strings have different characters. If one string is longer than the other, all of its extra characters should count as differences. For example:

   • numDiff("alien", "allen") should return 1 because the strings only differ in one position (position 2)
   • numDiff("alien", "alone") should return 3 because the the characters in the last 3 positions of the strings are all different
   • numDiff("same", "same") should return 0 because there are no differences between the two strings!
   • numDiff("same", "sameness") should return 4 because although the first 4 positions of the strings are the same, the second string has an extra 4 characters
   • numDiff("some", "sameness") should return 5 because the strings differ in position 1 and the second string also has an extra 4 characters
   • numDiff("", "abc") and numDiff("abc", "") should both return 3 because one of the strings is empty and thus all of characters in the other string are extra characters

   This method should not do any printing; it should return the appropriate integer. You may assume that neither parameter is null.

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

   • indexOf('b', "Rabbit") should return 2
   • indexOf('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. The String class comes with a built-in indexOf() method; you may not use that method in your solution!

Problem 7: A Letter Square solver

25 points; pair-optional

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.

The New York Times includes a daily puzzle called “Letter Boxed.” It involves a set of 12 letters arranged around the sides of a square, such as the following:

To solve the puzzle, you need to come up with a sequence of English words in which each letter in the puzzle appears at least once. In addition, the words in the sequence must observe the following constraints:

• Each word must be at least 3 letters long.

• Adjacent letters must come from different sides of the square. For example, when solving the puzzle above, if the first letter in a word is T, the second letter in that word cannot be either A or E, since A and E are on the same side of the square as T.

  One word that can be formed from the puzzle above is TIME. I is on a different side of the square than T, M is on a different side than I, and E is on a different side than M.

• The last letter of one word of the sequence must match the first letter in the next word in the sequence. For example, if we use TIME as the first word in our solution, the second word must then begin with E, since TIME ends with E.

For a given puzzle, there are many possible solutions, but solutions that use fewer words are preferred. For the puzzle above, one possible solution is

LIMES
STONES
SHAKY

However, an even better solution is

MILESTONES
SHAKY

because it uses fewer words.

In this problem, you will write a program that solves this type of puzzle using recursive backtracking!

Getting started

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

2. Download the following files:

   • LetterSquare.java
   • Dictionary.java
   • word_list.txt

   Make sure to put all three of them in your ps5 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 ps5 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 names of the files.

Task 1: review the provided code

We have provided:

• a class called LetterSquare that will serve as a blueprint for objects that represent a Letter Square puzzle, and that can be used to solve the puzzle. We have included some starter code, and you will implement two key methods of the class.

• a separate class called Dictionary that serves as a blueprint for a Dictionary object that you can use to check if a string is a word or the prefix of a word in a collection of common English words. You should not modify this class in any way.

• a text file called word_list.txt containing the words in the dictionary.

Begin by reading over the code that we have given you in LetterSquare.java. The provided code includes:

• a constant called dictionary that refers to the Dictionary object described above. The two key methods in this object are:

  • dictionary.hasString(s), which returns true if the string s is either a word or the prefix of a word in the dictionary of words, and false otherwise. For example, because "game" is a word in the dictionary, all of the following calls will return true:

    • dictionary.hasString("g")
    • dictionary.hasString("ga")
    • dictionary.hasString("gam")
    • dictionary.hasString("game")

    However, dictionary.hasString("gome") will return false, because the string `”gome” is neither a word nor the prefix of a word in the dictionary.

  • dictionary.hasFullWord(s), which returns true if the string s is a “full word” (i.e., a word that can stand on its own, and is not only a prefix) in the dictionary of words, and false otherwise. For example:

    • dictionary.hasFullWord("game") will return true, because "game" is a full word in the dictionary.

    • dictionary.hasFullWord("g"), dictionary.hasFullWord("ga"), and dictionary.hasFullWord("gam") will all return false, because these strings are not full words in the dictionary.

• a field called sides that refers to an array of strings. It is used to store the letters on each side of the puzzle, with each side represented by a three-letter string. For example, the sides of the puzzle above would be stored as the following array:

  {"tae", "nih", "omk", "lys"}
  

  (Either lower-case or upper-case characters can be used.)

• a field called letters that refers to an array of single-letter strings. This array is used to store the individual letters in the puzzle. For example, the letters in the puzzle above would be stored as the following array:

  {"t", "a", "e", "n", "i", "h", "o", "m", "k", "l" , "y", "s"}
  

  (Note: We are using an array of String objects, not an array of char values. Doing so simplifies some of the necessary constraint-checking. In particular, it allows us to use the built-in contains method from the String class to determine if a given letter is found within a given string.)

• a field called words that refers to an array of strings. It will be used to store the words in the solution to the puzzle. When the LetterSquare object is created, this array is initially filled with empty strings.

• a constructor that takes an array representing the sides of the puzzle and initializes the fields.

• a toString method that returns a string representation of the puzzle that will be used when you print a LetterSquare object.

• private static helper methods that make it easier to perform two types of operations on String objects:

  • one called lastLetter(word) that can be used to obtain a single-letter string consisting of the last letter in the string word; for example, lastLetter("world") would return the string "d".

  • one called removeLast(word) that takes a string word and returns the new string formed by removing the last letter in word; for example, removeLast("world") would return the string "worl".

• a private method called addLetter that takes a single-character string letter and an integer wordNum, and that adds the specified letter to the end of the word in position wordNum of the words array.

• a private method called removeLetter that takes an integer wordNum and that removes the last letter from the word in position wordNum in the words array.

• a private method called alreadyUsed that takes an arbitrary string word and that returns the boolean value true if word is already one of the words in the solution, and false otherwise.

• a private method called onSameSide that takes two single-character strings letter1 and letter2, and that returns true if letter1 and letter2 are on the same side of the puzzle, and false otherwise.

• a private method called allLettersUsed that returns the boolean value true if all of the letters in the puzzle have been used somewhere in the solution, and false otherwise.

• a private method called printSolution that takes an integer wordNum and prints the words in positions 0 through wordNum of the words array.

• the skeleton of a private method called solveRB that you will implement. This is the recursive-backtracking method, and it should return true if a solution to the puzzle has been found and false if no solution has been found (i.e., if the method is backtracking).

  This method must take three integer parameters:

  • wordNum: the index of the position in the words array of the word that is currently being built

  • charNum: the index of the character within the current word that this call is responsible for adding

  • maxWords: the maximum number of words that the solution is allowed to have.

• the skeleton of a private method called isValid that you will also implement. This method should be called by solveRB to check if a given letter would work as the next letter in the current word, given the words and prefixes in the dictionary and the constraints of the puzzle described at the beginning of the problem.

  This method must take three parameters:

  • letter: a single-character string representing the letter whose validity is being tested

  • wordNum: an integer specifying the index of the position in the words array of the word that is currently being built

  • charNum: an integer specifying the index of the position within the current word that letter is being considered for.

  It should return true if the specified letter is a valid choice for the letter in position charNum of the word in position wordNum of the words array, and false otherwise. You may assume that only appropriate values will be passed in. In particular, you may assume that letter is one of the letters of the puzzle.

• a public method named solve that clients can call to solve a LetterSquare puzzle. It repeatedly calls solveRB with increasing values of maxWords until it finds a solution to the puzzle, or until it has tried and failed to find solutions of up to 10 words.

• a main method that allows the user to enter and solve a puzzle.

The only methods that you should change are solveRB and isValid. All of the other provided methods should be left unchanged. You are welcome to add your own additional helper methods, although doing so is not required.

Task 2: implement solveRB and isValid

Once you have reviewed the provided code, you can begin to implement the bodies of the two methods that you are required to write. You should not change the headers that we have provided.

The recursive-backtracking method (solveRB) should follow the same basic approach as the recursive-backtracking template from lecture (the one designed to find a single solution). However, there will be a couple of key differences:

• In addition to a base case that checks if the puzzle has been solved, you will need a second base case for calls in which wordNum is too big, given the value of maxWords. For example, the call this.solveRB(3, 0, 3) should return false, because if maxWords is 3, we shouldn’t be looking for a fourth word (which is what a first input of 3 indicates).

• If the current call is able to add a letter to the solution, you may need to make two separate recursive calls:

  • First, you should make a call that attempts to expand the current word in the solution, making it one letter longer.

  • Then, if the first recursive call does not succeed in finding a solution and if the current word in the solution is a full word of at least three letters, you should make a second recursive call that moves on to the next word in the solution.

  For example, let’s say that the call this.solveRB(0, 3, 2) adds the letter e to position 3 of the first word in the solution, giving us the string "time" as that first word.

  • First, we would make the call this.solveRB(0, 4, 2) to see if we can expand "time" into a longer word.

  • Then, if the first call returns false, we would check if "time" is a full word of at least 3 letters. Because it is, we would make the call this.solveRB(1, 0, 2) to move onto the second word in the solution (the one in position 1 of the words array). Note that we also use a 0 for the second input of this call, since the call will be focused on the first letter in that new word.

  Note that you should only make a second recursive call if the first call returns false and the current word is a full word of at least three letters.

When implementing the isValid method, the constraints that you need to check will depend on the value of the charNum parameter (and possibly also of the wordNum parameter).

For example, let’s assume that we have the following situation:

• We are solving the puzzle shown at the start of the problem (the one with sides {"tae", "nih", "omk", "lys"}).

• We are looking for a solution of at most 2 words.

• The current partial solution is {"time", ...}.

• We are within the call this.solveRB(0, 4, 2) – i.e., we are attempting to expand the word in position 0 ("time") by finding a letter that would work in position 4 of that word.

Given this situation:

• this.isValid("l", 0, 4) should return true because "l" is on a different side of the puzzle than "e" (the letter that was added to give "time") and "timel" is a word and/or a prefix of a word in the dictionary (which we know because dictionary.hasString("timel") returns true)

• this.isValid("s", 0, 4) should also return true because "s" is on different side of the puzzle than "e" and dictionary.hasString("times") returns true

• this.isValid("a", 0, 4) should return false because "a" is on the same side of the puzzle as "e"

• this.isValid("y", 0, 4) should return false because "timey" is neither a word nor a prefix of a word in the dictionary (which we know because dictionary.hasString("timey") returns false).

Now imagine that we have added the letter "s" to the partial solution described above to give a new partial solution {"times", ...} and that we are now focused on the first letter in second word in the solution (i.e., that we are within the call this.solveRB(1, 0, 2)). Given this situation:

• this.isValid("s", 1, 0) should return true because we are focused on the first letter in a new word and "s" is the last letter of the previous word ("times")

• this.isValid("l", 1, 0) should return false because we are focused on the first letter in a new word and "l" is not the last letter of the previous word.

Other notes:

• Make sure that you use the addLetter() and removeLetter() methods when updating the state of the puzzle.

• In addition, take advantage of the other helper methods that we have provided – including the hasString and hasFullWord methods in the Dictionary object given by the class constant dictionary.

• When implementing isValid, you will need a special case for handling the first character of the first word in the solution. In that case, any letter of the puzzle is valid!

• When isValid is considering a case in which the current word is being expanded by one letter, it should return false if adding the letter would produce a word that is already part of the solution. Otherwise, you could end up producing a solution that repeatedly uses the same word (e.g., {"toast", "toast", ...}). Note that we have given you a helper method that makes it easy to check for this case!

• isValid should only determine if the specified letter is a valid choice for the next letter. It should not actually add the letter to the solution.

Task 3: test your code

Below are some other puzzles that you can use for testing. (In each case, we specify the four sides of the puzzle, separated by commas. You should enter them one at a time, without the commas!)

1. puv, rce, otl, diy
   This has a single-word solution: productively

2. puv, rce, otl, dix
   This has a two-word solution:

   productive
   expel
   

3. abc, def, ghi, jkl
   The shortest possible solution is one of length 6:

   jibe
   eagle
   elf
   fleck
   kea
   ahead
   

Depending on how you implement the methods, you may end up with different solutions than the ones shown above. However, you should still end up with a solution that has the same number of words as our solution.

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.

You should submit only the following files:

• StringRecursion.java
• LetterSquare.java

In addition, 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.