Monday June 19, 2000

Quiz 10

1. What are the five primary components in a class definition?

2. What two classes do we use in order to obtain input from the user?

3. What package must be imported in order to use those classes?

4. What statement is used in order to produce output?

E-mail addresses

The School of Computer and Information Sciences is collecting e-mail addresses of it students in order to make communication between itself and students easier. When you get a chance please visit the URL http://www.cis.usouthal.edu/email. You will be allowed to enter up to three different e-mail addresses. If you experience problems using it, please send me e-mail.

Webspace for majors

Beginning last year the School began offering each of its majors 10 MB of space and an account on our UNIX server. You may use the space to host your personal web page. You account may also be used to receive e-mail. The JDK is installed on the system so you may also log in to use the compiler and interpreter to write your Java programs if you want. In order to activate your space, go to the URL http://www.cis.usouthal.edu/policy.html, read the policy, sign it, and returng it to me. Your space will activated within approximately 48 hours and once you have created your page and have permissions set correctly you may view your page at http://www.cis.usouthal.edu/students.

Frequently Asked Questions

In order to make it easier for you to raise questions about topics you don't understand I have set up a Frequently Asked Questions list. You may post questions to this list anonymously and the answers will be available to everyone. You will find links to this list on the web page for this course, CIS 120 Summer Semester 2000.

Other ways to contact me

If you are at a machine at which you can't use electronic mail or you are using a browser which doesn't support sending electronic mail, you can go to the URL http://www.cis.usouthal.edu/~lynn/summer2000/contact.html. You can find a link to this on the web page for the course, CIS 120 Summer Semester 2000.

An Example Problem

In order to give you more practice in the problem solving process let us look at another problem and go through the steps of generating an algorithm and turning it into code.

Understanding the Problem

Problem: Suppose we wish to find the square root of a positive number following the divide-and-average method. We do this by starting out with a number, a. We make a guess to the square root of a, say x. We then divide a by x, and to get a new guess to the square root we average x and this result.

So, for example, suppose I wish to find the square root of 3. I make a guess, 1.5. I divide 3 by 1.5 to give 2. To get a new guess to the square root of 3 I average 1.5 and 2 to give 1.75.

Initial Guess: 1.5

Next Guess: 3/1.5 = 2. (1.5 + 2)/2 = 1.75.

Next Guess: 3/1.75 =~ 1.714. (1.75 + 1.714)/2 = 1.732.

We stop the process when the difference between guesses is less than a certain value, for example, 0.05.

Since the difference between 1.732 and 1.75 is less than 0.05 we would stop the process and accept 1.732 as an approximation of the square root of 3.

Devising a Plan

Now that we understand what we are trying to do we must now come up with a plan of how we will write a program to solve this problem. The first step will be to come up with an algorithm. So now let us examine the steps we take in solving the problem.

The first thing we need to do is get some input from the user. We must know three things: the number to find the square root of, the initial guess, and the acceptable error in approximation, that is the acceptable difference between guesses.

1. Get a, x, and tol, where a is the number to find the square root of, x is the initial guess, and tol is the acceptable error.

After we get the input from the user, notice that we then begin the process. Now notice that this is a process which we carry out until a certain condition is met. That is, we carry out the process as long as the difference between successive guesses is larger than the acceptable error. So the construct that is most suited to this process is a while loop. So let's describe the steps we take during each execution of the loop.

Notice that the condition which will stop the execution of the loop is that the difference between guesses is smaller than tol. So let us introduce a variable to help us describe this condition.

2. Declare a new variable called error and make its initial value equal to tol+1.

The reason for making the initial value of error = tol + 1 is that it will guarantee that the loop will execute at least once (we will be using a while loop). Since the loop will continuing executing as long as the value of error is larger than tol, assigning error = tol + 1 will guarantee that the loop will be executed at least once.

Now we are ready to start the loop.

3. Repeat the following steps as long as error > tol.

