Declaration of No Repetition of Previous Exam Questions

Herewith, I declare that the exam for the course M131 of this semester has no repeated questions from previous exams. I also declare that all the exam questions cover all the course material and reflect what has been covered in the continuous assessment. Also, I declare that I did not solicit the opinions of other tutors regarding preparation of this exam and have ensured adequate security of the exam.

Name: Mohamed Sayed

Signed by: Mohamed Sayed

Date: 20/10/2012

Faculty Of Computer Studies
M131
Discrete Mathematics
F I N A L E X A M I N A T I O N
Fall / 2012 – 2013
--/01/2013
2 Hours / Time Allowed: / 4 / Number of Exam Pages (including this cover sheet):

FORM A

Keys

Instructions:

Part 1: MULTIPLE CHOICE QUESTIONS

You may solve all questions. Each question is worth 2 marks. Your grade in this part is that of the best 5 questions, giving a total of 10 possible marks.

Q–1: The negation of is

a)

b)

c)

d)

e)  None of the above

Q–2: The quotient and remainder when 77 is divided by 6 is

a)  q = 11, r = 11

b)  q = 12, r = 5

c)  q = 13, r = −1

d)  q = 14, r = −7

e)  None of the above

Q–3: Assume that R is a relation on {1, 2, 3, 4} defined as follows: a R b if and only if a + b is an odd number, then R =

a)  {(1,2), (1,4), (2,3), (3,4)}

b)  {((2,1), (4,1), (3,2), (4,3)}

c)  {(1,2), (3,4)}

d)  {(1,2), (2,1), (1,4), (4,1), (2,3), (3,2), (3,4),(4,3)}

e)  None of the above

Q–4: A minimal element of the Poset ({2, 4, 5, 10, 20, 25}, |) is

a)  4

b)  5

c)  10

d)  20

e)  None of the above

Q–5: The number of rows in the adjacency matrix of the complete graph K6 is

a)  6

b)  7

c)  21

d)  36

e)  None of the above

Q–6: The number of vertices in a full binary tree with 50 internal nodes is

a)  99

b)  101

c)  51

d)  49

e)  None of the above

Part 2: ESSAY QUESTIONS

Each question is worth 10 marks. You should answer only FOUR out of the five questions, giving a total of 40 possible marks. If you answer all five questions, your tutor will only mark the first four in the order presented.

Q–1:

a)  [5×1 Marks] Determine the truth value of each of the following statements:

i.  If 0.5 is an integer, then 1 + 0.5 = 3.

T

ii.  Cats can fly whenever 5 > 2.

F

iii.  , domain is the set of real numbers.

F

iv.  , domain is the set of integers.

F

v.  123 27 (mod 4).

T

b)  [3+2 Marks] Establish whether each of the following propositions is a tautology, contradiction or contingency:

i.  (p®q) ˅ (p® Øq), by using truth table.

p q / p®q / Øq / p® Øq / (p®q) ˅ (p® Øq)
F F / T / T / T / T
F T / T / F / T / T
T F / F / T / T / T
T T / T / F / F / T

Tautology.

ii.  Ø (p® (q®p)), by using law of logic.

Ø (p® (q®p)) ≡ Ø ( Øp ˅ (Øq ˅ p)) ≡ Ø ((Øp ˅ p) ˅ Øq)

≡ Ø (T ˅ Øq) ≡ ØT = F.

Q–2:

a)  [5×1 Marks] Let P(x) be the statement "x is happy" and Q(x) be the statement "x is under 20", where the universe of discourse for x is the set of students. Express each of the following in English:

i.  P(Ali) ˄ Q(Ali).

Ali is happy and under 20

ii.  Q(Ahmed) → P(Ahmed).

If Ahmed is under 20, then he is happy

iii.  .

Some students are unhappy

iv.  .

There is a student who is happy and over 20

v.  .

Not all students are either unhappy or under 20.

b)  [3+2 Marks] If A = {x: x is an integer and 1≤ x ≤11}, B = {x | x is an even integer} and C = {2, 3, 5, 6}.

i.  Find (A Ç B) – C.

(A Ç B) – C = {4, 8, 10}

ii.  How many members does the power set P(C) have? The Cartesian product A×C have?

|P(A)| = 16

|A×C| = 24

## Q–3:

a)  [5×1 Marks] Consider the integers a = 825 and b = 1638.

i.  Find the prime factorizations of a and b.

a = 3×52×11 & b = 2×32×7×13

ii.  Are a and b relatively prime? Explain.

No, as 3 | a and 3 | b

iii.  Find GCD(a, b) and LCM(a, b).

GCD(a, b) = 3

LCM(a, b) = 2×32×52×7×11×13 = 450450

iv.  Convert a to a binary number.

a = (1100111001)2

v.  Convert a to a hexadecimal number.

a = (339)16

b)  [1+2+2 Marks] Let

i.  Calculate B ˄ C.

B ˄ C =

ii.  Calculate B ⊙ A.

B ⊙ A =

iii.  List the elements of the relation R on the set {1, 2, 3} represented by the matrix A.

R = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1)}

## a)  [5×1 Marks] Let R1 = {(x, y): x = y − 1} and R2 = {(x, y): x < y} be relations on the set A = {1, 2, 3, 4}.

i.  List the elements of R1 and R2.

R1 = {(1, 2), (2, 3), (3, 4)}

R2 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

ii.  Find R2○ R1.

R2○ R1 = {(1, 3), (1, 4), (2, 4)}

iii.  Find the matrix representation of R2.

iv.  Find the symmetric closure of R1.

{(1, 2), (2, 3), (3, 4), (2, 1), (3, 2), (4, 3)}

v.  Find the transitive closure of R2.

{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

b)  [5 Marks] Show that the relation on the set of integers

R = {(a, b) | a – b is an even integer}

is an equivalence relation.

Reflexive: a – a = 0; even integer, so (a, a) in R for all a.

Symmetric: If (a, b) in R, then a – b = 2n for some integer n, thus b – a = –2n and hence b – a is an even integer, then (b, a) in R for all a, b.

Transitive: If (a, b) and (b, c) in R, so a – b = 2n and b – c = 2m for some integers n , m. Now a – c = (a – b) + (b – c) = 2(n + m); even integer, hence (a, c) in R for all a, b, c.

## Q–5:

a)  [3+2 Marks] Let be the adjacency matrix of a graph G = (E, V), E = {a, b, c, d}.

i.  Draw G.

ii.  Find the incidence matrix of G.

b)  [3+1+1 Marks] Consider the binary search tree that results when the following integers are inserted in the order given: 50, 90, 40, 45, 80, 60, 65, 30.

i.  Draw the tree.

ii.  Is it a full binary tree? Find its height.

It is not a full binary tree. Its height is 4.

iii.  Show the inorder traversal of that tree.

30, 40, 45, 50, 60, 65, 80, 90