[SOLVED] Cs215: discrete math (h) written assignment # 2

Q.1 Suppose that A, B and C are three finite sets. For each of the following,
determine whether or not it is true. Explain your answers.
(a) (A → B = A) → (B ⊆ A)
(b) (A ∩ B ∩ C) ⊆ (A ∪ B)
(c) (A → B) ∩ (B → A) = B
Q.2 Prove or disprove the following.
(1) For any three sets A, B, C, C → (A ∩ B)=(C → A) ∩ (C → B).
(2) For any two sets A, B, P(A) ∩ P(B) = P(A ∩ B), where P(A) denotes
the power set of the set A.
(3) For any two sets A, B, P(A) ∪ P(B) = P(A ∪ B), where P(A) denotes
the power set of the set A.
(4) For a function f : X → Y , f(A ∩ B) = f(A) ∩ f(B), for any two sets
A, B ⊆ X.
Q.3 The symmetric difference of A and B, denoted by A ⊕ B, is the set
containing those elements in either A or B, but not in both A and B.
(a) Determine whether the symmetric difference is associative; that is, if
A, B and C are sets, does it follow that A ⊕ (B ⊕ C)=(A ⊕ B) ⊕ C?
(b) Suppose that A, B and C are sets such that A ⊕ C = B ⊕ C. Must it
be the case that A = B?
Q.4 For each set defined below, determine whether the set is countable or
uncountable. Explain your answers. Recall that N is the set of natural
numbers and R denotes the set of real numbers.
1
(a) The set of all subsets of students in CS201
(b) {(a, b)|a, b ∈ N}
(c) {(a, b)|a ∈ N, b ∈ R}
Q.5 Give an example of two uncountable sets A and B such that the difference
A → B is
(a) finite,
(b) countably infinite,
(c) uncountable.
Q.6 Prove that P(A) ⊆ P(B) if and only if A ⊆ B.
Q.7 For each set A, the identity function 1A : A → A is defined by 1A(x) = x
for all x in A. Let f : A → B and g : B → A be the functions such that
g ◦ f = 1A. Show that f is one-to-one and g is onto.
Q.8 Suppose that two functions g : A → B and f : B → C and f ◦ g denotes
the composition function.
(a) If f ◦g is one-to-one and g is one-to-one, must f be one-to-one? Explain
your answer.
(b) If f ◦g is one-to-one and f is one-to-one, must g be one-to-one? Explain
your answer.
(c) If f ◦ g is one-to-one, must g be one-to-one? Explain your answer.
(d) If f ◦ g is onto, must f be onto? Explain your answer.
(e) If f ◦ g is onto, must g be onto? Explain your answer.
Q.9 Derive the formula for !n
k=1 k2.
Q.10 Derive the formula for !n
k=1 k3.
Q.11 Find a formula for !m
k=0)
√
k+, when m is a positive integer.
2
Q.12 Show that if A, B, C and D are sets with |A| = |B| and |C| = |D|, then
|A × C| = |B × D|.
Q.13 Show that if A and B are sets with the same cardinality, then |A| ≤ |B|
and |B| ≤ |A|.
Q.14 Suppose that A is a countable set. Show that the set B is also countable
if there is an onto function from A to B.
Q.15 Show that the set Z+ ×Z+ is countable by showing that the polynomial
function f : Z+ × Z+ → Z+ with f(m, n)=(m + n → 2)(m + n → 1)/2 + m
is one-to-one and onto.
Q.16 By the Schr¨oder-Bernstein theorem, prove that (0, 1) and [0, 1] have the
same cardinality.
Q.17 Suppose that f(x), g(x) and h(x) are functions such that f(x) is Θ(g(x))
and g(x) is Θ(h(x)). Show that f(x) is Θ(h(x)).
Q.18 If f1(x) and f1(x) are functions from the set of positive integers to
the set of positive real numbers and f1(x) and f2(x) are both Θ(g(x)), is
(f1 → f2)(x) also Θ(g(x))? Either prove that it is or give a counter example.
Q.19 Show that if f(x) = anxn+an−1xn−1+···+a1x+a0, where a0, a1,…,an−1,
and an are real numbers and an .= 0, then f(x) is Θ(xn).
Q.20 Prove that for any a > 1, Θ(loga n) = Θ(log2 n).
Q.21 The conventional algorithm for evaluating a polynomial anxn+an−1xn−1+
··· a1x+a0 at x = c can be expressed in pseudocode by where the final value
Algorithm 1 polynomial (c, a0, a1,…,an: real numbers)
power := 1
y := a0
for i := 1 to n do
power := power ∗ c
y := y + ai ∗ power
end for
return y {y = ancn + an−1cn−1 + ··· + a1c + a0}
of y is the value of the polynomial at x = c. Exactly how many multiplica3
tions and additions are used to evaluate a polynomial of degree n at x = c?
(Do not count additions used to increment the loop variable).
Q.22 There is a more efficient algorithm (in terms of the number of multiplications and additions used) for evaluating polynomials than the conventional algorithm described in the previous exercise. It is called Horner’s
method. This pseudocode shows how to use this method to find the value
of anxn + an−1xn−1 + ··· + a1x + a0 at x = c.
Algorithm 2 Horner (c, a0, a1,…,an: real numbers)
y := an
for i := 1 to n do
y := y ∗ c + an−i
end for
return y {y = ancn + an−1cn−1 + ··· + a1c + a0}
Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at x = c? (Do not count additions
used to increment the loop variable.)
Q.23
(1) Show that (log n)log log n = O(log(nn)), where the base of the logarithm
is 2.
(2) Order the following function by asymptotic growth rates. That is, list
them as f1(n), f2(n),…,f9(n), such that fi(n) = O(fi+1(n)) for all i.
You don’t have to explain your answer.
n2
, log n, n log n, nlog n, (log n)
n, (log n)
log n, (log log n)
log n, (log n)
log log n, 3n/2
.
Q.24 Aliens from another world come to the Earth and tell us that the 3SAT
problem is solvable in O(n8) time. Which of the following statements follow
as a consequence?
A. All NP-Complete problems are solvable in polynomial time.
B. All NP-Complete problems are solvable in O(n8) time.
C. All problems in NP, even those that are not NP-Complete, are solvable in
polynomial time.
4
D. No NP-Complete problem can be solved faster than in O(n8) in the worst
case.
E. P = NP.
5