CPSC 124, Fall 2005
Answers to the First Test

Question 1: There are two types of errors that can occur in a program: syntax errors and semantics errors. Explain what is meant by each of these terms, and give a specific example of each type of error.

Answer: Syntax refers to the grammar or structure of a language. A program that has a syntax error cannot even be compiled, because it is not a legal program. Semantics refers to the meaning of a program. Because a computer can only follow instructions, and not understand what they are meant to do, the computer cannot find semantics errors. A program that has a semantics error can be compiled and run, but it will not do what the programmer intended.

An example of a syntax error would be a missing semicolon at the end of a statement, or using a variable that has not been declared. The computer will find these errors at compile time.

An example of a semantics error would be a for loop that says "for (i = 0; i <= 100; i++)" when the programmer wants to repeat a task 100 times. In fact, the for loop repeats the task 101 times, so the program does not do what the programmer intended.

Question 2: Java has eight built-in primitive types. List any four of them, and state briefly what type of data is represented by each primitive type in your list.

Answer: The eight primitive types are byte, short, int, long, float, double, char, and boolean. (Note that String is not a primitive type.) The most common primitive types are int, double, char, and boolean, so a typical answer to this question would be:

           int --- values of type int are whole numbers that can be represented using 32 bits.

           double --- values of type double are real numbers with about 17 decimal places of accuracy.

           char --- values of type char are individual characters from the Unicode character set.

           boolean --- the only values of type boolean are true and false

Question 3: What is meant by a literal? Explain the difference between a literal and the value that is represented by a literal.

Answer: A literal is a sequence of characters that is typed in a program to represent a constant value. There are numeric literals such as 37 and 18.75, character literals such as 'A' and '\n', the boolean literals true and false, string literals such as "Hello" and "He said \"Hello.\"\n", and so on. A literal is the way a value is typed, but it is not itself the value. The actual value in the computer is a binary number. For example, the actual value represented by the character literal 'A' is a 16-bit binary number that stands for the character A in the Unicode character set.

Question 4: Suppose that x and y are variables of type double that have already been declared and assigned values. Write a code segment that will compare the values of x and y, and will tell the user the result of the comparison by outputting one of the messages "x is bigger", "y is bigger", or "they are the same".

Answer: This can be done either with an if...else if statement or with three separate if statements. The first option is somewhat more efficient, since it doesn't make unnecessary tests after the answer is already known. Here are both solutions:

         if ( x > y )                                        if ( x > y )                                  
            System.out.println("x is bigger");                  System.out.println("x is bigger");         
         else if ( x < y )                                   if ( x < y )                             
            System.out.println("y is bigger");                  System.out.println("y is bigger");         
         else                                                if ( x == y )                                         
            System.out.println("they are the same");            System.out.println("they are the same");   

If you like to include braces in your if statements, even when they are unnecessary, then these become:

         if ( x > y ) {                                      if ( x > y ) {                                 
            System.out.println("x is bigger");                  System.out.println("x is bigger");         
         }                                                   }
         else if ( x < y ) {                                 if ( x < y ) {                            
            System.out.println("y is bigger");                  System.out.println("y is bigger");         
         }                                                   }
         else {                                              if ( x == y ) {                                        
            System.out.println("they are the same");            System.out.println("they are the same");   
         }                                                   }

Question 5: An integer N is said to be prime if it is greater than 1, and for every integer $i$ from 2 to $N-1$ (inclusive), N % i != 0 (that is, N is not evenly divisible by i). Write a complete program (starting with "public class\dots") that tests whether an integer that is input by the user is prime. The program should ask the user for an integer and read the response, and it should tell the user whether the number is or is not prime. If the number is less than 2, you can say immediately that it is not prime. Otherwise, you must use a loop to test for divisibility by any integer in the appropriate range.

Answer: Here is one possible answer:

         public class PrimeText {
            public void main(String[] args) {
               int N;  // the number to be tested for primality
               System.out.print("Enter a number to be tested for primality: ");
               N = TextIO.getlnInt();
               if ( N < 2 )
                  System.out.println( N + " is not prime." );
               else {
                  boolean isPrime;  // Value will tell whether N is prime.
                  int i;
                  isPrime = true;   // Assume N is prime, unless forced to change our mind.
                  for ( i = 2; i < N - 1; i++ ) {
                     if ( N % i == 0 ) {
                        isPrime = false;   // We have found evidence that N is not prime.
                        break;             // No need to go on testing, since we know the answer.
                  if ( isPrime )
                     System.out.println( N + " is prime." );
                     System.out.println( N + " is not prime." );

Question 6: Suppose that str is a variable of type String that has already been assigned some value. Write a for loop that will print all the characters in the string str, with one character on each line of output.

Answer: Recall that str.length() tells how many characters are in the string. The characters are numbered from 0 to str.length()-1, and character number i is referred to as str.charAt(i). Here is one possible answer:

         int i;
         for ( i = 0; i < str.length(); i++ ) {
            System.out.println( str.charAt(i) );

Question 7: Suppose that x and y are variables of type double. Suppose that the value of x is 10.0, and the value of y is 2.0. Find the value of each of the following expressions:

             a)  x + 3 * y
             b)  x / y / 2.0
             c)  Math.pow(x,y)
             d)  x > y && y < 0
             e)  (int)(x / 3.0)


             a)  x + 3 * y   is   16.0   (x + 3 * y = 10.0 + (3 * 2.0) = 10.0 + 6.0 = 16.0)

             b)  x / y / 2.0   is   2.5   (x / y  / 2.0 = (10.0 / 2.0) / 2.0 = 5.0 / 2.0 = 2.5)

             c)  Math.pow(x,y)   is   100.0   (Math.pow(x,y) means xy, and 102 = 100))

             d)  x > y && y < 0   is   true   (this is a boolean expression)

             e)  (int)(x / 3.0)   is    3   (x / 3.0 = 3.333..., but (int) takes the integer part)

