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 StudiesM131
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.
Contradiction.
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)}
Q–4:
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