Now we want to calculate a new guess. To make the calculaton easier to read let us introduce a new variable called newguess.

      a. Let newguess = (x + a/x)/2.

Now that we have the approximation we must compare it to the old guess and adjust error. Because it might be possible for the new guess to be smaller than the old guess we must use the absolute value of the difference.

      b. Let error = absolute value(newguess - x).

Now notice that there is one crucial step left. If we do not adjust the value of x, then this loop will repeat indefinitely since the value of new and x will always be the same. Since x is used to represent the guess, we need to assign the new guess into x.

      c. Let x = newguess.

Once the loop is completed the most current guess will be x.

4. Report that the approximation to the square root of a is x.

Implement the Plan

Now that we know the steps that we need to take in solving the problem, let us now translate these steps into code.

Let us look at each step and decide how we will implement each one in Java.

1. Get a, x, and tol, where a is the number to find the square root of, x is the initial guess, and tol is the acceptable error.

We have discussed how to obtain input from the user. We will assume that we import java.io.* into our program.

InputStreamReader stream = new InputStreamReader(System.in);
BufferedReader keyboard = new BufferedReader(stream);

Now we have a BufferedReader set up so we can get input from the user. Now we must decide what we expect the user to input.

Since there is no requirement for the number we are trying to take the square root of to be an integer, we will have more flexibility if we assume the number is a real number.

Because the approximations will usually be real number it is also a good idea to input x as a real number.

Normally the difference that we want between guesses is small so we want tol to be a real number.

We will also prompt the user to tell them what we expect.

System.out.println("Please enter the number you want to take the square root of.");

float a = new Float(keyboard.readLine()).floatValue();

System.out.println("Please enter an initial guess.");

float x = new Float(keyboard.readLine()).floatValue();

System.out.println("Please enter a tolerance for error.");

float tol = new Float(keyboard.readLine()).floatValue();

2. Declare a new variable called error and make its initial value equal to tol+1. Because the error will be small we want it to be a real number.

float error = tol + 1;

Now we must begin implementing the loop. Let us start with the beginning of our loop.

3. Repeat the following steps as long as error > tol.

Because of how this statement is made we are going to use a while loop. Note that in our algorithm more than one statement is executed each time through the loop, we need to surround the body of the loop with braces.

while (error > tol) {

Now we want to introduce the variable newguess. Let us assume that we have declared this variable already.

a. Let newguess = (x + a/x)/2.

newguess = (x + a/x)/2;

Now we must compute the error.

b. Let error = absolute value(newguess - x).

In the Math class there is a method called abs which will return the absolute value of a number.

error = Math.abs(newguess - x);

Now we must assign the approximation we just calculated to x.

c. Let x = newguess.

x = newguess;

Now that we have finished the body of the loop we must remember to include the closing brace.

When the loop is finished the final approximation to the square root of a is x. Recall that we concatenate strings and numbers in a System.out.println statement.

4. Report that the approximation to the square root of a is x.

System.out.println("The approximation to the square root of " + a + " is " + x);

Now let us put this code together in a program. Recall that in order for a Java program to be executed by the interpreter it must contain a main method.

import java.io.*;

public class DivideandAverage {

   public static void main(String[] args) throws IOException {
      float newguess;

      InputStreamReader stream = new InputStreamReader(System.in);
      BufferedReader keyboard = new BufferedReader(stream);

      System.out.println("Please enter the number you want to take the square root of.");

      float a = new Float(keyboard.readLine()).floatValue();

      System.out.println("Please enter an initial guess.");

      float x = new Float(keyboard.readLine()).floatValue();

      System.out.println("Please enter a tolerance for error.");

      float tol = new Float(keyboard.readLine()).floatValue();

      float error = tol + 1;

      while (error > tol) {
         newguess = (x + a/x)/2;
         error = Math.abs(newguess-x);
         x = newguess;
      }

      System.out.println("The approximation to the square root of " + a + " is " + x);
   }

}

Evaluate the Outcome

After compiling the program and executing it we try some sample data. Below is the output of two runs of the program

Please enter the number you want to take the square root of.
3
Please enter an initial guess.
1.5
Please enter a tolerance for error.
0.05
The approximation to the square root of 3.0 is 1.7321429


Please enter the number you want to take the square root of.
2
Please enter an initial guess.
0.5
Please enter a tolerance for error.
0.05
The approximation to the square root of 2.0 is 1.4142343

Since we get correct results from these two runs this gives us confidence that the program is correct. In practice we might make many runs to give us more confidence in our program. Note that because these are two simple cases there could be problems that might occur with other input data that this wouldn't uncover. So we cannot say for certain that the program is correct for all input but we are reasonable confident that it is correct.

Your programming assignment

Let us look at another example of the Euclidean Algorithm.

Consider b = 13, and a = 8.

13	=	1*8	+	5
8	=	1*5	+	3
5	=	1*3	+	2
3	=	1*2	+	1
2	=	2*1	+	0

Since the last non-zero remainder is 1, this is the greatest common divisor.

There are things we can notice from this example which can lead us to an algorithm for solving the problem in general.

Note that we start out with b = 13 and a = 8. On the second row, b is 8 and a is 5. Note where these values come from. 8 is the value of a in the previous row, and 5 is the remainder in the previous row.

Now let us find the coefficients to write 5 as a linear combination of 5 and 8.

     1   1   1   1
0 1  1   2   3   5
1 0  1   1   2   3

We are looking for numbers x and y such that 13x + 8y = 1. Now the smaller of the two numbers in the last column must be the coefficient of the larger of 13 and 8. So 5 is the absolute value of the coefficient of 8, and 3 is the absolute value of the coefficient of 13. Note that one of the coefficients must be negative. Now let us look at the two products.

5*8 = 40
3*13 = 39

So the coefficient of 13 is -3. So what we find when b = 13 and a = 8 is

the greatest common divisor is 1.
the coefficient of 13 is -3.
the coefficient of 8 is 5.

One thing that is very important to note is that in filling in the columns in the table, the only value which needs to be computed in order to find the values in a column is the header of the column, that is the quotient in that column. It is also important to note that as you move from left to right in the table, the only values you need to fill in the entry in a column are the two values to its left. That is, to fill in the entry under the first 1, you use 1 and 0. To fill in the entry under the second 1 you use 1 and 1. This is a very important observation.

Keep in mind that we have talked about two operations which you may find useful.

In order to find the integer part of a real number, we may cast that number as an int. So to find the quotient of the division of two numbers such as 19 and 4 we may cast the division of the two as an integer.

(int)(19/4)

To obtain the remainder in the division we may either use the quotient or use the modulus operator. In order to use the quotient we could do the following.

int remainder = 19 - ((int)(19/4))*4;

We could also use the modulus operator.

int remainder = 19 % 4;

Exam 1

Recall that our first exam is this Friday. The format of the exam will be the following.

Fill in the Blank (20 pts)
Definitions (10 pts)
Short Answer (30 pts)
Discussion (20 pts)
Coding (20 pts)

In the coding portion of the exam you will be presented with a problem and asked to come up with an algorithm for solving it and then translate that into Java code.

The material for the exam will be based upon what we cover up to Wednesday. Tomorrow a review for the exam containing a list of all the important concepts we have discussed will be posted.

Homework

To give you more practice at solving problems try to come up with an algorithm for the solution of the following problem and translate that into code. The solution will be posted tomorrow.

Problem The factorial of a number is a very important concept. The definition of the factorial of n, written n!, is the product of all integers from 1 to itself.

For example, 2! = 2*1, 3! = 3*2*1, 4! = 4*3*2*1, 5! = 5*4*3*2*1, etc.

Develop an algorithm for finding the factorial of a given number and translate that into Java code.