CONFIDENTIAL CS/FEB 2022/MAT415/Set 1

UNIVERSITI TEKNOLOGI MARA

FINAL EXAMINATION

COURSE : DISCRETE MATHEMATICS

COURSE CODE : MAT415
EXAMINATION : FEBRUARY 2022
TIME : 3 HOURS

INSTRUCTIONS TO CANDIDATES

1. This question paper consists of seven (7) questions.

2. Answer ALL questions in your own Answer Booklet. Start each answer on a new page.

3. Answer ALL questions in English.

DO NOT TURN THIS PAGE UNTIL YOU ARE TOLD TO DO SO

This examination paper consists of 6 printed pages

© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL

CONFIDENTIAL 2 CS/FEB 2022/MAT415/Set 1

QUESTION 1

a) A three-digit number is to be formed using the digits 1, 2, 3, 4, 5, 6 and no repetition is

allowed.

i) How many numbers can be formed if the leading digit is 4?

(2 marks)
ii) How many numbers can be formed if the number is more than 250?
(3 marks)
iii) How many odd numbers can be formed between 200 and 400?
(3 marks)

b) Consider a bookshelf contains 28 books in different genre. 14 books are in education, 9

books in business, and 5 books in motivation. A student would like to take 15 books. Find
the number of ways if:

i) there is no restriction.
(2 marks)
ii) the choice must consist of 8 books in education, 5 books in business and 2 books in
motivation genre.
(3 marks)
iii) the choice must consist of at least 9 books in education and exactly 5 books in
motivation genre.
(3 marks)

QUESTION 2

a) Find the conclusion of the following argument by using the rules of inference and/or laws
of logic.

p → q
r p
q
(4 marks)

b) Given the logical expression  ( p  q )   ( r  q ) .

i) draw a circuit that represents the above logical expression.

(3 marks)
ii) use the laws of logic to simplify the expression and state the name of laws used.
(3 marks)
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 3 CS/FEB 2022/MAT415/Set 1

c) Determine the truth values of the following quantifiers by giving example or

counterexample

i) ∀(x ∈ Z)∃(y ∈ R)(x + 4 = y).

(2 marks)
2 2
ii) ∀(x, y ∈ Z)(x + y > 0).
(2 marks)

QUESTION 3

a) Given the universal set μ = {x|x ∈ Z+ , x ≤ 40} with A and B are subsets of μ . Let

A = {x|x is a multiple of 4}. B = {x|x is a perfect square}.

i) Find A ∖ B.
(2 marks)
ii) Show that A − (A ∩ B) = A ∩ B by using Laws of Set Theory and state the name of
laws used.
(3 marks)

b) A group of 60 students participated in a mathematical quiz comprises of three questions.

In the competition, all the student attempted at least one question. There were twenty
students who did not attempt the first question. Two students attempted the first question
only. Meanwhile, fifteen students failed to attempt the second question. Five students
attempted the second and third question only. Ten students attempted the third question
only. Finally, nineteen students answered all three questions.

i) Draw a Venn diagram to represent the information above.

(3 marks)
ii) Find the number of students attempted the first and the second questions only.
(2 marks)
iii) Find the number of students attempted exactly two questions.
(2 marks)
iv) Find the number of students attempted at most one question.
(2 marks)

© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL

CONFIDENTIAL 4 CS/FEB 2022/MAT415/Set 1

QUESTION 4

a) Given a sequence, 1, 6, 16, 31…

Find the

i) recursive formula for the above sequence.

(2 marks)
ii) sixth term of the sequence using the formula in i).
(2 marks)

b) 5
A sequence a1 , a2 , a3 , … is defined by an = 7n − 3. Compute a
k =1
k .

(3 marks)

c) Prove the following proposition by using the Mathematical induction method

n
3n − 1
If n ∈ Z and n ≥ 1, 3
i =1
i −1
=
2
.

(8 marks)

QUESTION 5

a) Given the set A = (1, 2, 3, 4, 5, 6) and R is a relation on A such that aRb if and only if
(3a + b) is an even number.

i) List down the elements of R.

(2 marks)
ii) Determine whether R is reflexive, symmetric, and transitive. Give reason(s) for your
answer.
(3 marks)
iii) Is R an equivalence relation? State the reason(s) for your answer.
(2 marks)
iv) Find the equivalence classes of R.
(2 marks)

© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL

CONFIDENTIAL 5 CS/FEB 2022/MAT415/Set 1

b)  −7.41 − 2 1.42  
Determine the value of  .
(
trunc ( 3.17 )
2
)
(5 marks)

QUESTION 6

a) Draw a binary tree for the following expression and hence state the root of the tree.

xy
− p3 .
5
(3 marks)

b) For the graph G (V, E) as in Figure 1. Find

i) the length of the G (V, E).

(1 mark)
ii) the degree of nodes b and f.
(2 marks)
iii) the hamiltonion cycle (if any). Give reason(s) if the cycle doesn’t exist.
(1 mark)
iv) the eulerian trail (if any). Give reason(s) if the trail doesn’t exist.
(2 marks)
v) the eulerian circuit (if any). Give reason(s) if the circuit doesn’t exist.
(2 marks)
vi) the spanning tree rooted at c.
(1 mark)

© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL

CONFIDENTIAL 6 CS/FEB 2022/MAT415/Set 1

QUESTION 7

a) Given an algebraic expression

c 
(11a + 8b ) −  + 4 3d  .
7

 5 

i) Construct a full binary tree for the above expression.

Hence for questions in ii) – v), determine whether the statement is either TRUE or
FALSE.
(3 marks)
ii) The height of the tree is 5.
(1 mark)
iii) The number of leaves is 11.
(1 mark)
iv) The root of the tree is “-”.
(1 mark)
v) The siblings of “7” is “/”.
(1 mark)
vi) The parent of “c” and “5” is “↑”.
(1 mark)

b) Given the following letters with the respectives frequencies

Letter R E S G B T N O
Frequency 30 7 14 29 65 86 51 100

i) Construct the optimal binary prefix code for each letter.

(6 marks)
ii) Hence, encode the word “STRONG”.
(1 mark)

END OF QUESTION PAPER

© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL