Problem Set 2

due by 11:59 p.m. on Sunday, February 10, 2019

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

32 points total

This part of the assignment consists of a series of short-answer questions. You will be able to check your answers to at least some of these questions by writing your own programs, but we encourage you to try answering them on your own and convincing yourself of the correctness of your answers before you attempt to test them in programmatically. These questions are similar to ones that could appear on the midterms and final exam, which you will have to take without the use of a computer!

Problem 1: Memory management and arrays

16 points; individual-only

Put all of your work for this problem in a plain-text file named ps2pr1.txt.

In this problem, you will draw a series of diagrams that illustrate the execution of a simple program that operates on arrays. We worked on a similar problem in Lab 2, and you may find it helpful to review our solutions to that problem before continuing. We will also use a similar memory diagrams in our discussion of the ArrayBag class.

Consider the following Java program:

public class ArrayTest {
    public static void foo(int[] a, int[] b) {
        // part 2: what do things look like when we get here?
        int[] c = {3, 5, 7, 9};
        a = c;
        for (int i = 0; i < b.length; i++) {
             b[i] = a[i];
        }
        // part 3: what do things look like when we get here?
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 8};
        int[] b = new int[a.length];
        int[] c = b;

        // part 1: what do things look like when we get here?
        foo(a, b);
        // part 4: what do things look like when we get here?

        System.out.println(a[2] + " " + b[2] + " " + c[2]);
    }
}

1. Construct a single memory diagram that shows what things look like in memory just before the call to foo(). Include both the stack and the heap in your diagram. Begin by copying the following template into your text file, and then use text characters to complete the diagram.

       stack        |     heap
   +------------+
   | main       |
   |   +----+   |          +---+---+---+---+
   | a |  --|---+--------->| 2 | 4 | 6 | 8 |
   |   +----+   |          +---+---+---+---+
   |            |
   |   +----+   |
   | b |    |   |
   |   +----+   |
   |            |
   |   +----+   |
   | c |    |   |
   |   +----+   |
   +------------+
   

2. Construct a single memory diagram that shows what things look like in memory at the start of the execution of foo() – just before its first statement is executed. Include both the stack and the heap in your diagram.

3. Construct a single memory diagram that shows what things look like in memory at the end of the execution of foo() – just before it returns. Include both the stack and the heap in your diagram.

4. Construct a single memory diagram that shows what things look like in memory after the call to foo() has returned – just before the print statement executes in main().

Problem 2: Understanding code that uses an array

8 points total; individual-only

Open up a text editor (e.g., Notepad or TextEdit) and create a plain-text file named ps2pr2.txt. Put all of your work for this problem in that file.

1. (3 points) What is the output of the following lines of code?

   int[] a = {3, 6, 9, 12, 15};
   int[] b = {3, 6, 9, 12, 15};
   int[] c = b;
   c[3] = 10;
   System.out.println(a[3] + " " + b[3] + " " + c[3]);
   

   After giving the output, explain briefly why it makes sense.

2. (3 points) Consider the following static method, which operates on an array of integers:

   public static void mystery(int[] arr) {
       for (int i = 0; i < arr.length / 2; i++) {
           int n = arr.length - 1 - i;
           int val = arr[n];
           arr[n] = arr[i];
           arr[i] = val;
           // What values do the variables have here,
           // for each value of the loop variable `i`?
       }
   }
   

   Consider the following code fragment, which calls this method:

   int[] values = {0, 1, 2, 3, 4, 5, 6, 7};
   mystery(values);
   

   Copy the table shown below into your text file for this problem, and complete it to illustrate the execution of the above method call.

   mystery's variables
     i  |  n  | val | arr 
   -------------------------------------------
     -  |  -  |  -  | {0, 1, 2, 3, 4, 5, 6, 7}
     0  |     |     |
   

   We have started the table for you. The first row shows what the array looks like before the start of the for loop. For each value of the loop variable i, include a row in the table that shows the values of the other variables at the end of the iteration of the loop for that value of i. Note that you should write the value of arr as an array literal that shows the current contents of the array, even though the variable itself actually holds a reference to the array.

3. (2 points) After running the code fragment from part 2, we then execute the following statement:

   System.out.println(Arrays.toString(values));
   

   Do we see the original array, or do we see the changes made by the call to the mystery() method? Explain briefly why your answer makes sense.

   (Note: If you want to check your answer, you’ll need to import thejava.util package so that you can use the Arrays.toString() method.)

Problem 3: Two-dimensional arrays

8 points total; pair-optional

This is one of only two problems in this 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.

Open up a text editor (e.g., Notepad or TextEdit) and create a plain-text file named ps2pr3.txt. Put all of your work for this problem in that file.

Overview
Two-dimensional arrays in Java are extremely similar to two-dimensional lists in Python.

In Python, a 2-D list is a list of lists:

grid = [ [2, 4],
         [5, 7],
         [8, 1] ]

In the same way, a 2-D array in Java is an array of arrays:

int[][] grid = { {2, 4},
                 {5, 7},
                 {8, 1} };

(Note: When we declare a variable for a 2-D array, the type of the elements is followed by two pairs of square brackets: int[][])

Here is a comparison of other key operations for 2-D sequences:

Problems
Assume that you have a variable twoD that refers to a two-dimensional array of integers. Here is another example of such an array:

int[][] twoD = { {1, 2, 3},
                 {4, 5, 6},
                 {7, 8, 9} };

In your answers below, you may assume that the array is rectangular – i.e., that all rows have the same number of elements.

1. (2 points) Write an assignment statement that replaces the value of 6 in the above array with a value of 12.

2. (3 points) Write a code fragment that prints the values in the leftmost column of the array to which twoD refers. Print each value on its own line. For the array above, the following values would be printed:

   1
   4
   7
   

   Make your code general enough to work on any two-dimensional array named twoD that has at least one value in each row.

3. (3 points) Write a code fragment that prints the values in the anti-diagonal of the array to which twoD refers – i.e., the values along a diagonal line from the bottom-left corner to the upper-right corner. Print each value on its own line. For the array above, the following values would be printed:

   7
   5
   3
   

   Make your code general enough to work on any two-dimensional array in which the dimensions are equal – i.e., the number of rows is the same as the number of columns.

Part II Programming Problems

68 points total

Problem 4: Palindrome

18 points total; individual-only

For this problem, we will continue to explore using Java to do input and output, and in particular focus on using Strings. String reference is a simple reference on Strings. Googling “Java String library” or “Java Character library” will produce many references with explanations about these libraries For full details, the canonical reference on these libraries is the Oracle online Java page, which contains every detail you need to know: String, Character.

Begin by downloading StringTest.java. Execute the program as is; you will see that it inputs a sequence of strings and simply prints them out between double quotes. The program will continue to do this until you enter “quit” or if force quit by entering Control-d [hold down the Control key and hit the letter “d”] if you are running your program in a control terminal.

Using the program StringTest.java as a guide, write a new program PalindromeTest.java, which will read in a string, assumed to be an English sentence, and will invoke the method isPalindrom to check whether the string is a palindrome.

Note a string that is a palindrome reads the same backwards as forwards.

Here are the steps you should follow:

1. Read in the string and call a function named isPalindrome, which you will write, to determine if the string passed is in fact a palindrome.

2. Write the method isPalindrom which should have the following signature:

   public static boolean isPalindrome( String s ) {
      boolean isPal = false;    // assume that it is not
   
      // code to determine if the string s is a palindrome
   
      // If the default (as above) assumes the string is not a palindrome,
      // the logic here should determine if it is and reassign the return
      // variable isPal appropriately, or vice verse.
   
      return( isPal );
   }
   

3. Encode the logic of the method:

   1. Convert the string s to all lower case.

   2. Remove any character from the string which is neither a letter nor a digit. Hint: use replace(....) to replace any non-letter non-digit by the empty String “”.

   3. Check if the string s is a palindrome by checking to see if each letter is the same as the letter in its “mirror image” position; for example “Taco Cat” and “Toot!” are palindromes:

   but honor is not.

NOTE: There are multiple ways that you can solve this problem, but you are to follow the steps outlined. For example, you may NOT form the solution to the problem by converting the String to a char array first OR reverse the String and then compare if they are equal.

Test your code on at least the following palindromes:

A man, a plan, a canal, Panama!

Go hang a salami, I'm a lasagna hog!

Campus Motto: Bottoms up, Mac!

7/1/17      // A palindrome date!

Are we not pure "No sir!" Panama's moody Noriega brags. It is garbage! Irony dooms a man; a prisoner up to new era.

Note that the last quote may cause a problem because there are various kinds of “smart quotes” which are different from the simple ASCII double quotes; if all the others work and this one doesn’t, don’t worry about it!

Also test your code on a non-palindrome example – such as the word “palindrome” itself, or this sentence!

Problem 5: Word Palindrome

15 points total; individual-only

For this problem consider a different kind of palindrome – instead of having mirror images of characters in a string, a Word Palindrome has mirror images of words in a sentence; often these are given as Palindrome Poems or Mirror Poems:

Spoken Breath
Creating flesh and spirit
Spirit and flesh creating
Breath spoken.

The need to create a new program that is similar, but not exact, in nature to an existing program is a typical paradigm in computer science. What do you do when you do not want to lose the existing program but you need to modify it to accomplish some related purpose.

One option, and the one to use in this case, is to copy the solution of the first problem to a new file, and modify the new file. We will be talking about this paradigm and other ways of addressing it in the coming lectures!

