Problem Set 1

due by 11:59 p.m. on Friday, February 1, 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 course instructor or teaching fellow.

Make sure to follow the instructions outlined at the end of the problem set when submitting your assignment.

Part I Analytics Problems

46 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 entering the code in Eclipse, but we strongly encourage you to answer them on your own and convince yourself of the correctness of your answer. If you choose to also enter the code, you should only do so to verify correctness. These questions are similar to ones that could appear on the midterms and final exam, which you will have to answer without the use of a computer, so it is important to test your own knowledge through these assignments!

Problem 1: Learning to read (code)

18 points total; 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. Your work for this problem should be in order and written neatly, with your name written at the top.

1. Suppose that a and b are int values. Simplify the following expressions to a boolean expression involving only a single operator:

   1. (!(a < b) && !(a > b))
   2. ( (a < b) == true )
   3. ( (a <= b) == false )
   4. (!(a > b) && !(a < a))
   5. ( (b < b) || !(a <= b))

2. Which of the following will create an error because of a misuse of types?

   1. int n = 3 + '3';
   2. double x = (3.4 + (int) 2.1) * "3";
   3. String s = "hi" + 5 + 't' + true + "there";

3. What do each of the following print? (Be sure you understand WHY!)

   1. System.out.println(2 + "bc"); 
   2. System.out.println(2 + 3 + "bc");  
   3. System.out.println((2+3) + "bc"); 
   4. System.out.println("bc" + (2+3)); 
   5. System.out.println("bc" + 2 + 3); 

4. What’s wrong with the following program? State as many errors as possible that (individually) would prevent the program from compiling without error:

   Public class test1 {
       public static integer f( x ) {
           if(x = 5)
           x = 1;
       }
   
       public static void main [String[] argv] {
       {
           System.println('Hello World!')
       }
   )
   

Note: The next several tasks require you to perform a paper and pencil trace of the specified code. Use a methodology outlined in both lecture and lab to execute the program as if you are the CPU, and state the output of the program exactly as if the computer exectued it.

You must be able to successfully answer these types of questions using a paper and a pencil! Do not simply encode these programs and copy the results.

Unless the format of the paper and pencil trace is specified, use whatever format you are comfortable with. We are interested to see if the trace you follow produces the correct results.

5. Perform a paper and pencil trace of the following program:

   public class test2 {
       public static void main (String[] argv) {
           System.out.println( (double) (int) 3.1415 );
           int i = 10;
           while (i >= 1)
               System.out.println(i);
               --i;
       }
   }
   

6. Perform a paper and pencil trace of the following program:

   public class test3 {
       public static void main (String[] argv) {
           int[] A = { 1, 1, 1, 1 };
           for(int i = 0; i < 4; ++i) {
               for(int j = i-1; j >=0; --j) {
                   A[i] +=  A[j];
               }
           }
   
           for(int i = 0; i < 4; ++i)
               System.out.println(A[i]);
       }
   }
   

7. Perform a paper and pencil trace of the following program:

   public class test4 {
   
       public static void main (String[] argv){
           int[] A = { 1, 2, 3, 4, 5, 6 };
           for(int i = 0; i < A.length; ++i) {
               if( A[i] % 2 == 0 )
                   continue;
               else if( A[i] > 4 )
                   break;
               else
                   A[i] *= 2;
           }
   
           for(int i = 0; i < A.length; ++i)
               System.out.println(A[i]);
       }
   }
   

Problem 2: Static methods

8 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. 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 ps1pr2.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 3: for Loops

7 points total; 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.

1. (2 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. (2 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. (3 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 4: 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 ps1pr4.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 5: String objects and their methods

7 points total; individual-only

Open up a text editor (e.g., Notepad or TextEdit) and create a plain-text file named ps1pr5.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 write a simple program to experiment with them.

   For example, you can do this:

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

   Doing so should display the return value:

   "ost"
   

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

54 points total

Problem 6: Practice with static methods, part I

18 points total; 6 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: Methods.java. Open it in Eclipse, 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. Write a simple program and test this method.

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:

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

   > Methods.middleChar("clock")
   'o'
   > Methods.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:

   > Methods.moveToEnd("Boston", 4)
   "onBost"
   > Methods.moveToEnd("Terriers", 2)
   "rriersTe"
   > Methods.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 that contains code to test all the methods you have implemented. Do not rely on your own test program. This is an important step as it will help identify any inconsistencies in the method calls to ensure that these problems are not found during grading. Here’s how:

• Download the following file: TestMethods.java.

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

• Open TestMethods.java in Eclipse 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 TestMethods.java and reopen it later.

• If TestMethods.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 TestMethods.java to compile.

• Once TestMethods.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 7: Practice with static methods, part II

24 points total; 6 points each part; individual-only

In a class named MyMethods, 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:

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

   > MyMethods.firstAndLast("Boston") 
   "Bn"
   > MyMethods.firstAndLast("University")
   "Uy"
   > MyMethods.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:

   > MyMethods.lastIndexOf("Boston", 'o')
   4
   > MyMethods.lastIndexOf("banana", 'a')
   5
   > MyMethods.lastIndexOf("banana", 'b')
   0
   > MyMethods.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 must somehow signal for the loop to stop (think through the conditional expression that controls the loop) or you can use the break statement.

   • 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:

   > MyMethods.repeat("Java", 3)
   "JavaJavaJava"
   > MyMethods.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: TestMyMethods.java

Problem 8: Simple Statistics

12 points total; individual-only

For this problem you will write a program called Statistics.java which will contain a method that performs various statistics.

Begin by downloading the file: Statistics.java, which simply sets-up the skeleton of your program.

Complete the function display_statistics that accepts three integers as arguments, namely: numOne, numTwo, and numThree. The function should compute and print out the following statistics:

1. The sum of the three numbers;
2. The maximum of the three numbers;
3. The range of the numbers (i.e. the distance between the maximum and the minimum value);
4. The mean (average) of the three numbers;
5. The (population) standard deviation of the three numbers;
6. Finally, print out the three numbers in ascending order (hint: find the median using the maximum and minimum plus addition and subtraction).

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 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 ps1pr5.txt file containing your solutions for Problem 4
• your modified Methods.java source file containing your solutions for Problem 6; 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 MyMethods.java source file containing your solutions for Problem 7
• your Statistics.java source file containing your solution for Problem 8