CS 112 Summer II, 2017-- Homework One

Due Friday, July 7th at 11:59pm using Websubmit

No late assignments will be accepted; we will give you some leeway this first homework, so if you hand it in a little after the deadline you will be fine.

Introduction

This homework has two parts: in Part A you will write up answers to analytical problems related to the lectures in the past week, both to confirm and extend your understanding of the abstract principles discussed; in Part B you will write code to implement this understanding, and to practice your Java coding skills. I suggest you read this whole assignment carefully and for Part B, it is definitely worth thinking about your solution for a bit before launching Eclipse and beginning to type. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):

 

Part A: Analytical Problems (20 pts)

Hand in your answers to the following problems, in order and written neatly, with your name on the top, in a text file hw01.txt (use Notepad, Textedit, or Word, and save as .txt).

  1. Give the following values:
    1. log2(2)
    2. log2(1024)
    3. log2(1000)
    4. floor( log2(1000) )
    5. ceiling( log2(1000) )

  2. For which values of N is log2(N) = floor( log2(N) ) ?
  3. For which values of N is (floor( log2(N) ) + 1) = ceiling( log2(N) ) ?
  4. 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))

  5. Which of the following will create an error because of a misuse of types?
          (a)  int n = 3 + '3';                             
          (b)  double x = (3.4 + (int) 2.1) * "3";          
          (c)  String s = "hi" + 5 + 't' + true + "there";  
      
  6. 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); 
  7. Consider the ordered list [ 2, 7, 12, 15, 19, 25, 26, 38, 45, 78 ] presented in lecture. During binary search, which numbers will take 3 comparisons to find (i.e., search for and return "Found!")?
    
    
  8. Again, considering binary search on the same list, will all unsuccessful searches (i.e., searching for a number not in the list) take the same number of comparisons (count only comparisons between n and a number in the list, not comparisons used to control the loop)? If not, give an example of two numbers (neither in the list) which prove your answer, and give the number of comparisons to do an unsuccessful search on each.
      
    
  9. Consider the unordered list [ 78, 25, 2, 15, 26, 38, 7, 45, 12, 19 ] presented in lecture. Using linear search, what is the average number of comparisons to search for the even numbers in the list only (assume each even number is searched for once)?
  10. Consider the following unordered list of integers: [ 2, 6, 3, 8, 6, 1, 3, 9, 3, 2]. What is the average number of comparisons to search for each of the numbers which occurs in the list? [Hint: when you search for a number, you only find the first occurrence of the number, never later duplicates.]
    
        

Part B: Programming Problems (80 points)

It is assumed that you have done Lab 1 before you start this homework; additional helpful information may be found at the bottom of this page in the appendices.

Problem B.1: Lab Problems (10 points)

Hand in your solutions for Haiku.java, SquareRoot.java, ArrayStatistics.java, and StringPractice.java.

Problem B.2: Print out Unix's (and OS X's) Birthday (30 points)

Write a program called PrintDay.java which calculates the day of the week (Sunday, Monday, ...., Saturday) a particular date falls on. You will represent the date as three integers, i.e., the due date for this assignment (September 14th, 2016 or 9/14/2016) would be represented as

   int day = 14;
   int month = 9;
   int year = 2016;        // these values are just an example, you will use different values in your submission
   

For simplicity these values will be "hard-coded" into your assignment and can only be changed by modifying your program (i.e., there will be no user input to the program). You will represent the resulting day of the week by an integer from 0 to 6 (0 = Sunday, 1 = Monday, ..., 6 = Saturday), and you will determine the day of the week for any date in the Gregorian Calendar using the following calculations, which are written in mathematical notation (with d = day, m = month, y = year, and d0 is the day of the week) as follows:

NOTE: You will have to translate this standard math-style notation into Java; notice that multiplication is represented both by a small x in the third line and by concatenation (31m0) in the last line. Division here is integer division, as in Java; thus all the variables will be int (don't use doubles anywhere!). The mod is the typical modulus operator. We are not trying to drive you crazy with this, just emphasizing that math notation is often different from Java and you may need to occasionally translate!

In order to print out the day of the week, assuming that your result is in the Java variable d0, you should use an array (not covered until next week) as follows:

   String[] dayOfWeek = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
   System.out.println("Unix\'s birthday was on a " + dayOfWeek[d0]); 
   

Time in Unix (and therefore in OS X) is defined as the number of seconds (or fractions of a second) since January 1st, 1970 (since the operating system was first named "Unix" in 1970 at Bells Labs in New Jersey). Write your program so that it prints out the day of the week that 1/1/1970 fell on. Hand in your program as a file PrintDay.java, following the instructions below under

Problem B.3: Simple Statistics (40 points)

You will write a program called Statistics.java which will take three integers input from the user and calculate various statistics of the three numbers. You must create this problem by modifying the template Statistics.java, which simply reads in a single number and prints it out; this should provide what you need to do the user input for the program. For this problem, you will use the Math library (see the end of the assignment for a description of this library, or simply Google "Java Math Library").

Suppose you input the three integers that the user types in as numOne, numTwo, and numThree. You must print out the following statistics for these three numbers:

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

You may not use any conditionals or loops for part (6): you must use only min(...), max(...), plus, and minus.

You may not use any libraries other than the Math library, as shown in Appendix One at the end of this document.

You should print out the doubles to four digits of precision, using the following variation of the println statement:

double p = 3.14159265;
System.out.printf("Pi is %.4f\n", p);        // This prints out:  Pi is 3.1416

Your goal is to simulate as closely as possible the printout shown below in Appendix Two. Hand in your program as a file Statistics.java, using proper indentation and a header comment.

 

Submission Instructions

Submit these files (make sure to name your files EXACTLY AS SHOWN, including upper and lowercase letters):

Make sure that each of your java files is neat and readable: it must have proper indentation (click anywhere inside the editor pane and then select Source -> Format from the Eclipse menu, or use the shortcut) and a header comment such as this:

/* File: Statistics.java 
 * Author: Wayne Snyder (waysnyder@gmail.com)
 * Date: May 7th, 2017
 * Purpose: This is a solution for HW01, Problem B.3.
 */

Note: When you format using the Eclipse formatting command, it will rearrange this comment. Don't worry about this, we will fix it in the next homework.

Similarly, put your name and the date on any .txt files. Any file submitted which does not follow these basic requirements will receive a penalty (more requirements will follow in the next couple of assignments).

 

Appendix One: Getting Started.....

1. Start Eclipse and click on File->New->Java Project

2. Under Project Name in 'New Java Project' window enter 112Hwks

3. Right Click on src under '112Hwks' and select 'New' and then 'Package'. See screenshot




4. Enter the name of the package as 'hw1'. 

5. Your Package Explorer in Eclipse MUST look like this as shown in the next image i.e. if you have followed all steps from 1-4 correctly. Please note everything is case sensitive. 




6. Right click on 'hw1', and then click on 'New' and then 'Class'.

7. Enter the name of the class as Haiku

8. Repeat steps 6) and 7) above for the following classes: SquareRoot, PrintDay and Statistics

9. Your Package Explorer in Eclipse MUST look like this as shown in the next image i.e. if you have followed all the steps from 1-9 correctly. Please note everything is case sensitive. 



10. All your Java files in Eclipse must look like this i.e. the first line in these files must have package hw1; 



11. You will write your code for Homework 1 in Haiku.java, SquareRoot.java, PrintDay.java and Statistics.java

12. When you have completed your assignment, you are required to submit all your five files i.e. four java files i.e. Haiku.java, SquareRoot.java, PrintDay, Statistics AND hw01.txt to us using WebSubmit. 

13. WebSubmit is available for you to use on this link  Link to WebSubmit  .  

Appendix Two: Using the Java Math Library

Here is a brief description of the Java Math library. You do not need to use an import statement to use these methods, but do need to precede them with the name of the library (as shown below):

int abs(int a)                 =>    absolute value of a      //  "=>" means "returns the value"
double abs(double a)           =>    absolute value of a  
int max(int a, int b)          =>    maximum of a and b 
double max(double a, double b) =>    maximum of a and b 
int min(int a, int b)          =>    minimum of a and b 
double min(double a, double b) =>    minimum of a and b        
double log(double a)           =>    ln( a )                  // log to the base e 
double pow(double a, double b) =>    a^b                      // a to exponent b          
long round(double a)           =>    round a to the nearest 64-bit integer  ...   If you want this to return an int, use a cast: (int) round( ... )
double sqrt(double a)          =>    square root of a
   

Note carefully that some methods (e.g., abs, max, and min) are overloaded (have implementations for ints and also for doubles).

Here are various (arbitary) examples of how to use these methods, using the name of the library plus a period:

Math.sqrt(5.0*5.0 - 4.0*4.0)  =>  3.0  
Math.sqrt(5*5 - 4*4)          =>  3     
Math.log(Math.E)              =>  1.0          // Math.E is Euler's constant e
Math.round(Math.PI)           =>  3.0          // Math.PI is 3.1415.....
(int) Math.round(Math.PI)     =>  3            // Math.PI is 3.1415.....
Math.max(1.0, 9)              =>  9.0
Math.pow(2, 10.0)             =>  1024.0
   

Appendix Three

Here is a sample output of the program Statistics.java in Eclipse; you should try to do something very similar:

Here is sample session with the PalindromeTest program: