C960 Discrete Mathematics II: Algorithms, Probability & Computation Short Keywords

C960 DISCRETE MATH II QUESTIONS AND
ANSWERS

Pre-Assessment: Algorithms - Algorithm Structures:
Question 1:
Consider the following pseudocode that merges two lists of numbers into one:
Merge0(List1, List2)
Set OUT list to empty
While List1 is not empty OR List2 is not empty
If one list is empty and the other is not,
Remove the first number from the non-empty list and add it to OUTlist
If both lists are non-empty,
Remove the first number from List1 and add it to OUTlist
Remove the first number from List2 and add it to OUTlist
Return OUTlist

If List A is [1, 3, 5] and List B is [2, 4, 6] then what is the result of Merge0 (ListA,
Merge0 (List 2B, List A))? - ANSWER-[ 1, 2, 3, 1, 5, 4, 3, 6, 5 ]
Step 1:
To solve this, we need to understand how the Merge0 function works. It merges
two lists by taking the first element of each list and adding it to the output list in
ascending order. If one list is empty and the other is not, it removes the first
element from the non-empty list and adds it to the output list.
Using the given example, we have:
List A = [1, 3, 5]
List B = [2, 4, 6]
Now, let's analyze the innermost function Merge0(List B, List A):
1. OUTlist = empty
2. OUTlist = [2]
3. OUTlist = [2, 1]
4. OUTlist = [2, 1, 4]
5. OUTlist = [2, 1, 4, 3]
6. OUTlist = [2, 1, 4, 3, 6]
7. OUTlist = [2, 1, 4, 3, 6, 5]
8. List A is now empty, so we return OUTlist = [2, 1, 4, 3, 6, 5]
Step 2:

,Now, let's use the result of Merge0(List B, Lis tA) as the second argument for the
outer Merge0 function. So we have:
List1 = List A = [1, 3, 5]
List2 = Merge0(List B, List A) = [2, 1, 4, 3, 6, 5]
Using the Merge0 function with these lists, we have:
1. OUTlist = empty
2. OUTlist = [1]
3. OUTlist = [1, 2]
4. OUTlist = [1, 2, 3]
5. OUTlist = [1, 2, 3, 1]
6. OUTlist = [1, 2, 3, 1, 5]
7. OUTlist = [1, 2, 3, 1, 5, 4]
8. OUTlist = [1, 2, 3, 1, 5, 4, 3]
9. OUTlist = [1, 2, 3, 1, 5, 4, 3, 6]
10. OUTlist = [1, 2, 3, 1, 5, 4, 3, 6, 5]
11. return OUTlist = [1, 2, 3, 1, 5, 4, 3, 6, 5]
Therefore, the result of Merge0(List A, Merge0(List B, List A)) is [1, 2, 3, 1, 5, 4,
3, 6, 5].

Pre-Assessment: Algorithms - Algorithm Structures:
Question 2:

Given this pseudocode:
S = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
x=2
While(x<11):
For i in S:
If 0 ≡ i mod x and i ≠ x:
delete i from S
end-If
end-For
x=x+1
end-While

What is S at the end of this code? - ANSWER-{2, 3, 5, 7, 11, 13, 17, 19}

This code is nothing but finding the prime numbers from the given set.

, Start from x = 2
1) When x = 2, we have to delete that elements from S which satisfy 0 == i mod 2
and i ≠ 2 i.e multiples of 2 except 2. So we remove {4, 6, 8, 10, 12, 14, 16, 18, 20}
x = x+1
2) When x = 3, we have to delete that elements from S which satisfy 0 == i mod 3
and i ≠ 3 i.e multiples of 3 except 3. So we remove {6, 9, 12, 15, 18}
x = x+1
3) When x = 4, we have to delete that elements from S which satisfy 0 == i mod 4
and i ≠ 4 i.e multiples of 4 except 4. So we remove {8, 12, 16, 20}
x = x+1
4) When x = 5, we have to delete that elements from S which satisfy 0 == i mod 5
and i ≠ 5 i.e multiples of 5 except 5. So we remove {10, 15, 20}
x = x+1
5) When x = 6, we have to delete that elements from S which satisfy 0 == i mod 6
and i ≠ 6 i.e multiples of 6 except 6. So we remove {12, 18}
x = x+1
6) When x = 7, we have to delete that elements from S which satisfy 0 == i mod 7
and i ≠ 7 i.e multiples of 7 except 7. So we remove {14}
x = x+1
7) When x = 8, we have to delete that elements from S which satisfy 0 == i mod 8
and i ≠ 8 i.e multiples of 8 except 8. So we remove {16}
x = x+1
8) When x = 9, we have to delete that elements from S which satisfy 0 == i mod 9
and i ≠ 9 i.e multiples of 9 except 9. So we remove {18}
x = x+1
9) When x = 10, we have to delete that elements from S which satisfy 0 == i mod
10 and i ≠ 10 i.e multiples of 10 except 10. So we remove {20}
x = x+1
Now x = 11, we break the while loop and the program is terminated.
So, after deleting the above elements, we are left with
{2, 3, 5, 7, 11, 13, 17, 19}

Pre-Assessment: Algorithms - Algorithm Structures:
Question 3:

Given the pseudocode fragment:
x := 2