Written Assignment # 2 Solution

Q.1 Suppose that A, B and C are three nite 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) ! (jA [ Bj  2jAj)

    (e) (A\B\C)  (A[B)

    (f) (A  B)\(B  A)=B



Q.2 For each set de ned 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) f(a; b)ja; b 2 Ng

    (c) f(a; b)ja 2 N; b 2 Rg


Q.3 Give an example of two uncountable sets A and B such that the inter-section A \ B is
    (a) nite,

    (b) countable in nite,

    (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 de ned by f(x) = j2xj.

        (b) The mapping f from f1; 3g to f2; 4g de ned by f(x) = 2x.

(c) The mapping f from R to R de ned by f(x) = 8    2x.

(d) The mapping f from R to Z de ned by f(x) = bx + 1c.

(e) The mapping f from R+ to R+ de ned by f(x) = x    1.

(f) The mapping f from Z+ to Z+ de ned 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

jA [ B [ Cj =  jAj + jBj + jCj j A \ Bj

j A \ Cj j B \ Cj + jA \ B \ Cj:


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 + 13 c + bx + 23 c.

2




Q.10 Derive the formula for Pnk=1 k2.

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) = anxn+an 1xn 1+ +a1x+a0, where a0; a1; : : : ; an 1, and an are real numbers and an 6= 0, then f(x) is (xn).

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 fcount is the number of 1’s in Sg



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 nd 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 anxn+an  1xn  1+
a1x + a0 at x = c can be expressed in pseudocode by where the  nal 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 fy = ancn + an  1cn  1 +    + a1c + a0g


of y is the value of the polynomial at x = c. Exactly how many multiplica-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.19 There is a more e cient algorithm (in terms of the number of multi-plications and additions used) for evaluating polynomials than the conven-tional algorithm described in the previous exercise. It is called Horner’s method. This pseudocode shows how to use this method to nd the value of anxn + an 1xn 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 fy = ancn + an  1cn  1 +    + a1c + a0g


Exactly how many multiplications and additions are used by this algo-rithm to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.)









4