CSE 260 Exam 2 Version A
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 260
Exam 2 Version A
(50 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 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?
Q13: |
R - [0 .. 1] |
Q14: |
NxN |
Q15: |
NxR |
Q16: |
Irrational numbers other than pi |
Q17: |
Number of one-to-one functions from R to Z+ |
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.
Min = |
Max = |
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 }.
Is |X| = |N|? |
Explain |
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
|
|
Justification |
1 |
|
|
2 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
2023-06-16