Problem Set 1

due by 11:59 p.m. on Tuesday, January 30, 2018

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.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

Part I

40 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 in DrJava, 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 DrJava. 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: Static methods

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

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

1. Consider the following Java program, which includes two static methods:

   public class TracingMethodCalls {
       public static int compute(int x, int y) {
           x += 3;
           y = 2*y - x;
           System.out.println(x + " " + y);
           return x;
       }
   
       public static void main(String[] args) {
           int x = 1;
           int y = 3;
           System.out.println(x + " " + y);
           x = compute(x, y);
           System.out.println(x + " " + y);
           compute(y, y);
           System.out.println(x + " " + y);
           y = 3 + 4 * compute(y, x);
           System.out.println(x + " " + y);
       }
   }
   

   Copy the tables shown below into your text file for this problem, and complete them to illustrate the execution of the program.

   main's variables
     x  |  y  
   -----------
     1  |  3     
        |
   
   compute's variables
     x  |  y  
   -----------
        |       
        |
   
   output (the lines printed by the program)
   ------
   1 3
   

   Note that you must include three tables: one for the variables that belong to the main method (ignoring its args parameter), one for the variables that belong to the compute method, and one for the output of the program. Don’t forget that each method has its own separate set of variables, even though they happen to have the same names.

   We have started the first and third tables for you. You should:

   • complete the first and second tables so that they illustrate how the values of the variables change over time
   • complete the third table so that it shows the output of the program (i.e., the values that are printed).

   You should add rows to the tables as needed.

2. Fill in the blanks below to create a static method that takes as parameters an original price (a real number that can include a decimal) and a percent discount (an integer) and computes and returns the discounted price as a real number. Put the final completed method in your ps1pr1.txt file.

   For example, if the original price is 50.0 and the percent discount is 10, your method should return a discounted price of 50.0 - 0.10(50.0) = 45.0. (You will need to divide the percentage by 100 as part of the computation.)

   Use the names originalPrice and percentDiscount for the parameters.

   public ____________ discountPrice(______________________) {
       ______ newPrice = ___________________;
       __________________;
   }
   

   Note that the body of the method should be exactly two lines: one line that assigns the appropriate expression for the discounted price to to the variable newPrice, and a second line that returns the value of newPrice.

   Important: In Java, the / operator is used for both integer division and floating-point division. In order to get floating-point division — which preserves the digits after the decimal — you need to make sure that at least one of the operands is a floating-point number. If both of the operators are integers, you will get integer division.

Problem 2: for Loops

10 points total; individual-only

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

1. (3 points) Fill in the blanks below to create a loop that repeats the message “Repeat!” 112 times. Use the template for obtaining N repetitions that we discussed in lecture, and give the full completed loop as your answer.

   for (____________; ____________; ____________) { 
       System.out.println("Repeat!");
   }
   

2. (3 points) Consider the following code fragment:

   for (int i = 4; i < 10; i++) {
       System.out.println(i);
   }
   

   This code is supposed to print the even integers from 4 to 10 on a single line (i.e., 4 6 8 10 ). However, it currently fails to do so.

   Make whatever changes are needed to obtain the correct output, and give the full corrected code fragment as your answer. The corrected version should still consist of a three-line for loop — i.e., you should not add any lines.

3. (4 points) Consider the following code fragment, which is an example of one loop nested in another:

   for (int i = 4; i >= 2; i--) {
       for (int j = 2; j <= 4; j++) { 
           System.out.println(i + " " + j);
       }
       System.out.println("--");
   }
   

   Modify this fragment to make it produce the following output:

   4 1
   4 2
   4 3
   4 4
   4 5
   --
   3 1
   3 2
   3 3
   3 4
   --
   2 1
   2 2
   2 3
   --
   1 1
   1 2
   --
   

   Make whatever changes are needed to obtain the correct output, and give the full corrected code fragment as your answer. The corrected version should still consist of six lines, with one three-line for loop nested in another for loop.

Problem 3: Variable scope

6 points total; 1 point each part; individual-only

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

Consider the following program, which includes a number of incomplete println statements:

public class ScopePuzzle {
    public static void doSomething(int a) {
        System.out.println(________);            // first println
        int b = 5;

        for (int i = 1; i <= 5; i++) {
            int c = 2;
            for (int j = 0; j < 3; j++) {
                int d = 4;
                System.out.println(________);    // second println
            }
            System.out.println(________);        // third println
        }

        System.out.println(________);            // fourth println
    }

    public static void main(String[] args) {
        int x = 5;
        System.out.println(________);            // fifth println

        int y = 2;
        doSomething(x);
        System.out.println(________);            // sixth println
    }
}

The program includes a number of int variables: a,b,c,d, i, j, x and y. Given the rules that we have learned about variable scope:

1. Which of these variables could be printed by the first println statement?
2. Which of them could be printed by the second println statement?
3. Which of them could be printed by the third println statement?
4. Which of them could be printed by the fourth println statement?
5. Which of them could be printed by the fifth println statement?
6. Which of them could be printed by the sixth println statement?

