CS 1401, Quiz 5

Date: Wednesday, October 11, 2006
Name (please type legibly, ideally in block letters): ______________________________________________________________________

1. Draw the truth tables for "and", "or", and "not" operations. Use these truth tables to find the truth value of the statement 3 < 5 && 1 < 4 || 4 < 1. 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, 1 < 4 is True, 4 < 1 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.

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

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++ or ++k instead of k = k+1?


Solution:

k = 0;
while (!(k * k * k > n))
  k++;
result = k;

Tracing:

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

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

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

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.