Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 260

Exam 2 Version A

Fall 2021

(53 points)

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 one-to-one function is always strictly increasing

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

Q5: Set  is always a subset of set A

Q6: Set  and B are always disjoint

Q7:  (- 32) mod 5 = 3

Q8: 2ⁿ  is O(3ⁿ)

Q9: One to one function is always onto

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)₇ * (65235)₇  <  (2353512)₈ * (65235)₈  

       Note numbers are same only bases are different

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

(Total Points: 9)

Bubbling instructions for Q. 13-17

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?

Q13: R - [0..1]

Q14: NxN

Q15: NxR

Q16: Irrational numbers other than pi

Q17: Number of onto functions from R to Z⁺

Q18: Circle all factors of (2723426000)₇

A. 1

B. 7

C. 49

D. 343 (=7³)

E. 2401 (=7⁴)

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

A. 27 and 42

B. 11 and 44

C. 1 and 12

D. 25 and 36

Q20: Alice has a secret function f in her mind. She tells that the function is in . What can you say about f (circle all correct choices)

A. f must be in

B. f may be in

C. f cannot be in

D. f may be in

E. f cannot be in

Q21: Alice has a secret function f in her mind. She tells that the function is in . What can you say about f (circle all correct choices)

A. f must be in

B. f may be in

C. f cannot be in

D. f may be in

E. f cannot be in

Q22:  (1pt) What is the largest 8 digit number in base 7 (You can leave your answer with terms that include a^b. Do not need to find the exact decimal number.)

Q23: (2pts) Identify and explain the relation between 5²ⁿ and 2⁵ⁿ in terms of the Big-O, Big-Omega.

Q24: (2pts) Find the GCD of 87 and 41 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 4 elements. What are the minimum and the maximum number of elements in set.

Q27: (2pts) Is the function f: one-to-one? Explain.

Q28: (2pts) Is the function f: onto? Explain.

Q29: (2pts) Convert 365 to base 8. Show your work.

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

    3525

x        4

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

Is |X| = |Z+|

Explain

Q32: (4pts) Find a₁ a₂ a₃ for following sequences

a_n = 2n² + 3

a_n = 3ⁿ + 7

a_n = 2a_n-1 + 3, a₀ = 2

a_n = a_n-1 + 6, a₀ = 2

Q33: (2pts) What is 2^x mod 13 if x = (1100101110)₂ 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 2⁶⁰³ 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: (2pts) Let f be a given function from Z⁺ to P(Z⁺). Find a set such that for any n,  

(P(Z⁺) is the powerset of Z⁺)

Note: Do not use the fact that to P(Z⁺).is uncountable. Your proof would be similar (in spirit) to the proof showing that set of real numbers is uncountable. You should provide a construction for S that uses f to determine if integer n should be included in S or not.

(Hint: Choose S = { n | some property relating n and f(n) } )

Q36: *(1pt) Without converting the numbers into base 10 show that  is a multiple of

Q37: *(1pt) Write a program to enumerate all positive rationales at least once. (Pseudo code is ok)

Q38: *(1pt) Prove or disprove

The set of `finite subsets of N’ is countable.

Q39: Use this space to answer any questions you needed more space