Note that we are only focusing on the variables of type int, so you can ignore the args parameter of the main method.

Problem 4: String objects and their methods

14 points total; individual-only

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

Working with strings: Python vs. Java
Python has built-in operators and functions for common string operations like indexing and slicing. In addition, string objects — like all objects — have methods inside them. These methods allow you to obtain information about a string and to create new strings that are based on the original one.

Java lacks many of Python’s built-in operators and functions for strings. Instead, most operations involving strings – including indexing and slicing – are done using methods that are inside the string object.

The table below compares the ways in which some common string operations would be accomplished in Python and Java:

Notes:

• Java has a separate type called char for values that consist of a single character. Literals of this type are surrounded by single quotes (e.g., the 'o' in the call s1.indexOf('o')), whereas string literals must be surrounded by double quotes. (In Python, there is no separate char type, and string literals can be surrounded by either single or double quotes.)

• The charAt() method that we use for indexing in Java returns a value of type char. For example, the call s1.charAt(0) in the table above would return the char value 'B', since 'B' is the first character in the string "Boston".

Given the information above, here are the tasks you should perform:

1. (0 points) To ensure that you understand how the above string operations work in Java, we strongly encourage you to use DrJava’s Interactions Pane to experiment with them.

   Open DrJava and click on the tab labeled Interactions near the bottom of the window. You should see a prompt that looks like this:

   >
   

   This prompt is like the >>> prompt in the Python Shell, and you can use DrJava’s Interactions Pane in much the same way that you can use the Shell in Python.

   For example, you can do this:

   > String s1 = "Boston";
   > s1.substring(1, 4)
   

   Doing so should display the return value:

   "ost"
   

   Use the Interactions Pane to enter the statements and expressions from the Java column of the table above. Make sure to begin with the first lines in that column, so that you will declare and assign values to the two variables.

   In addition to the expressions in the table, try other variations of those expressions until you are confident that you understand how the methods and operators work.

