For questions 1-12 answer the questions using the bubble sheet provided.

(Total Points: 12)

For True, fill in the bubble for a.

For False, fill in the bubble for e.

Q1: Let A and B be any two finite sets. Then, |A x B| = |B x A|.

Q2: A monotonically increasing function is always one-to-one.

Q3: The cardinality of the set { 1, 2, {3, 4}} is 4.

Q4: A and B are any two finite sets. Then, |A ∩ B| < |A ∪ B|

Q5: Set A - B is always a subset of set A

Q6: Set (A - B) and B are always disjoint

Q7: The number (2723426000)7  is a multiple of (49) 10

Q8: (-32) mod 5 = 2

Q9: 2n   is O(3n)

Q10: Let m, n, q be any positive integers. m < n ⇒ (m mod q) < (n mod q)

Q11: Let X be the set of positive integers that are multiples of 2. Let Y be the set of positive integers that are a multiple of 4. Then, |X| = |Y|

Q12:          (2353512)7  * (65235)7   > (2353512)8  * (65235)8

Note numbers are same only bases are different

For questions 13-21 answer the questions using the bubble sheet provided.

(Total Points: 9)

For finite, fill in the bubble for a.

For countably infinite, fill in the bubble for b.

For uncountably infinite, fill in the bubble for c.

What is the cardinality of the following sets?

Q18:          Which pairs of numbers are relatively prime? (Circle all)

A. 12 and 30

B. 5 and 15

C. 22 and 45

D. 12 and 25

Q19: The function n4   is (Circle all)

A.  O(n3)

B.  O(n5)

C.  O(2n)

D.  O(n!)

E.  O(Ln⌋4)

Q20: The function n4   is (Circle all)

A.  Q(n3)

B.  Q(n5)

C.  Q(2n)

D.  Q(n!)

E.  Ω(Ln⌋4)

Q21:The function n4   is (Circle all)

A.  Θ(n3)

B.  Θ(n5)

C.  Θ(2n)

D.  Θ(n!)

E.  Θ(Ln⌋4)

Q22:          (1pt) What is the largest 8 digit number in base 7 (You can leave your answer

with terms that include ab . Do not need to find the exact decimal number.)

Q23:          (2pts) Identify and explain the relation between 32n and 23n  in terms of the Big-O,

Big-Omega.

Q24:         (2pts) Find the GCD of 34 and 45 using Euclid’s method.

Q25:         (2pts) Find a function from Z+ → Z+ which is one-to-one but not monotonically

increasing or monotonically decreasing.

Q26:          (1pt) Set A contains 10 elements. Set B contains 3 elements. What are the

minimum and the maximum number of elements in set A - B.

Q27:         (2pts) Is the function f: RxR → R+  f(m, n) = 2m3n one-to-one? Explain.

Q28:

(2pts) Is the function f: RxR → R+  f(m, n) = 2m3n onto? Explain.

Q29:         (2pts) Convert 375 to base 7. Show your work.

(2pts) Assuming base 7 arithmetic, answer what is

4233

4

Q31:          (3pts) Let X be the set of complex integers. In other words, X = { m + i n | m and

n are integers }.

Q32:         (4pts) Find a 1 a2  a3 for following sequences

an = 2n + 3

an = 2n + 7

an = 2an- 1 + 2, a0 = 2

an = an- 1 + 9, a0 = 2

Q33:          (2pts) What is 2x  mod 13 if x = (1100101010)2  Show your work. Do not use

methods other than those taught in class. (No credit for guessing the right answer. Circle the answer in the box below.)

Q34:          (2pts) What is 2602 mod 13? Show your work. Do not use methods other than

those taught in class. (No credit for guessing the right answer.  Circle the answer in the box below.)

Q35:         (3pts) Write the following proof

Let m be a (fixed) integer

h1 = ∃x m = 15x

c1 = ∃x m = 5x

c2 = ∃x m = 3x

Show that h1 ⇒ (c1 ∧ c2) using proof chain method

Q36:          (2pts) In your own words, write the proof that we did in class to show that real

numbers are not countable.

Note: I am not looking for vague answers like there are too many real numbers because there are numbers like ½, pi, etc. I am looking for specific proof that any function from Z+ to R cannot be a bijection.

Bonus Questions

Q37:          (1pt) Find functions f(x) and g(x) such that f(x) = Θ(g(x)). However, 2f(x)  is not

Θ(2g(x)) Explain your answer.

Q38:          (1pt) Identify constraints to show when a sequence is simultaneously an

arithmetic sequence and a geometric sequence. Explain you answer.

Q39:          (1pt) Prove or disprove

The set of `finite subsets of N’ countable.