Description

CENG223
Discrete Computational Structures
Take Home Exam 2

Question 1
If A and B are sets, prove or disprove that
a. A ∩ B ⊆ (A ∪ B) ∩ (A ∪ B)

b. A ∩ B ⊆ (A ∪ B) ∩ (A ∪ B)
Question 2
Suppose that f is a function from X to Y × Z. Let A and B be subsets of Y and C be a subset of Z.
Prove or disprove that
f−1((A ∩ B) × C) = f−1(A × C) ∩ f−1(B × C)
Note that f−1(A × C) is the inverse image of the set A × C. In order to prove the equation, you will show that each side is a subset of the other side. In order to disprove, you will give a counter example.
Question 3
Determine whether each of the following functions from R to R is one-to-one and onto.
a. f(x) = ln(x2 + 5)
b. f(x) = eex7
1
Question 4
a. Let A and B are two countable sets. Determine whether that A × B is countable.
b. If A is uncountable and A ⊆ B, is B uncountable ? Explain.
c. If B is countable and A ⊆ B, is A countable ? Explain.
Question 5
Suppose that f1 and f2 be increasing functions and f1(x) is O(f2(x)). Prove or disprove that a. ln|f1(x)| is O(ln|f2(x)|)
b. 3f1(x) is O(3f2(x))
Question 6
Prove or disprove the following questions.
a) x,y ∈ Z+
(3x − 1)mod(3y − 1) = 3(x mod y) − 1
b) Use the Euclidean algorithm to find gcd(123,277)
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given. Other than that, you cannot change the provided template answer file. If a latex structure you want to use cannot be compiled with the included packages in the template file, that means you should not use it.
2. Do not write any other stuff, e.g. question definitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.
3. Late Submission: Not allowed
5. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.
2 Submission
Submission will be done via COW. Download the given template file, ”the2.tex”, when you finish your exam upload the .tex file with the same name to COW.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex the2.tex
2