Discrete Math for Computer Science  Assignment # 2

CS201: Discrete Math for Computer Science
 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 6= ∅) → ((A − B) $ A)
(b) (A − B = A) → (B $ A)
(c) (A − B = ∅) → (A ∩ B = B ∩ A)
(d) (A ⊆ B) → (|A ∪ B| ≥ 2|A|)
(e) (A ∩ B ∩ C) ⊆ (A ∪ B)
(f) (A − B) ∩ (B − A) = B
Q.2 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.
(a) The set of all subsets of students in CS201
(b) {(a, b)|a, b ∈ N}
(c) {(a, b)|a ∈ N, b ∈ R}
Q.3 Give an example of two uncountable sets A and B such that the intersection A ∩ B is
(a) finite,
(b) countable infinite,
(c) uncountable.
1
Q.4 Prove the following using set identities.
(a) (B − A) ∪ (C − A) = (B ∪ C) − A
(b) (A ∩ B) ∩ (B ∩ C) ∩ (A ∩ C) = ∅
Q.5 For each of the following mappings, indicate what type of function they
are (if any). Use the following options to describe them, and explain your
answers.
i. Not a function.
ii. A function which is neither one-to-one nor onto.
iii. A function which is onto but not one-to-one.
iv. A function which is one-to-one but not onto.
v. A function which is both one-to-one and onto.
(a) The mapping f from Z to Z defined by f(x) = |2x|.
(b) The mapping f from {1, 3} to {2, 4} defined by f(x) = 2x.
(c) The mapping f from R to R defined by f(x) = 8 − 2x.
(d) The mapping f from R to Z defined by f(x) = bx + 1c.
(e) The mapping f from R
+ to R
+ defined by f(x) = x − 1.
(f) The mapping f from Z
+ to Z
+ defined by f(x) = x + 1.
Q.6 Prove that P(A) ⊆ P(B) if and only if A ⊆ B.
Q.7 Show that if A, B and C are sets, then
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B|
− |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Q.8 Suppose that f is an invertible function from Y to Z and g is an invertible
function from X to Y . Show that the inverse of the composition f ◦g is given
by (f ◦ g)
−1 = g
−1 ◦ f
−1
.
Q.9 Let x be a real number. Show that b3xc = bxc + bx +
1
3
c + bx +
2
3
c.
2
Q.10 Derive the formula for Pn
k=1 k
2
.
Q.11 Show that a subset of a countable set is also countable.
Q.12 If A is an uncountable set and B is a countable set, must A − B be
uncountable?
Q.13 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.14 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.15 Show that if f(x) = anx
n+an−1x
n−1+· · ·+a1x+a0, where a0, a1, . . . , an−1,
and an are real numbers and an 6= 0, then f(x) is Θ(x
n
).
Q.16 Show that n log n is O(log n!).
Q.17
(a) Show that this algorithm determines the number of 1 bits in the bit
string S:
Algorithm 1 bit count (S: bit string)
count := 1
while S 6= 0 do
count := count + 1
S := S ∧ (S − 1)
end while
return count {count is the number of 1’s in S}
Here S − 1 is the bit string obtained by changing the rightmost 1 bit
of S to a 0 and all the 0 bits to the right of this to 1’s. [Recall that
S ∧ (S − 1) is the bitwise AND of S and S − 1.]
(b) How many bitwise AND operations are needed to find the number of
1 bits in a string S using the algorithm in part a)?
3
Q.18 The conventional algorithm for evaluating a polynomial anx
n+an−1x
n−1+
· · · a1x+a0 at x = c can be expressed in pseudocode by where the final value
Algorithm 2 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 = anc
n + an−1c
n−1 + · · · + a1c + a0}
of y is the value of the polynomial at x = c. Exactly how many multiplications 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.19 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 anx
n + an−1x
n−1 + · · · + a1x + a0 at x = c.
Algorithm 3 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 = anc
n + an−1c
n−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.)
4