Summative Assessment 1 Summative Assessment 2 Summative Assessment 3
SUBJECT CODE: DCT115D/HSP115D
Discrete Structures/ History of Computing and Info
SUBJECT NAME:
Models
ASSESSMENT DATE:
(For Office Use Only)
Contact person(s) to collect the scripts
Examiner Moderator
Name L Cronjé CK Lepota
Campus
(If Applicable)
Office Address
Work Tel No.
Mobile No. 083 660 5251
For Office use only:
Applicable Campus (x) No.
ARCADIA
ARTS
EMALAHLENI
GA-RANKUWA
NELSPRUIT
POLOKWANE
PRETORIA
SOSHANGUVE
EXTRAS
TOTAL COPIES
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)
(𝑛⋁𝑜) ∧ (𝑚 ∧ 𝑡) ∧ (𝑛⋁¬𝑜) ≡ (𝑛⋁𝑜) ∧ (𝑚) ∧ (𝑛⋁¬𝑜) Identity law
(𝑛⋁𝑜) ∧ (𝑚) ∧ (𝑛⋁¬𝑜) ≡ 𝑚⋀[(𝑛⋁𝑜)⋀(𝑛⋁¬𝑜)] Associative/commutative law
𝑚⋀(𝑛⋁𝑜)⋀(𝑛⋁¬𝑜) ≡ 𝑚⋀[𝑛⋁(𝑜⋀¬𝑜)] Distributive law
𝑚⋀[𝑛⋁(𝑜⋀¬𝑜)] ≡ 𝑚⋀(𝑛⋁𝑐) Negation law
𝑚⋀(𝑛⋁𝑐) ≡ 𝑚⋀𝑛 Identity law
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 2 of 14
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 MEMORANDUM Page 3 of 14
d) Prove, using Mathematical induction, for any 𝑛 ≥ 1, that
2 + 4 + 8 + ⋯ + 2𝑛 = 2𝑛+1 − 2
(10)
Let 𝑃(𝑘): 2 + 4 + 8 + ⋯ + 2𝑘 = 2𝑘+1 − 2
𝑃(1) is true, because 2 = 21+1 − 2 = 22 − 2 = 4 − 2 = 2
𝑃(𝑘 + 1): 2 + 4 + 8 + ⋯ + 2𝑘+1 = 2(𝑘+1)+1 − 2 = 2𝑘+2 − 2
𝑃(𝑘) + 𝑛𝑒𝑥𝑡 𝑡𝑒𝑟𝑚: 2 + 4 + 8 + ⋯ + 2𝑘 + 2𝑘+1 = 2𝑘+1 − 2 + 2𝑘+1
= 2 ⋅ 2𝑘+1 − 2 = 2(𝑘+1)+1 − 2 = 2𝑘+2 − 2
Since P(k+1)=P(k)+next term, the formula is proven
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 4 of 14
Question 2 Sets, functions and matrices [30]
a) Calculate the following
7
i) ( ) (2)
3
7!
= 3!4! = 35
(𝑘+3)!
ii) (3)
(𝑘+1)!
(𝑘+3)(𝑘+2)(𝑘+1)!
= (𝑘+1)!
= (𝑘 + 3)(𝑘 + 2) OR 𝑘 2 + 5𝑘 + 6
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)
21 ⋅ 26 ⋅ 10 ⋅ 10 ⋅ 4 = 218400
3
√𝑥
c) If 𝑓(𝑥) = , find the inverse 𝑓 −1 (𝑦) (4)
2
3
√𝑥
𝑦= 2
3
√𝑥 = 2𝑦
𝑥 = (2𝑦)3
𝑓 −1 (𝑦) = (2𝑦)3 = 8𝑦 3
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 5 of 14
d) If 𝑓(𝑥) = 𝑥 + 6 and 𝑔(𝑥) = 𝑥 2 − 2 find 𝑓 ∘ 𝑔 and 𝑔 ∘ 𝑓 (4)
𝑓 ∘ 𝑔 = 𝑓(𝑔(𝑥)) = 𝑓(𝑥 2 − 2) = (𝑥 2 − 2) + 6 = 𝑥 2 + 4
𝑔 ∘ 𝑓 = 𝑔(𝑓(𝑥)) = 𝑔(𝑥 + 6) = (𝑥 + 6)2 − 2 = 𝑥 2 + 12𝑥 + 36 − 2 = 𝑥 2 + 12𝑥 + 34
4
e) Write the following in expanded form and calculate: ∑𝑘=1(2𝑘+1 ) (4)
= (21+1 ) + (22+1 ) + (23+1 ) + (24+1 ) = 4 + 8 + 16 + 32 = 60
f) Write out the binomial expansion of: (𝑎 − 2𝑏)4 (4)
4
4
∑ ( ) 𝑎4−𝑗 (−2𝑏)𝑗
𝑗=0 𝑗
4 4 4 4 4
= ( ) 𝑎4 + ( ) 𝑎3 (−2𝑏) + ( ) 𝑎2 (−2𝑏)2 + ( ) 𝑎(−2𝑏)3 + ( ) (−2𝑏)4
0 1 2 3 4
= 𝑎4 + 4𝑎3 (−2𝑏) + 6𝑎2 (−2𝑏)2 + 4𝑎(−2𝑏)3 + (−2𝑏)4
= 𝑎4 − 8𝑎3 𝑏 + 24𝑎2 𝑏 2 − 32𝑎𝑏 3 + 16𝑏 4
½ mark if at least half of the terms are correct
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)
13 2 5 6 0 −3 26 4 10 6 0 −3 20 4 13
= 2[ ]−[ ]=[ ]−[ ]=[ ]
5 1 1 −2 2 1 10 2 2 −2 2 1 12 0 1
½ mark if at least half of the elements are correct
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 6 of 14
ii) 𝐵𝐶 (3)
1 0 −1
6 0 −3 3 −6 −9
=[ ] [3 2 0 ]=[ ]
−2 2 1 5 6 3
1 2 1
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)
a 25 23 21
b 10 13 16
j 1 2 3 4 5
b) Find and fix the mistakes on the following linear search algorithm
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 7 of 14
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)
The list must be sorted
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)
16
Find the middle ⌊ 2 ⌋ = 8 and split the list
1, 3, 5, 7, 9, 11, 13, 15 and 17, 19, 21, 23, 25, 27, 29, 31
Compare the last number in the first list with the number you’re looking for (11)
If the number you’re looking for is greater than the last number in the 1st list, …, otherwise
move the ending marker to the last number in the 1st list
1, 3, 5, 7, 9, 11, 13, 15
8
Find the middle ⌊2⌋ = 4 and split the list
1, 3, 5, 7 𝑎𝑛𝑑 9, 11, 13, 15
Compare the last number in the first list with the number you’re looking for (11)
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 8 of 14
If the number you’re looking for is greater than the last number in the 1st list, move the
beginning marker to the 1st number in the 2nd list
9, 11, 13, 15
4
Find the middle ⌊2⌋ = 2 and split the list
9, 11 𝑎𝑛𝑑 13, 15
Compare the last number in the first list with the number you’re looking for (11)
If the number you’re looking for is greater than the last number in the 1st list, …, otherwise
move the ending marker to the last number in the 1st list
9, 11
2
Find the middle ⌊2⌋ = 1 and split the list
9 𝑎𝑛𝑑 11
Compare the last number in the first list with the number you’re looking for (11)
If the number you’re looking for is greater than the last number in the 1st list, move the
ending marker to the last number in the 1st list
11
We stop when the ending marker is the same as the beginning marker
Check if it is indeed the number we’re looking for and if it is assign the location to the
current position, otherwise location is 0
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 9 of 14
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 12, 13, 9, 15, 24
i=2 12, 9, 13, 15, 24
i=3 9, 12, 13, 15, 24
i=4 9, 12, 13, 15, 24
Question 4 Divisibility, modular arithmetic, and cryptography [20]
a) Find 2048 mod 625 (4)
= (2042 )4 mod 625 = 416164 mod 625 = [(41616 mod 625)4 ] mod 625
= (366)4 𝑚𝑜𝑑 625 = (3662 )2 mod 625 = 1339562 mod 625
= [(133956 mod 625)2 ]𝑚𝑜𝑑625 = 2062 mod 625 = 42436 mod 625 = 561
OR 2042 mod 625 = 41616 mod 625 = 366
2044 mod 625 = (2042 )2 mod 625 = (2042 mod 625)2 mod 625 = 3662 mod 625 = 206
2048 mod 625 = (2044 )2 mod 625 = (2044 mod 625)2 mod 625 = 2062 mod 625 = 561
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 10 of 14
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)
336 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 7 and 80 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 5
𝐺𝐶𝐷 = 2 ⋅ 2 ⋅ 2 ⋅ 2 = 16
d) Say whether the following is true or false
i) 5 ≡ 8(mod 2) (1)
False
ii) 21 ≡ 33(mod 3) (1)
True
iii) −7 ≡ 10(mod 3) (1)
False
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 11 of 14
iv) 203 ≡ 302(mod 15) (1)
False
e) Assume that a modified Caesar cipher is given by 𝐶 = (𝑀 + 6) mod 26
i) What will the decrypting formula be? (1)
𝑀 = (𝐶 − 6)𝑚𝑜𝑑 26
ii) Decrypt the following ciphertext: ZNK JUM XATY GCGE (3)
THE DOG RUNS AWAY
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 12 of 14
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 MEMORANDUM Page 13 of 14
Figure 0-3: Modular arithmetic. Image credit: Epp (2018)
Reference
EPP, S. 2018. Discrete mathematics with applications. 5th ed. Nelson Education.
DCT115D/HSP115D 2020 Semester 2 – March 2021 Paper 2 MEMORANDUM Page 14 of 14