Faculty of Information and Communication Technology
SUMMATIVE ASSESSMENT 2
MODULE NAME: Discrete Structures/History of Computing
and Info Models
MODULE CODE: DCT115D/HSP115D
I declare that I am familiar
with, and will abide to the Examiner:
Examination rules of Tshwane Duration: 2 hours Ms. L Cronjé
University of Technology
Date: March 2021
Total Marks: 100
Total pages: 13 pages
Moderator:
Mr. CK Lepota
_____________________
Student number
Signature
Surname: Initials: Mark:
Instructions:
• Answer ALL questions, show all steps.
• Use the spaces provided to answer each question.
• Write legibly in blue or black PEN.
• Round to 2 decimal places, where applicable
• See Appendix for formulas and tables for logical equivalences and rules of inference
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 1
Question 1 Logic and proofs [30]
a) Write down the logical expression of the following circuit: (6)
b) Using propositional equivalences, prove that: (𝑛 ∨ 𝑜) ∧ (𝑚 ∧ 𝑡) ∧ (𝑛 ∨ ¬𝑜) ≡ 𝑚 ∧ 𝑛
(Show one step per line with a reason for the step) (6)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 2
c) A set of premises and a conclusion is given. Use the rules of inference to deduce the conclusion
from the premises, giving a reason for each step. (8)
i) 𝑃 → 𝑄
ii) 𝑅 → 𝑆
iii) 𝑃
iv) ¬𝑆 ∧ 𝑇
v) 𝑄 ∧ ¬𝑅 → 𝑈
vi) ∴ 𝑈
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 3
d) Prove, using Mathematical induction, for any 𝑛 ≥ 1, that
2 + 4 + 8 + ⋯ + 2𝑛 = 2𝑛+1 − 2
(10)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 4
Question 2 Sets, functions and matrices [30]
a) Calculate the following
7
i) ( ) (2)
3
(𝑘+3)!
ii) (3)
(𝑘+1)!
b) Calculate how many possible passwords can be created using two letters of the alphabet, only
uppercase (no vowels allowed for the 1st letter), together with two digits and one of the following
four special characters: $, ~, &, % (4)
3
√𝑥
c) If 𝑓(𝑥) = , find the inverse 𝑓 −1 (𝑦) (4)
2
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 5
d) If 𝑓(𝑥) = 𝑥 + 6 and 𝑔(𝑥) = 𝑥 2 − 2 find 𝑓 ∘ 𝑔 and 𝑔 ∘ 𝑓 (4)
4
e) Write the following in expanded form and calculate: ∑𝑘=1(2𝑘+1 ) (4)
f) Write out the binomial expansion of: (𝑎 − 2𝑏)4 (4)
1 0 −1
13 2 5 6 0 −3
g) Given the following matrices: 𝐴 = [ ],𝐵 = [ ] 𝑎𝑛𝑑 𝐶 = [3 2 0 ],
5 1 1 −2 2 1
1 2 1
find:
i) 2𝐴 − 𝐵 (2)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 6
ii) 𝐵𝐶 (3)
Question 3 Algorithms and trace tables [20]
a) Use the table provided to trace the values of the variables in the following pseudo code:
a:=25
b:=10
for j:=1 to 4
if b<(a-10)
then b:=b+3
else a:=a-2
next j
(5)
b) Find and fix the mistakes on the following linear search algorithm
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 7
procedure linear search(x: integer, a1, a2, . . . , an: distinct integers)
i := 1
while (i ≥ n and x = ai )
i := i + i
if i ≥ n then location := i
else location := 10
return location{location is the subscript of the term that equals x, or is 0 if x is not found}
(5)
c) Explain the binary search algorithm in your own words.
i) What is the condition for the algorithm to work? (1)
ii) Refer to the following data set to help with your explanation: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
21, 23, 25, 27, 29, 31 (assume you need to find the 11) (5)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 8
d) Given the bubble sort algorithm and list of values: 12, 13, 24, 9, 15; what will be the state of the
list after each pass (i.e., for i=1 to 4)?
procedure bubblesort(a1, . . . , an : real numbers with n ≥ 2)
for i := 1 to n − 1
for j := 1 to n − i
if aj > aj+1 then interchange aj and aj+1
{a1, . . . , an is in increasing order}
(4)
i=1
i=2
i=3
i=4
Question 4 Divisibility, modular arithmetic, and cryptography [20]
a) Find 2048 mod 625 (4)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 9
b) Find the prime factors of 2520 (show steps) (4)
c) Make use of prime factors to find the greatest common divisor (GCD) of 336 and 80 (4)
d) Say whether the following is true or false
i) 5 ≡ 8(mod 2) (1)
ii) 21 ≡ 33(mod 3) (1)
iii) −7 ≡ 10(mod 3) (1)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 10
iv) 203 ≡ 302(mod 15) (1)
e) Assume that a modified Caesar cipher is given by 𝐶 = (𝑀 + 6) mod 26
i) What will the decrypting formula be? (1)
ii) Decrypt the following ciphertext: ZNK JUM XATY GCGE (3)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 11
Appendix
Figure 0-1:Logical Equivalences. Image credit: Epp (2018)
Figure 0-2: Rules of Inference. Image credit: Epp (2018)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 12
Figure 0-3: Modular arithmetic. Image credit: Epp (2018)
𝑛
𝑛
(𝑎 + 𝑏)𝑛 = ∑ ( ) 𝑎𝑛−𝑗 𝑏 𝑗
𝑗
𝑗=0
Reference
EPP, S. 2018. Discrete mathematics with applications. 5th ed. Nelson Education.
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 13