CENG 223 Discrete Computational Structures Take Home Exam 2 solution

$30.00

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (1 vote)

Question 1 (20 pts)
For each of the following functions, show whether they are a) surjective or not b) injective or not.
• f1 : R → R, f(x) = x
2
• f2 : R¯ + → R, f(x) = x
2
• f3 : R → R¯ +, f(x) = x
2
• f4 : R¯ + → R¯ +, f(x) = x
2
Note: R¯ + denotes the set of nonnegative real numbers.

Question 2 (20 pts)
A function f : A ⊂ R
n → R
m is said to be continuous at x0 ∈ A if
∀ ε ∈ R
+ ∃ δ ∈ R
+ ∀ x ∈ A (∥x − x0∥ < δ → ∥f(x) − f(x0)∥ < ε)
where ∥x∥ represents the Euclidean norm, i.e. for x = (x1, x2, . . . , xn) ∈ R
n
, the norm is given as
∥x∥ =
qPn
i=1 x
2
i
. If f is continuous at every x ∈ A, f is continuous. Use this definition to
a) show that every function f : A ⊂ Z → R is continuous.
b) show that a necessary and sufficient condition for a function f : R → Z to be continuous is that f is
a constant function.

Question 3 (20 pts)
a) Show that a finite Cartesian product of countable sets, i.e. Xn = A1 × A2 × . . . × An for all n ≥ 2,
is countable.
1
b) Show that an infinite countable product of the set X = {0, 1} with itself is uncountable.
Note: You can use the following without proving them: i) the set of positive integers Z
+, Z and Z × Z
have the same cardinality, ii) a set A is countable if and only if there exists some f : Z → A that is
surjective.

Question 4 (25 pts)
Arrange the following functions so that each function is big-O of the next function. Show your work.
2
n
, n50
, (log n)
2
,

n log n, 5
n
, (n!)2
, n51 + n
49
Note: You can use calculus in this question.

Question 5 (15 pts)
a) Use the Euclidean algorithm to find gcd(94, 134).
b) Goldbach’s conjecture states that every even integer greater than 2 is the sum of two primes. Show
that this statement is equivalent to the statement that every integer greater than 5 is the sum of three
primes.

Question 6 (ungraded)
Let f : A → B be a function, A0 ⊂ A, B0 ⊂ B and f
−1 denote the preimage of B0 under f defined by
f
−1
(B0) = {a | f(a) ∈ B0}
a) Show that A0 ⊆ f
−1
(f(A0)) and that equality holds if f is injective.
b) Show that f(f
−1
(B0)) ⊆ B0 and that equality holds if f is surjective.

Question 7 (ungraded)
a) A real number is said to be algebraic over the rationals if it satisfies some polynomial equation of
positive degree
x
n + an−1x
n−1 + . . . + a1x + a0 = 0
where ai ∈ Q. Assuming that each polynomial has only finitely many roots, show that the set of algebraic
numbers is countable.
b) A real number is said to be transcendental if it is not algebraic. Show that the set of transcendental
numbers are uncountable.
2

Regulations
1. Your submission should be a single vector-based PDF document with the name the2.pdf.
2. Late Submission: Not allowed.
3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be
punished according to the university regulations.
4. Updates & Announces: You must follow the odtuclass for discussions and possible updates. You
can ask your questions in the Student Forum on the course page in odtuclass.
5. Evaluation: Your .pdf file will be checked for plagiarism automatically using “black-box” technique and manually by assistants, so make sure to obey the specifications.

Submission
Submission will be done via odtuclass. For those who prefer to use LATEX to generate the vector-based
PDF file, a template answer file the2.tex is provided in odtuclass. You need to compile the filled template
yourselves and submit the generated .pdf file only.
3