Assignment 2 Solution

Description

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)

2. (A B=A)!(B$A)

2. (A B=;)!(A\B=B\A)

2. (A B) ! (jA [ Bj 2jAj)

2. (A\B\C) (A[B)

2. (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.

1. The set of all subsets of students in CS201

2. f(a; b)ja; b 2 Ng

3. 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

1. nite,

2. countable in nite,

3. uncountable.

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.

1. Not a function.

2. A function which is neither one-to-one nor onto.

3. A function which is onto but not one-to-one.

4. A function which is one-to-one but not onto.

5. A function which is both one-to-one and onto.

1. 1. The mapping f from Z to Z de ned by f(x) = j2xj.

1. 2. 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) ¹ = g ¹ f ¹.

Q.9 Let x be a real number. Show that b3xc = bxc + bx + ¹₃ c + bx + ²₃ c.

Q.10 Derive the formula for ^Pn_k=1 k².

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 f₁(x) and f₁(x) are functions from the set of positive integers to the set of positive real numbers and f₁(x) and f₂(x) are both (g(x)), is (f₁ f₂)(x) also (g(x))? Either prove that it is or give a counter example.

Q.15 Show that if f(x) = a_nxⁿ+a_{n 1}x^{n 1}+ +a₁x+a₀, where a₀; a₁; : : : ; a_{n 1}, and a_n are real numbers and a_n 6= 0, then f(x) is (xⁿ).

Q.16 Show that n log n is O(log n!).

Q.17

1. 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.]

2. How many bitwise AND operations are needed to nd the number of 1 bits in a string S using the algorithm in part a)?

Q.18 The conventional algorithm for evaluating a polynomial a_nxⁿ+a_{n 1}x^{n 1}+

a₁x + a₀ at x = c can be expressed in pseudocode by where the nal value

Algorithm 2 polynomial (c; a₀; a₁; : : : ; a_n: real numbers)

power := 1

y := a₀

for i := 1 to n do

power := power c

y := y + a_i power

end for

return y fy = a_ncⁿ + a_{n 1}c^{n 1} + + a₁c + a₀g

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 a_nxⁿ + a_{n 1}x^{n 1} + + a₁x + a₀ at x = c.

Algorithm 3 Horner (c; a₀; a₁; : : : ; a_n: real numbers)

y := a_n

for i := 1 to n do

y := y c + a_{n i}

end for

return y fy = a_ncⁿ + a_{n 1}c^{n 1} + + a₁c + a₀g

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