CIS 66 – Midterm 1 Last Name (print) ______

Fall 2002

ssn (last 4 digits) First (Name print) ______

______Signature ______

1. (20 points) Compute the following - the result must be a number

log10(100100) ______

log2(1,000,000) (approximate) ______

The bitwise result of ((1100) Ú (1010)) Ù (1001) ______

200
S / j / ______
j = 100
|A| where set A = {{{a}, b}, c} ______

|P(A)|If set A = {{{a}, b}, c} ______

|B´B| if set B = {{a, b, c}} ______

é-104/10ù ______

The prime factorization of 90. ______
The prime factorization of 10240. ______

GCD(123456, 100) ______

GCD(64, 1024) ______

LCM(64, 1024) ______

Convert A0F (base 16) to decimal. ______

Convert A0F (base 16) to binary. ______

1. continued, Compute the following - continued

Convert 70 decimal to binary. ______
Convert 70 decimal to base 3. ______

-12345 mod 100 ______

What decimal number does the 4-bit,

2’s complement number 1111 represent? ______

Represent –3 as a 2’s complement 8 bit number. ______

2. (20 points) Circle the correct answer

propositions:

If 1 + 1 = 3, then 1 + 1 = 3 True False

" x " y Ø P(x,y) Û Ø ($ y $ x P(x,y)) True False

" jÎN $ kÎN (j = k2) True False

p®Øq « (ØpÚØq) tautology contradiction contingency

(pÚØp) ® (Øq Ú q) tautology contradiction contingency

Ø(pÙq) « ØpÚØq tautology contradiction contingency

sets:

{x} Í {{x}} True False

{{}} Î {{x}} True False

{(1, a)} Í A ´ B where A = {1, 2}, B = {a, b} True False

AÈ(BÇC) Û (AÇB)È(AÇB) True False

N+1 / n-2
S / j-2 / = / S / k+1 /
True False
j = 3 / k = 0

2. (20 points) Circle True or False, continued

- ëxû = é- xù True False

3x3 + 5x + 2 is O(log(xx)) True False

If a, b, and c are integers and a | b and b | c, then a| (b + c) True False

If A and B are n by n matrices, (AB)t = BtAt True False

-1 | -72 True False

1,000,001 and 100 are relatively prime. True False

Problems that are exponential worst-case complexity are

solvable. True False

y = x + 1, xÎN, yÎN (natural numbers) injection surjection bijection

y = x + 1, xÎZ, yÎZ (the integers) injection surjection bijection

3. (5 points) Create a truth table for the proposition Øp Ù (p ® q) ® Øq

p / q
T / T
T / F
F / T
F / F

4. (5 points) Define the following sets by listing their elements if A, B, C, and D are defined as follows.

U = {a, b, c, d, e, f, g}

A = {a, b, c, d}

B = {a, c, e, g}

C = {b, d, f}

D = {a, b}

AÈB = {______}

U-A = {______}

P(D) = {______}

C´D = {______}

AÅU = {______}

5. (10 points) Find the indicated functions when f(x) and g(x) (from R to R) are defined as follows:

f(x) = 2x2 + 1 g(x) = 3x + 4

(f°g)(x) ______

(f°f)(x) ______

(g°g)(x) ______

(g°f)(x) ______

(g-1)(x) ______

f(x) is an injection (one to one). True false

f(x) is an surjection (onto). True false

g(x) is an injection (one to one). True false

g(x) is an surjection (onto). True false

6. (10 points) Assume a, b, and c are integers. Show (prove) that, if a|b and b|c, then a|c.

7. (10 points) Assume matrices A, B, and C are defined as follows. Compute AB – 2C.

A = / 3 / -2
1 / 2
/ B = / 1 / 3
0 / 1
/ C = / 2 / -3
2 / 1

8. (5 points) Provide the best possible big O estimate (that is, a big Theta estimate) for each of the following functions

f(x) = (3 x3 + 4x2+ 5 x + 2) * ( log xx + x2) ______

f(x) = (3 x3 log x) * (xlog x + log x) ______

f(x) = ( log x+ x2) / (3 x3 + 4x2+ 5 x + 2) ______

f(x) = (x! + x2)*(xx + x2)*( x2 + x) ______

n
S / x j / ______
J = 1

9. (10 points) Provide the best possible big-O estimate for f(x) = x3 + 5x2 log x + log xx. Then show (prove) that your answer is in fact a big-O estimate.

10. Define each of the following terms or symbols (6 points).

a | b (where a and b are integers)

a º b mod m

f(x) = O(g(x)) (that’s big O of course)

Two (possibly infinite) sets A and B have the same cardinality, |A| = |B|

The compound proposition p « q

The universal quantification of P(x), "x P(x)