Computer Science
15-111 (Sections A & B), Spring 2007
Quiz 1 Practice
This is optional. It will not be submitted and it will not be
graded.
This practice sheet is meant to help
you prepare for Quiz 1. While it is
representative of the kinds of problems you can generally expect, it may not be
comprehensive – the quiz may include questions related to any topic we have
covered in class, in readings, or in homework, and include any types of
questions.
I will review the answers tonight
from 6-7pm in Wean 5419-D (after reviewing the hw2 solution set from 5-6pm). Attendance at either session is optional.
==============================
The
following problems are to be solved without use of a calculator or a computer. Work them by hand. (This is what you will need to do on upcoming
quizzes and tests!).
1. The expression Math.round(4*Math.random()) does not generate all possible
values equally often. For each possible
value, indicate the expected frequency (as a percentage), and briefly explain
why this is so.
2. Consider the following method:
public static int foo(int x) {
if (Math.abs(x) > 20) return x/2;
else return x + foo(-2*x);
}
a. What is the result of foo(3).
b. What happens on a call to foo(0)?
3. Express -177 in 8-bit 2’s complement
(that is, as a signed byte).
4. What will the following code print
out?
System.out.println(0x65);
System.out.println(065);
System.out.println(65);
System.out.println((char)65);
System.out.println((byte)65);
System.out.println((byte)(65+ 'A'));
System.out.println((int)(char)-1);
5. How can you quickly tell if a binary
number is even or odd? Does this work
for negative numbers (in two’s complement), too?
6. Convert any number from/to
binary/octal/decimal/hexadecimal.
7. Evaluating the expression (5 % 0)
results in a division by zero
exception. Explain.
8. TRUE or FALSE: if (a !=0), then ((x – (x % a)) % a) always equals 0.
9. Use a truth table to prove
DeMorgan’s Laws. This shows that you
recan rewrite And(x,y) using only Or(x,y) and Not(x). Thus, we really don’t need the &&
operator, do we? But it is convenient!
10. Nand(x,y) is a boolean function that
returns true iff And(x,y) returns false (“Nand” means “Not And”).
a. Show that you can rewrite Not(x)
using only Nand’s.
b. Show that you can rewrite And(x,y)
using only Nand’s (using part (a)).
c. Show that you can rewrite Or(x,y)
using only Nand’s (use the previous question).
d. Aside (you can skip this, but it’s
fascinating):: given any logical expression, we can reduce it
to Disjunctive Normal Form (DNF), which uses only And, Or, and Not (we do this
by writing a truth table, then expressing the function as an Or of the rows where it is true, which
are expressed as an And of the
variables or their negations). This is
why we only get those three logical operators – no other ones are needed. However, we just demonstrated that you can
reduce And, Or, and Not all to a bunch of Nand’s, and so you really only need
ONE logical operator: Nand. It would be clumsy, but doable. Amazing!
11. What will the following code print
out?
int x = 4, y = 2;
if ((x++ > 4) && (--y == 1))
System.out.println("A");
System.out.printf("%2d%3.2f\n",x,Math.pow(x/y,y));
12. What will the following code print
out?
byte b = 16;
System.out.println(b*b + b == b);
int x = 16;
System.out.println((byte)(x*x + x) == x);