Write a program WordPalindromeTest.java which invokes a method named isWordPalindrome to test whether your input String is a word palindrome. Follow these steps:

1. Read a line from the console, pass the line read (i.e. string) to the method isWordPalindrom which should return true or false accordingly.

2. The method should begin by converting the passed string to all lower-case and then also remove any character which is: not a digit, not a letter, and not white space (note we need to keep the white space to do the split in the next step)

3. Convert the string into an array of Strings (i.e. each entry in the array is a single word of the original string).

4. Adapt your algorithm from the first problem to test for equality of arrays of Strings instead of individual Strings.

5. Print out the array of words (this will help with debugging), and then your answer;

6. Demonstrate your code on the poem shown above:

   Note: You will have to enter this poem in a single line to avoid the newlines. In eclipse you can also do so as follows using backslashes, a typical way of indicating line breaks in a poem when putting it all in one line:

   Spoken Breath /  Creating flesh and spirit / Spirit and flesh creating / Breath spoken.
   

   Also test your program on the following sentence:

   This is not a word palindrome!
   

Another Word Palindrome:

Life-
imitates nature,
always moving, traveling continuously.
Continuously traveling, moving always,
nature imitates
life.

Problem 6: Array-processing methods

35 points total; 7 points each part; individual-only

In a class named ArrayMethods, implement each of the methods described below.

1. Write a method with the header

   public static void swapAdjacent(int[] values)
   

   that takes a reference to an array of integers values and swaps adjacent pairs of elements: values[0] with values[1], values[2] with values[3], etc.

   For example, after implementing this method and compiling your ArrayMethods class, you should see the following when you test the method programmatically:

   > int[] a1 = {0, 2, 4, 6, 8, 10};
   > ArrayMethods.swapAdjacent(a1);
   > System.out.println( Arrays.toString(a1) );
   { 2, 0, 6, 4, 10, 8 }
   

   In an odd-length array, the last element should not be moved:

   > int[] a2 = {1, 2, 3, 4, 5, 6, 7};
   > ArrayMethods.swapAdjacent(a2);
   > System.out.println( Arrays.toString(a2) );
   { 2, 1, 4, 3, 6, 5, 7 }
   

   Special case: If the parameter is null, the method should throw an IllegalArgumentException.

2. Write a method with the header

   public static int[] copyReplace(int[] values, int oldVal, int newVal)
   

   that takes a reference to an array of integers values and two integers oldVal and newVal, and that creates and returns a new array that is a copy of the original array, but in which all occurrences of the value oldVal are replaced with the value newVal.

   Important:

   • You may not use any of the built-in methods for copying an array.

   • Your method must not modify the original array.

   Examples:

   > int[] a1 = {2, 5, 4, 2, 7, 4, 2};
   > int[] a2 = ArrayMethods.copyReplace(a1, 4, 0);
   > System.out.println( Arrays.toString(a2) );
   { 2, 5, 0, 2, 7, 0, 2 }  
   > int[] a3 = ArrayMethods.copyReplace(a1, 2, -1);
   > System.out.println( Arrays.toString(a3) );
   { -1, 5, 4, -1, 7, 4, -1 }  
   > System.out.println( Arrays.toString(a1) );
   { 2, 5, 4, 2, 7, 4, 2 }
   

   Special case: If the parameter is null, the method should throw an IllegalArgumentException.

3. Write a method with the header

   public static int maxSorted(int[] values)
   

   that takes a reference to an array of integers and returns the length of the longest sorted sequence of integers in the array. For example:

   > int[] a1 = {3, 8, 6, 14, -3, 0, 14, 207, 98, 12};
   > System.out.println( ArrayMethods.maxSorted(a1) );
   4
   

   The above call should return 4, because the longest sorted sequence in the array has four values in it (the sequence -3, 0, 14, 207). Note that the sorted sequence could contain duplicates. For example:

   > int[] a2 = {17, 42, 3, 5, 5, 5, 8, 4, 6, 1, 19};
   > System.out.println( ArrayMethods.maxSorted(a2) );
   5
   

   This call should return 5 for the length of the sequence 3, 5, 5, 5, 8.

   Special cases:

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

   • Your method should return 0 if passed an empty array (i.e., an array of length 0).

   • Your method should return 1 if passed an array with one element or an array in which all of the elements are in decreasing order. It should be possible to get a return value of 1 for these cases without needing to explicitly check for them.

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;
• You have removed or changed all comments inherited from my templates which do not relate to your solution;
• 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;

Follow the gsubmit instructions and submit the following files:

• your ps2pr1.txt file containing your solutions for Problem 1
• your ps2pr2.txt file containing your solutions for Problem 2
• your ps2pr3.txt file containing your solutions for Problem 3; if you worked with a partner on this problem, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner
• your PalindromeTest.java source file
• your WordPalindromeTest.java source file
• your ArrayMethods.java source file

@