Friday June 23, 2000

Quiz 14

1. What are the four primary components in the signature of a method?

2. If we have two methods with the same name, what is that called?

3. How do we distinguish between them?

4. How do we distinguish between a class variable and an instance variable?

Problem:

Given two integer, a and b, with a < b, find the greatest common divisor of the two numbers, and find a linear combination of a and b which equals the greatest common divisor.

Solution:

Let us begin with our standard example to get an idea of how to proceed.

We carry out the Euclidean Algorithm as follows.

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

The last non-zero remainder is the greatest common divisor.

Now we find the coefficients to give us a linear combination.

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

So the absolute value of the coeffient of 8 is 5, and the absolute value of the coefficient of 13 is 3. Since 5*8 > 3*13, the actual coefficient of 13 is -3, and the actual coefficient of 8 is 5.

So for this example we have the following outcome.

a	b	Greatest Common Divisor	Coefficient of a	Coefficient of b
8	13	1	5	-3

Examine the first line of the algorithm.

13 = 1*8 + 5

We divide 13 by 8 to get quotient 1 and remainder 5. Note our two operations which will give us the quotient and remainder.

To get the quotient of 13/8 we can use the casting operator. To get the remainder we can use the modulus operator, 13 % 8.

In the first line of the algorithm, b = 13, and a = 8.

(int)(b/a) = 1

b % a = 5

In the second line of the algorithm the new value of b is the old value of a, and the new value of a is the remainder from the previous line.

This process continues until the remainder is found to be 0.

So let's list the algorithm used to find the greatest common divisor.

1. Get a and b with a < b.

2. Introduce a variable called remainder and initialize it to 1.
(Note that since our condition for stopping the Euclidean
Algorithm is that the remainder become 0, we can set remainder
to any integer value greater than 0.)

3. Repeat the following steps as long as remainder is greater than 0.

   Let quotient equal to the integer value of b/a.

   Let remainder equal to the remainder in the division b/a.

   Let b equal to the current value of a.

   Let a equal to remainder

Now what is the value of the greatest common divisor?

Recall that the last non-zero remainder is the greatest common divisor.

Now notice the last two lines of our example.

3 = 1*2 + 1

2 = 2*1 + 0

Now notice what happens when b = 3 and a = 2.

The value of the quotient is 1.

The value of the remainder is 1.

Then b is reset to 2, and a is reset to 1.

We know that the greatest common divisor is 1 and this value has been placed into a after we complete the next to last line in the algorithm.

Now b is 2 and a is 1.

The quotient is 2, and the remainder is 0.

So we know that this is the last step in the algorithm.

However we don't make the test until the top of the loop so we still reset the values of a and b.

b is reset to 1, and a is reset to 0.

Notice that the greatest common divisor has been placed into b.

Now we go to the top of the loop and since the remainder is now 0, the loop stops.

So after we complete the Euclidean Algorithm, the variable b contains the greatest common divisor.

The code used to accomplish the Euclidean Algorithm is as follows. Assume that quotient, b, and a are defined to be integers.

int remainder = 1;

while (remainder > 0) {
   quotient = (int)(b/a);
   remainder = b % a;
   b = a;
   a = remainder;
}

Notice the placement of the assignment statements.

Now let us modify this algorithm to compute the coefficients in the table.

First b is reassigned to the value of a. Then a is reassigned to the value of remainder.

The order is important. If we reassign the value of a first, then we have lost the old value of a. Now let us modify this algorithm to compute the coefficients in the table.

Examine the first column of the table.

      1
0  1  1
1  0  1

Let us assign variable names to make the discussion easier to follow. In the first row let us call the two entries coef_a and coef_a1, and the two entries in the second row coef_b and coef_b1.

                                
                                     1 (quotient)
0 (coef_a) 1 (coef_a1)               1
1 (coef_b) 0 (coef_b1)               1

Now to compute the entry in the top row we use the formula

quotient*coef_a1 + coef_a

To compute the entry in the bottom row we use the formula

quotient*coef_b1 + coef_b

Once these values have been computed, we then will adjust these variables to point to the new values.

              1 (quotient)
0  1 (coef_a) 1 (coef_a1)
1  0 (coef_b) 1 (coef_b1)

Now let us see how these values change as we go through the Euclidean Algorithm.

      1          1 (quotient)
0  1  1 (coef_a) 2 (coef_a1)
1  0  1 (coef_b) 1 (coef_b1)

      1  1          1 (quotient)
0  1  1  2 (coef_a) 3 (coef_a1)
1  0  1  1 (coef_b) 2 (coef_b1)

      1  1  1          1 (quotient)
0  1  1  2  3 (coef_a) 5 (coef_a1)
1  0  1  1  2 (coef_b) 3 (coef_b1)

Notice that the computation of a new column in the table depends upon the quotient and the two values directly to the left of the position.

So we can modify the Euclidean Algorithm to make these computations.

Note one problem however.

When we wish to compute the new value of coef_a1, it depends upon both coef_a1 and coef_a.

the new value of coef_a1 = quotient*coef_a1 + coef_a

After this computation is complete, the value of coef_a is the old value of coef_a1.

But how can I make these two variables the correct values?

I can't simply make the assignment

coef_a1 = quotient*coef_a1 + coef_a

because I will lose the current value of coef_a1.

I can't assign coef_a1 into coef_a before I compute the new value of coef_a1 because I need the current value of coef_a.

One solution is to store the value of coef_a1 into a temporary variable, compute the new value of coef_a1, and then assign the stored value of coef_a1 into coef_a.

The algorithm for doing this is

store coef_a1 into a temporary integer variable
compute the new value of coef_a1
copy the stored value of coef_a1 into coef_a

We can compute the new value of coef_b in the same way. Now a question to ask is what will be the values of these variables when the Euclidean Algorithm stops. Notice that in the last column listed we have the last non-zero remainder. That is after we compute the quotient 2 and the remainder 0 we again recompute the values of coef_a1 and coef_a. So we will have one more column included.

      1  1  1  1           2 (quotient)
0  1  1  2  3  5 (coef_a) 13 (coef_a1)
1  0  1  1  2  3 (coef_b)  8 (coef_b1)

After the variables are calculated, then the Algorithm stops. So after the Euclidean Algorithm stops, the absolute values of the coefficients of a and b are stored in the variables coef_a and coef_b, respectively.

So now we can test to see which product is larger, coef_a*a or coef_b*b, and then the one that is smaller will have a negative coefficient.

Now let us modify our Algorithm.

1. Get a and b with a < b.

2. Introduce a variable called remainder and initialize it to 1.
(Note that since our condition for stopping the Euclidean
Algorithm is that the remainder become 0, we can set remainder
to any integer value greater than 0.)

3. Introduce a new variable called coef_a and initialize it to 0.
   Introduce a new variable called coef_a1 and initialize it to 1.
   Introduce a new variable called coef_b and initialize it to 1.
   Introduce a new variable called coef_b1 and initialize it to 0.
   Introduce an integer called temp.

4. Repeat the following steps as long as remainder is greater than 0.

   Let quotient equal to the integer value of b/a.

   Store coef_a1 into temp.

   Compute the new value of coef_a1.

   Store temp into coef_a.

   Store coef_b1 into temp.

   Compute the new value of coef_b1.

   Store temp into coef_b.

   Let remainder equal to the remainder in the division b/a.

   Let b equal to the current value of a.

   Let a equal to remainder

So when this algorithm completes, the greatest common divisor will be in the variable b, the absolute value of the coefficient of a will be in coef_a, and the absolute value of the coefficient of b will be in coef_b. To decide which coefficient should be negative we make a simple test.

(Note here that we need to use the original values of a and b.)

if (coef_a*a < coef_b*b)
   negate coef_a
else
   negate coef_b

One last part of the program is to test for the case where a is a divisor of b. In this case we don't need to carry out the Euclidean Algorithm because we know that the greatest common divisor of a and b is a. The coeffients of a and b will be 1 and 0.

The algorithm to accomplish this is

if (a is a divisor of b)
   report that a is the greatest common divisor of a and b.
   report that the coefficient of a is 1.
   report that the coefficient of b is 0.
else {
   carry out the Euclidean Algorithm.
   report the greatest common divisor.
   report the coefficient of a.
   report the coefficient of b.
}

Now let's list the complete algorithm. One thing we need to keep in mind is that the values of b and a will be changed through the algorithm. So since I need those original values later, I will store them in temporary variables once they are read in.

1. Introduce the integer variables, a, b, quotient, remainder,
temp, coef_a, coef_a1, coef_b, coef_b1, temp_a, and temp_b. a
and b will be input from the user. We can swap their values
if necessary. After a and b are read in, copy them into temp_a
and temp_b, respectively.

2. if (a is a divisor of b) {
      report that a is the greatest common divisor of a and b.
      report that the coefficient of a is 1.
      report that the coefficient of b is 0.
   } else
      go to step 3.

3. while (remainder is greater than 0) {
      let quotient = (int)(b/a)

      let temp = coef_a1

      let coef_a1 = quotient*coef_a1 + coef_a

      let coef_a = temp

      let temp = coef_b1

      let coef_b1 = quotient*coef_b1 + coef_b

      let coef_b = temp

      let remainder = b % a

      let b = a

      let a = b
   }

   report that b is the greatest common divisor
   
   if (coef_a*temp_a is less than coef_b*temp_b)
      let coef_a = -1*coef_a
   else
      let coef_b = -1*coef_b

   report that coef_a is the coefficient of temp_a

   report that coef_b is the coefficient of temp_b

Now let us translate this algorithm into Java code.

import java.io.*;

public class GCD {

   public static void main(String[] args) throws IOException {
      int a,b,quotient,remainder = 1;
      int coef_a = 0,coef_a1 = 1,coef_b = 1,coef_b1 = 0;
      int temp,temp_a,temp_b;

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

      System.out.println("Please enter the value of a");

      a = new Integer(keyboard.readLine()).intValue();

      temp_a = a;

      System.out.println("Please enter the value of b");

      b = new Integer(keyboard.readLine()).intValue();

      temp_b = b;

      if (b % a == 0) {
         System.out.println("The greatest common divisor of " + a + " and " + b + " is " + a + ".");
         System.out.println("The coefficient of " + a + " is 1.");
         System.out.println("The coefficient of " + b + " is 0.");
      } else {
         while (remainder > 0) {
            quotient = (int)(b/a);
            temp = coef_a1;
            coef_a1 = quotient*coef_a1 + coef_a;
            coef_a = temp;
            temp = coef_b1;
            coef_b1 = quotient*coef_b1 + coef_b;
            coef_b = temp;
            remainder = b % a;
            b = a;
            a = remainder;
         }
         System.out.println("The greatest common divisor of " + temp_a + " and " + temp_b + " is " + b + ".");
         if (coef_a*temp_a < coef_b*temp_b)
            coef_a *= -1;
         else
            coef_b *= -1;
         System.out.println("The coefficient of " + temp_a + " is " + coef_a + ".");
         System.out.println("The coefficient of " + temp_b + " is " + coef_b + ".");
      }
   }

}

Here is sample output from the program.

Please enter the value of a
8
Please enter the value of b
13
The greatest common divisor of 8 and 13 is 1.
The coefficient of 8 is 5.
The coefficient of 13 is -3.

Please enter the value of a
15
Please enter the value of b
100
The greatest common divisor of 15 and 100 is 5.
The coefficient of 15 is 7.
The coefficient of 100 is -1.

Please enter the value of a
5
Please enter the value of b
10
The greatest common divisor of 5 and 10 is 5.
The coefficient of 5 is 1.
The coefficient of 10 is 0.

Please enter the value of a
10
Please enter the value of b
40
The greatest common divisor of 10 and 40 is 10.
The coefficient of 10 is 1.
The coefficient of 40 is 0.

Exam 1 will be Monday. Recall that the exam will be composed of 5 parts.

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

The defintions you should pay particular attention to are:

What is a instance variable?
What is a class variable?
What is a constructor?
What is a primitive data type?
What is a bit?
What is a byte?
What is a kilobyte?

For the short answer questions you can expect at least one of each of the following problems:

Given a decimal number convert it to binary
Given a binary number convert it to hexadecimal

For the discussion portion you can expect to be asked questions about

How we write and execute a Java program
Polya's steps in the problem solving process
The Software Life Cycle
The syntax of various statements like if, etc.

For the coding portion you will be given a simple problem, asked to develop an algorithm and then translate that into Java code.

Note that the questions on the test will not be limited to the above topics. But they will give you an idea of what you can expect on the exam.

Recall the exam topics.

Review Topics for Exam 1

Bloom's Level of Mastery 1 - 3

The student can recite facts, can recognize facts, and can state definitions.
The student can differentiate between related concepts, can paraphrase or translate into his/her own words, and can use the concept when cued. The student can explain the idea to someone else.
The student can apply the concepts to a new domain without any cues being provided.

Java is an Object Oriented Programming Language that was developed by James Gosling at Sun MicroSystems.

Steps taken in writing a Java program.

We first create a file containing source code.
We then run the program javac which compiles the code into Java bytecode. This bytecode is platform independent.
We then run the interpreter java which converts the Java bytecode into executable machine code and executes it.

What does the Java compiler create?

Java bytecode

What is main disadvantage/advantage of this approach?

bytecode is slower to execute because it must be loaded into the CPU by another program. but bytecode is portable since it is not machine dependent.

The three types of errors that can occur in programming.

Compile-time errors. These errors occur because of syntax problems with the source code. They are usually easily resolved.
Run-time errors. These errors occur during the execution of a program. Such errors would be trying to divide by 0 or open and read from a file which doesn't exist. These errors are also often easy to resolve.
Logic errors. These are errors that occur because of fundamental flows in the design and implementation of our program. They can sometimes be very difficult to resolve. Of these three types of error, logic errors are the most difficult to resolve.

What is an IDE?

Integrated Development Environment

What does JDK stand for?

Java Development Kit

CPU - the Central Processing Unit. The CPU fetches instructions from main memory and executes them.

Main Memory - the portion of memory used to hold program as they are being executed. Main memory is directly accessed by the CPU. Often main memory is a combination of RAM and ROM.

ROM - Read Only Memory.

RAM - Random Access Memory.

Kilobyte - 1,024 (2¹⁰) bytes.

Megabyte - 1,048,576 (2²⁰) bytes.

Megahertz - a unit of measurement for how fast a system clock is ticking. 1 megahertz is 1 million cycles per second. Some systems are rated as much as 1000 megahertz or 1 gigahertz. The original IBM PC was 4.7 MHz.

microprocessor - when a CPU is manufactured on a single chip, it is referred to as a microprocessor.

microcomputer - a computer based on a microprocessor.

cache memory - extra fast memory that can sit between the processing unit and main memory. Instructions can be fetched faster from cache than from main memory.

The Binary System or base 2. Consists only of the digits 0 and 1. The two units are usually referred to as bits. Bits are the smallest unit that a computer can understand. Instructions at the machine level consist of sequences of 0's and 1's.

The Octal System or base 8. Consists of the digits 0-7.

The Decimal System or base 10. Consists of the digits 0-9.

The Hexadecimal System or base 16. This is a system of numbers with 16 digits. The ordinary digits 0-9 are used and the letters A,B,C,D,E, and F are also used. Their decimal equivalents are, respectively, 10,11,12,13,14, and 15.

What is the connection between binary, octal, and hexadecimal?

They are based on powers of 2

Conversions between number systems

Binary -> Decimal
Decimal -> Binary
Binary -> Octal
Octal -> Binary
Binary -> Hexadecimal
Hexadecimal -> Binary

How many different states can n bits represent?

2ⁿ

What is a bit?

A binary digit, i.e. 0 or 1

What is a byte?

a collection of 8 bits

What is ASCII?

The American Standard Code for Information Interchange

How do we represent both positive and negative numbers?

Use one bit as a sign bit

What is the range of numbers that can be represented?

-2^n-1 to 2^n-1-1

Polya's steps in the problem solving process.

Understand the problem - This is an essential step because if you don't understand what you are being asked to solve, you are unlikely to be able to solve it.
Design or Devise a plan - A plan is called an algorithm. It is a finite sequence of logical steps that terminate to produce a desired outcome.
Implement the Plan
Evaluate the Outcome

The Software Life Cycle

BIRTH

Requirements specification. Here we must understand the problem and decide what the desired outcome should be.
Analysis - consider the requirements specifications and raise and questions about Input/Output issues, etc.
Design - we come up with an algorithm. An algorithm should not contain code that is specific to the language with which we are dealing. It should simply be an abstract solution of the problem. For example, one step in algorithm might state: load an integer from a file, but not discuss any specific Java code used to open a file.
Implementation - after we have come up with a good plan, then we put it into action. We write specific code to implement our plan. Sometimes it is tempting to skip the design phase, but very often this will cause you to be unsuccessful in solving the problem.
Test/Debug - more than likely when we are writing a program that is not trivial, there will be errors. The purpose of testing our program is to try to find errors. However, through testing alone we cannot prove that our program will always work correctly. We simply use testing to try to discover any problems and try to correct them. Removing the problems we find is called debugging. Where did this term originate?
Maintenance - once we have successfully written a program to solve a problem, we must maintain it, that is, while a client is using the program they may discover problems with it or decide that would like something new added to it.
Ugrading - when new errors are discovered or new requirements are requested we must modify our original solution

DEATH

Three types of execution

Sequential Execution
Conditional Execution
1. if
2. if - else
3. switch
Repeated Execution
1. while
2. do-while
3. for

What is the syntax of each of these?

What are the flowchart symbols used for the following?

Start and End
User Input
Complex block
If
If - else
Switch
Do -while
While
For

The sytax of a class header. <access control keyword> class classname <extends A> <implements B, C, etc.>

The parts surrounded with < and > are optional.

What is a literal?

a stated value

What are the whole number primitive data types? How many bytes are used to store each?

int - 4 bytes

long - 8 bytes

What are the real number primitive data types? How many bytes are used to store each?

float - 4 bytes

double - 8 bytes

What is the character primitive data type? How many bytes are used to store it?

char - 2 bytes

What are the rules for creating identifiers?

You can use any alphabetical character, uppercase or lowercase, the digits 0-9, _, or $.
It can't start with a digit.
Java is case-sensitive.
We cannot use a Java keyword.

What is the difference between a variable and a constant?

a variable can change throughout the program.

a constant is fixed.

How do we distinguish between them in Java?

the keyword final

What are the unary operators?

+ -

What are the binary multiplicative operators?

* / %

What are the binary additive operators?

+ -

What is the casting operator? What does it do?

causes a value that is currently of one type to be stored in a varialble of another type.

What is the syntax for a cast?

(data - type) expression

What is the precedence Java follows in evaluating an arithmetic expression?

Parentheses

Unary Operators

The Binary Multiplicative Operators

The Binary Additive Operators

What are the comparison operators in Java?

< <= > >= != ==

What are the shortcuts we can use with the binary operators and assignment operators?

*= += -=, etc.

What is the output of the logical and?

A boolean value

What is the output of the logical or?

A boolean value

What symbol is used to represent the logical and?

What symbol is used to represent the logical or?

What are the truth tables for the logical and and the logical or?

What is the logical primitive data type called?

A boolean

What is a package?

a collection of related classes

What is the rule for creating a package?

You must have the statement package packagename in each .java file which is part of the package. Each .class file must be stored in a directory with the name of the package.

What is the CLASSPATH?

An environment variable which tells the compiler and interpreter where to find Java .class files.

How does the Java compiler and interpreter use the CLASSPATH?

What are four things contained in the signature of a method?

Access Control Keyword
Return Type
Name
Formal Parameter List

What distinguishes a Java application from a Java applet?

Java applications have a main method

How do we use packages in our programs?

we use the import statement

What is the statement used to load a package into our program?

import

What package is automatically available when we write a program?

java.lang

What are the five primary components of a class definition?

Instance Methods
Instance Variables
Class Methods
Class Variables
Constructors

How does a class differ from an object?

a class is abstract. an object is concrete.

How do we distinguish between class variables and instance variables?

the keyword static

What is the job of the constructor?

to create a new instance of a class

What is the signature of the constructor of a class?

access control keyword

name of class

formal parameter list

What is the sigature of a main method?

What two classes are used to obtain input from the user?

InputStreamReader

BufferedReader

What package do we have to import in order to use those classes?

java.io

What method is used to get the input? What type does it return?

readLine(). it returns a string.

How do we convert it into an integer or real variable?

use a wrapper class

What is a wrapper class?

What is the extends clause used for?

What statement do we use to get output?

System.out.println

What package needs to be imported in order to use that statement?

none. java.lang is already imported.

What is a subclass?

What is a superclass?

What is a parent class?

What is single inheritance?