CS 1401, Exam #2

Date: Friday, October 6, 2006, 9:30 am
Name (please type legibly, ideally in block letters): ______________________________________________________________________

1. Use if-statements to write down a code that, given three numbers n1, n2, and n3, finds the largest of these three numbers, and assigns this value to the variable whose name is largest.

Hint: you do not need to read anything from the keyboard or from a file, you do not need to print anything to the screen or place it into a file, just compute and assign. Assume that n1, n2, and n3 have been assigned some values already, which are the numbers that you are comparing.


Solution:

if (n1 >= n2 && n1 >= n3)
  largest = n1;
else if (n2 >= n1 && n2 >= n3)
  largest = n2;
else
  largest = n3;

2. Write down a code that, given two strings s1 and s2, sorts them in alphabetic order: i.e., if s1 follows s2 in alphabetic order, your code should swap the strings. You can assume that both s1 and s2 only contain small letters.

Example: if s1 is "table" and s2 is "chair", then after your code, s1 should contain "chair" and s2 should contain "table". Trace your code, step by step, on this example: draw all the boxes and show how their values change after each operation.

For extra credit: make the code work also if some of the letters are capital letters.

Solution:

if (s1.compareTo(s2) > 0)
  {String temp = s1;
   s1 = s2;
   s2 = temp;
  }

Tracing:

originally

 --------    -------   -------    -------
|  22    |  |   33  | | table |  | chair |
 --------    -------   -------    -------
   s1           s2        22        33

after the line String temp = s1:

 --------    -------   -------    -------   -------
|  22    |  |   33  | | table |  | chair | |   22  |
 --------    -------   -------    -------   -------
   s1           s2        22        33       temp

after the line s1 = s2:

 --------    -------   -------    -------   -------
|  33    |  |   33  | | table |  | chair | |   22  |
 --------    -------   -------    -------   -------
   s1           s2        22        33       temp

after the line s2 = temp:

 --------    -------   -------    -------   -------
|  33    |  |   22  | | table |  | chair | |   22  |
 --------    -------   -------    -------   -------
   s1           s2        22        33       temp

Extra credit:

if ((s1.toLowerCase()).compareTo(s2.toLowerCase()) > 0)
  {String temp = s1;
   s1 = s2;
   s2 = temp;
  }

3. Draw the truth tables for "and", "or", and "not" operations. Use these truth tables to find the truth value of the statement 3 < 5 && 2 < 4 || 4 < 2. Explain precedence of different logical operations, and how this precedence is related to precedence of different arithmetic operations.

For extra credit: what is the difference between && and &? What is the advantage of each of these operations? Give an example when they lead to different results.


Solution:

 ------------------------------------
| A |  B | A and B | A or B | not A |
 ------------------------------------
| F |  F |    F    |   F    |   T   |
 ------------------------------------
| F |  T |    F    |   T    |   T   |
 ------------------------------------
| T |  F |    F    |   T    |   F   |
 ------------------------------------
| T |  T |    T    |   T    |   F   |
 ------------------------------------

3 < 5 is True, 2 < 4 is True, 4 < 2 is False, so the above statement is
(T && T) || F. By the table, T && T is T, so we get T || F, which is True.

Precedence: negation ! has the highest precedence, then &&, then ||.

Inside the computer, True is 1, False is 0, so && is actually
multiplication. Or is almost addition, and precedence for && and || is
the same as for multiplication and addition.

Extra credit: in computing A && B, if the computer finds out that A is
false, it stops computing and assigns the value False to A && B without
bothering to compute the truth value of B. If we use & instead of &&,
the computer evaluates both A and B. An example where we get different
results:

* 2>4 && (1/0 > 0) returns false because 2>4 is false.

* on the other hand, 2>4 & (1/0 > 0) returns an error message because
1/0 is not defined.


4. Use the while loop to write a piece of code that, given an integer n, finds the smallest natural number k for which 2^k > n. In other words, your code should find the smallest power of two which is larger than a given integer n. For example, for n = 7, we should return 3, because 2^3 = 8 > 7, and 3 is the smallest such power: 2^2 = 4 < 7. Trace your code for n = 7. Idea: start with k = 0, and while the condition 2^k > n is not satisfied, keep increasing k by 1. Trace your code step-by-step for n = 7.

Reminder: to compute the power a^b in Java, you can use the operation Math.pow(a,b).

For extra credit: when you want to increase k by 1, what is the advantage of using k++ instead of k = k+1?


Solution:

k = 0;
while (!(Math.pow(2,k) > n))
  k++;
result = k;

Tracing:

First k = 0. The condition !(2^0 > 7), i.e., not (1 > 7),
is satisfied, so we increase k by 1; the new value of k is thus 1.

The condition !(2^1 > 7), i.e., not (2 > 7), is still satisfied, so
we increase k by 1; the new value of k is thus 2.

The condition !(2^2 > 7), i.e., not (4 > 7), is satisfied, so we
increase k by 1; the new value of k is thus 3.

The condition (2^3 > 7), i.e., 8 > 7, is true, so !(2^3 > 7) is false,
and we get out of the while loop. So, the variable result is assigned a
value k = 3.

Extra credit: in general, addition c = a + b means that we fetch a, fetch b,
and then send the result to c. In the computer, fetching requires
looking into the huge memory, so it takes much longer than performing
any arithmetic operation. Operation k++ requires only one fetching of k,
so it requires only half of the time of addition.

5. To convert a decimal integer n to binary form, you repeatedly divide n by 2 and keep the remainder until you get 0. Reading the remainders from bottom to top provides the desired binary number. Use this algorithm to convert 13 to binary code. Check the result by converting the binary number back into the decimal code.

Reminder: 137 in decimal code means 1 * 10^2 + 3 * 10^1 + 7 * 10^0. Similarly, 101 in binary code means 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 1*4 + 0*2 + 1*1 = 4 + 1 = 5.


Answer:

13 / 2 = 6 rem 1
 6 / 2 = 3 rem 0
 3 / 2 = 1 rem 1
 1 / 2 = 0 rem 1

When we read the remainders from bottom to top, we get 1101. In binary
code, it means 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 =
1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 8 + 4 + 1 = 13.