2. (14 points) Assume that the following statements have already been executed:

   String str1 = "A method";
   String str2 = "to my MADNESS";
   

   For each of the following values, construct an expression involving operations on str1 and/or str2 that evaluates to that value. For full credit, you should not use literal values (e.g., "T" or 'e') unless it is absolutely necessary to do so.

   1. Construct an expression involving str1 or str2 that produces the following value:

      "to my MADNESS a method"`
      

      Note: You will need to explicitly add a space.

   2. Construct an expression involving str1 or str2 that produces the following value:

      'h'
      

      Note that the single quotes mean that you must produce a char, not a String. See the notes under the table above that discuss the char type.

   3. Construct an expression involving str1 or str2 that produces the following value:

      "MAD"
      

   4. Construct an expression involving str1 or str2 that produces the following value:

      "YES"
      

      Hint: Part of your expression will need to chain two method calls together. For example:

      > str2.toLowerCase().substring(9)
      "ness"
      

   5. Construct an expression involving str1 or str2 that produces the following value:

      "ethos"
      

   6. Construct an expression involving str1 or str2 that produces:
      the following value:

      10
      

      Hint: Use the indexOf method to find a character in str1 or str2.

   7. Construct an expression involving str1 or str2 that produces the following value:

      "to my BADNESS"
      

      Use the first replace method in the String class; consult the API of the String class to figure out how to use it.

Part II

60 points total

Problem 5: Practice with static methods, part I

24 points total; 8 points each part; 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.

This problem asks you to write a series of static methods.

Begin by downloading this file: Methods5.java. Open it in DrJava, and add your methods to the class that we have given you in that file.

Here are the methods you should implement:

0. a static method called printVertical that takes a String as its parameter and prints the characters of the string vertically — with one character per line. For example, a call of printVertical("method") should produce the following output:

   m
   e
   t
   h
   o
   d
   

   We have given you this example method in the starter file.

   Initial testing of a static method
   You can use the DrJava Interactions Pane to test a static method as soon as you are able to compile it.

   For example, to test the provided printVertical method:

   • Compile the provided code by clicking the Compile button in DrJava.

   • Click on the tab labeled Interactions near the bottom of the window, which should display this prompt:

     >
     

   • Enter method calls at the prompt. Because these calls are being made from outside the class to which the method belongs, you will need to prepend the class name:

     > Methods5.printVertical("foobar")
     

     Doing so should show you the appropriate output.

1. a static method called printWithSpaces that takes a String as its parameter and prints the characters of the string separated by spaces. For example:

   > Methods5.printWithSpaces("method")
   m e t h o d
   

   You should have a single space after the last character. This method should not return a value.

   Hint: Use printVertical as a model.

2. a static method called middleChar that takes a String object as a parameter and returns the character (a value of type char) in the “middle” of the string. If the string has an odd number of characters, the method should return the actual middle character. If the string has an even number of characters, there are two characters that could both be considered middle characters, and your method should return the first of these characters (the one closer to the beginning of the string). For example:

   > Methods5.middleChar("clock")
   'o'
   > Methods5.middleChar("Boston") 
   's'
   

   This method should not do any printing; rather, it should extract the appropriate character and return it.

   Hint: You will need to perform a computation to determine the index of the character that you need to extract, and you should be able to perform the same computation regardless of whether the string has an odd or even number of characters.

3. a static method called moveToEnd that takes as its two parameters a string str and an index i and returns a new string created by “moving” the first i characters of str to the end of the string, after the other characters in str. If the string str has i or fewer characters, the method should simply return the original string. For example:

   > Methods5.moveToEnd("Boston", 4)
   "onBost"
   > Methods5.moveToEnd("Terriers", 2)
   "rriersTe"
   > Methods5.moveToEnd("Boston", 8)
   "Boston"
   

   You may assume that the value of i is positive. This method should not do any printing; rather, it should return the appropriate string. Hint: You will need to use conditional execution to allow your method to check for the case in which str has i or fewer characters.

Additional testing Once you have completed all of these methods, you should use a test program that we have created. Here’s how:

• Download the following file: Test5.java.

  Use the File→Save As (or equivalent) option in your browser to put this file in the same folder as your Methods5.java file.

• Open Test5.java in DrJava and compile it. Don’t try to do this until all of your methods have been written. If you are not yet done with all of the methods, you should close Test5.java and reopen it later.

• If Test5.java doesn’t compile, that probably means that one or more of your methods does not have the correct header — i.e., either the name, the return type, or the parameters are incorrect. Make whatever changes are needed to your methods to get Test5.java to compile.

• Once Test5.java does compile, you should run it and check the results that it produces; the correct results are given in the descriptions of the methods above.

• We encourage you to add additional test cases to the ones that we have provided.

Problem 6: Practice with static methods, part II

36 points total; 9 points each part; individual-only

In a class named Methods6 (note the 6 at the end), implement each of the methods described below.

1. a static method called printDecreasing that takes a String as its parameter and prints decreasing substrings of the original string. For example:

   > Methods6.printDecreasing("method")
   method
   metho
   meth
   met
   me
   m
   

   This method should not return a value. Hint: You may find it helpful to use a for loop with a header that does not match either one of the usual templates.

2. a static method called firstAndLast that takes a string str as its parameter and returns a new string formed by combining the first and last characters of str. If the string has only one character, the method should just return the original string. For example:

   > Methods6.firstAndLast("Boston") 
   "Bn"
   > Methods6.firstAndLast("University")
   "Uy"
   > Methods6.firstAndLast("a")
   "a"
   

   You may assume that str has at least one character. This method should not do any printing. Rather, it should return the appropriate string. Hint: You will need to use conditional execution.

3. a static method called lastIndexOf that takes as its two parameters a string str and a character ch and returns the index of the last occurrence of ch in str. If ch does not appear in str at all, the method should return -1. For example:

   > Methods6.lastIndexOf("Boston", 'o')
   4
   > Methods6.lastIndexOf("banana", 'a')
   5
   > Methods6.lastIndexOf("banana", 'b')
   0
   > Methods6.lastIndexOf("banana", 'x')
   -1
   

   This method should not do any printing; rather, it should return the appropriate integer.

   Important: You may not use the built-in lastIndexOf methods!

   Hints:

   • One way to solve this problem is to use a for loop that examines at one character at time, starting at the end of the string and working backwards towards the beginning of the string. As soon as you find an occurrence of the character you are looking for, you can return its index, which will break you out of the loop.
   • You will need to use conditional execution.

4. a static method called repeat that takes as its two parameters a string str and an integer n and returns a new string consisting of n copies of str. You may assume that n is positive. For example:

   > Methods6.repeat("Java", 3)
   "JavaJavaJava"
   > Methods6.repeat("oh!", 7)
   "oh!oh!oh!oh!oh!oh!oh!"
   

   This method should not do any printing; rather, it should construct and return the appropriate string.

   Hints:

   • You will need to gradually build up the return value using string concatenation. To do so, we recommend that you use a variable for your return value and that you give it the empty string as its initial value:

     String result = "";
     

     This will allow you to gradually add to the result by using statements that look like the following:

     result = result + expr;
     

     where expr is replaced by an appropriate expression.

   • You will need to use a for loop as part of your implementation of this method.

Additional testing Once you have completed all of these methods, you should use the following test program to test them: Test6.java

Submitting Your Work

You should use Apollo to submit the following files:

• your ps1pr1.txt file containing your solutions for Problem 1
• your ps1pr2.txt file containing your solutions for Problem 2
• your ps1pr3.txt file containing your solutions for Problem 3
• your ps1pr4.txt file containing your solutions for Problem 4
• your modified Methods5.java file containing your solutions for Problem 5; if you worked with a partner, 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 Methods6.java file containing your solutions for Problem 6

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.