Faculty of Information and Communication Technology
FORMATIVE ASSESSMENT 2
MODULE NAME:
Discrete Structures / History of Computing and Info Models
MODULE CODE: (please tick)
I declare that I am familiar
DCT115D→ DCTF15D→ HSP115D→
with, and will abide to the
Duration: 2 hours Examiner:
Examination rules of Tshwane
University of Technology Date: October 2022 Ms. L Cronjé
Total Marks: 50
Full Marks: 50
Moderator:
Total pages: 7 pages Ms. E Rynners
_____________________ 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. No pencil work!
• Round to 2 decimal places, where applicable
• See Appendix for formulas
Question 1 Algorithms and trace tables [20]
1.1 Use the table provided to trace the values of the variables in the following pseudo code:
p := 1
q := -1
while (q<p)
if q < = 0
then do p := p*2
q := q+1 end do
else q := q*2
end while
(5)
1.2 Rewrite and fill in the missing parts of the given linear search algorithm
procedure linear search(x: integer, a1, a2, . . . , an: distinct integers)
i := 1
________ (i ≤ n and _______ )
i := i+1
____ i ≤ n then ___________ := i
______ location := 0
return location{location is the subscript of the term that equals x, or is 0 if x is not found}
(5)
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 2
1.3 The binary search algorithm is given:
1.3.1 True/False: The list must be sorted in decreasing order? (1)
1.3.2 Refer to the following data set: 2 3 8 9 12 15 20 25. Show the midpoint calculations
and resulting ⅈ and 𝑗 values as the algorithm searches through the list for the value 15. Start
by writing down ⅈ, 𝑗 and 𝑥. Also indicate when the while loop will terminate and the resulting
value of location. (5)
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 3
1.4 Given the bubble sort algorithm and list of values: 33, 100, 45, 87, 20; 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 2 Divisibility, modular arithmetic, and cryptography [30]
2.1 What is 59𝑑ⅈ𝑣10? (1)
2.2 Find 3015 mod 530 (5)
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 4
2.3 Find the prime factors of 2100 (show steps) (4)
2.4 Make use of prime factors to find the greatest common divisor (GCD) of 280 and 616 (4)
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 5
2.5 Say whether the following is true or false and motivate your answer.
2.5.1 14 ≡ 77(mod 7) (2)
2.5.2 11 ≡ 23(mod 3) (2)
2.5.3 8 ≡ −12(mod 4) (2)
2.5.4 −12 ≡ 42(mod 5) (2)
2.6 Assume that a modified Caesar cipher is given by 𝐶 = (𝑀 − 3) mod 26
2.6.1 What will the decrypting formula be? (1)
2.6.2 True or false? 𝐶 = (𝑀 + 23) mod 26 will give the same result. Motivate. (2)
2.6.3 Decrypt the following ciphertext: XIJLPQ BKA LC QEB VBXO (5)
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 6
Appendix
Let 𝑎, 𝑏, and 𝑛 be integers with 𝑛 > 1. Then
𝑎𝑏 ≡ [(𝑎 𝑚𝑜𝑑 𝑛)(𝑏 𝑚𝑜𝑑 𝑛)](𝑚𝑜𝑑 𝑛)
Or, equivalently,
𝑎𝑏 𝑚𝑜𝑑 𝑛 = [(𝑎 𝑚𝑜𝑑 𝑛)(𝑏 𝑚𝑜𝑑 𝑛)] 𝑚𝑜𝑑 𝑛
In particular, if 𝑚 is a positive integer, then
𝑎𝑚 ≡ [(𝑎 𝑚𝑜𝑑 𝑛)𝑚 ](𝑚𝑜𝑑 𝑛)
Or, equivalently,
𝑎𝑚 𝑚𝑜𝑑 𝑛 = [(𝑎 𝑚𝑜𝑑 𝑛)𝑛 ] 𝑚𝑜𝑑 𝑛
DCT115D/DCTF15D/HSP115D FA2 2022 Semester 2 – October 2022 7