Question 8: Show the exact output that will be produced when the computer executes the following code segment. (If your answer is wrong, you might get some partial credit by explaining your reasoning.)

             int a, b, c;
             a = 33;
             b = 12;
             while ( b > 0 ) {
                 c = b;
                 b = a % b;
                 a = c;
                 System.out.println("a = " + a);
                 System.out.println("b = " + b);
             System.out.println("Answer is:  " + a);

Answer: The expression "a % b" means the remainder when a is divided by b. For example, 33 &12 is 9, so the first time through the loop, b becomes 9 and a becomes 12. Continuing in this way, the output is seen to be:

             a = 12
             b = 9
             a = 9
             b = 3
             a = 3
             b = 0
             Answer is:  3

(Note: This code might look like nonsense, but as a matter of fact, it produces a meaningful and useful answer. The output of the code is the greatest common divisor of the original values of a and b, that is, the result is the largest positive integer that is a common divisor of both a and b. The algorithm that is used here to compute the greatest common divisor is known as Euclid's algorithm, and it was one of the first algorithms ever invented.)

Question 9: Approximately what do you expect the value of total to be after the following code segment is executed? Why?

             int i, total;
             total = 0;
             for ( i = 0; i < 100; i++ ) {
                 if ( Math.random() < 0.5 )
                     total = total + 1;
                     total = total + 2;

Answer: The if statement has a 50% chance of adding 1 to the total and a 50% chance of adding 2 to the total. Since the loop is repeated 100 times, we expect that 1 will be added to total about 50 times, and 2 will be added about 50 times. If it were exactly 50 times in each case, the final value of total would be 150. Since the process is random, we don't expect to get exactly 150, but the answer is probably something pretty close to that. (In theory, it could be anything between 100 and 200, but in practice the answer is almost always pretty close to 150.)

Question 10: One way to approach the task of developing an algorithm is to use pseudocode and stepwise refinement. What does it mean to "develop an algorithm?" How can pseudocode and stepwise refinement be used in the process? (An example would be helpful.)

Answer: An algorithm is an unambiguous step-by-step process that performs a certain task and finishes in a finite number of steps. A computer program is an expression of an algorithm in a programming language. To develop an algorithm means to start with a problem and to create an algorithm that will solve that problem. The goal is to come up with a step-by-step procedure that can be expressed in program code, so that it will be possible to use a computer to solve the problem.

The term "pseudocode" refers to informal, English-like descriptions of algorithms. When using pseudocode, there is no need to follow the strict, formal syntax of a programming language. Also, it is not necessary to include all the details of the algorithm, at least in the early stages of development.

To use stepwise refinement, a short pseudocode algorithm is written. The goal is to give a coarse outline of the major steps that need to be taken to solve the problem. The outline is still an algorithm is that it describes a step-by-step process for solving the problem, but with much less detail than is needed in a computer program. Once the first outline of the algorithm is written, it can be "refined." That is, detail can be added to the algorithm by breaking down the steps in the pseudocode algorithm into smaller steps. This refinement step is repeated until the pseudocode algorithm is detailed enough to be translated directly into program code.

As an example, consider problem 5 on this test. A first rough outline of the solution could be:

          Get a number from the user
          Test if the number is prime
          Tell the user the answer

This is a very rough pseudocode algorithm, and it is the the first step in the development of an algorithm by stepwise refinement. The next step could refine this to:

          Ask the user to enter a number
          Read the user's number
          if the number is less than 2
              tell the user it's not prime
              test whether the number has a divisor
              if it does
                 tell the user it's not prime
                 tell the user it's prime

This is more detailed, but the test for divisibility needs still more detail. A loop has to be used to test numbers in the appropriate range. Also, it's useful at this stage to have some names for the data objects in the algorithm. So the next step could be to refine this to:

          Ask the user to enter a number
          Let N be the user's input number
          if the number is less than 2
              tell the user N is not prime
              Let isPrime = true 
              for each i from 2 to N-1
                 if N is divisible by i
                    isPrime = false
              if isPrime is true
                 tell the user N is not prime
                 tell the user N is prime

This pseudocode algorithm is detailed enough to be translated directly into Java code.

David Eck, 1 October 2005