University of Cape Coast
College of Agriculture & Natural Sciences
School of Physical Sciences
Department of Computer Science & Information Technology
CSC / INF 212-Algorithm Quiz 1- Likely Questions
Index Number ……………………… Date …………………………….
1. Write a swap Algorithm for swapping 3 elements/Values.
Solution
🕊
Algorithm SwapThree = { Value1,Value2,Value3 } :
temp = Value1
❤️
Value1 = Value2
Value2 = Value3
Value3 = temp
Return Value1,Value2,Value3
🙌
𝐨
2. How many comparisons, to check if a swap is required, be performed by the bubble sort
algorithm for 3 elements/Values?
𝐨𝐥
Solution
𝐮𝐥
For n = 3 elements:
𝐚𝐰
First Pass: Compare 1st and 2nd
𝐥𝐌
Compare 2nd and 3rd = 2 comparisons
Second Pass: Compare 1st and 2nd = 1 comparison
𝐮𝐞
Total comparisons = 2 + 1 = 3 comparisons
𝐦
✅ Formula Reference:
𝐒𝐚
For Bubble Sort, the maximum number of comparisons is:
𝑛(𝑛−1)
2
3(3−1) 3 ×2
For n=3: 2
= 2
= 3 comparisons
3. The African Oware game is a computation too, Show the trace for Calculating 52-5
Solution
Representing -5 (in 10's complement, 6 digits)
9 9 9 9 9 9
0 0 0 0 0 5
– – – – – –
(Subtraction placeholder)
🕊
9 9 9 9 9 4
( 9’s Complement )
❤️
⥔ (Implied 1 to be added for 10’s complement)
🙌
Adding 1 to convert to 10’s complement
9 9 9 9 9 4
𝐨
𝐨𝐥
1
𝐮𝐥
+ + + + + +
(Addition placeholder)
𝐚𝐰
9 9 9 9 9 5
(-5 in 10’s complement )
𝐥𝐌
Now, Adding 52 + (-5)
𝐮𝐞
0 0 0 0 5 2
(52)
9 9 9 9 9 5
𝐦
(-5 in 10’s complement )
𝐒𝐚
+ + + + + +
(Addition placeholder)
0 0 0 0 4 7 1
(Result with carry )
⥔(Discarded carry-out)
0 0 0 0 4 7
(Final result after discarding the carry-out )
Therefore , the final result after discarding the carry-out is 47.
4. Assuming we are provided the procedure SWAP(i , j )
🕊
Void Swap(int p, int q) {
❤️
int temp;
temp = Pi
🙌
p=q
𝐨 q = temp;
}
𝐨𝐥
(a) How many comparisons, to check if a SWAP is required, are performed by the Bubble
𝐮𝐥
sort algorithm for an array of three elements.
𝐚𝐰
𝑛(𝑛−1)
Answer: 2
3(3−1) 3 ×2
For n=3: 2
= 2
= 3 comparisons
𝐥𝐌
(b) What is the complexity of the Bubble sort algorithm given N as size of problem?
𝐮𝐞
Answer: Sort Complexity = O(N²)
Even though the best case can be O(n), the general case is O(n²).
𝐦
𝐒𝐚
5. For each group of functions, sort the functions in increasing order of asymptotic (big-O)
complexity:
Group 1
Answer :
Note:
🕊❤️🙌
Group 2
𝐨
𝐨𝐥
𝐮𝐥
𝐚𝐰
𝐥𝐌
Answer:
𝐮𝐞
𝐦
Note:
𝐒𝐚
6. For the following algorithm, give the time complexity (in Big-Oh(0) notation)
Algorithm Algol(A)
Input: An array A storing n ≥ = 1 integers
Output: The sum of the prefix sums in A
s ← A[0]
for 𝑖 ← 1 to n - 1 do
s ← s + A[0]
for j ←1 to i do
s ← s + A[j]
end for
end for
return s
Solution: Outer Loop: runs n-1 times ⇒ O(n)
🕊
Inner Loop: runs 1 + 2 + 3 + ... + (n-1) times ⇒ sum of first (n-1) numbers ⇒
(𝑛−1)𝑛
❤️
2
= O(n²).
The dominant term is O(n²).
🙌
Answer: O(n²).
7. What is number of swapping needed to sort the numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending
order, using bubble sort is. Show Full trace
𝐨
Answer : Initial List: 8, 22, 7, 9, 31, 19, 5, 13
𝐨𝐥
𝐮𝐥
Pass 1: 8 22 7 9 31 19 5 13
𝐚𝐰
8 7 22 9 31 19 5 13 -> swap
8 7 9 22 31 19 5 13 -> swap
8 7 9 22 31 19 5 13 -> no swap
𝐥𝐌
8 7 9 22 19 31 5 13 -> swap
8 7 9 22 19 5 31 13 -> swap
8 7 9 22 19 5 13 31 -> swap
𝐮𝐞
Total swaps in pass 1 = 5
𝐦
Pass 2: 8 7 9 22 19 5 13 31
𝐒𝐚
7 8 9 22 19 5 13 31 -> swap
7 8 9 22 19 5 13 31 -> no swap
7 8 9 19 22 5 13 31 -> swap
7 8 9 19 5 22 13 31 -> swap
7 8 9 19 5 13 22 31 -> swap
Total swaps in pass 2 = 4
Pass 3: 7 8 9 19 5 13 22 31
7 8 9 19 5 13 22 31 -> no swap
7 8 9 19 5 13 22 31 -> no swap
7 8 9 5 19 13 22 31 -> swap
7 8 9 5 13 19 22 31 -> swap
Total swaps in pass 3 = 2
Pass 4: 7 8 9 5 13 19 22 31
7 8 9 5 13 19 22 31 -> no swap
🕊
7 8 9 5 13 19 22 31 -> no swap
7 8 5 9 13 19 22 31 -> swap
❤️
Total swaps in pass 4 = 1
🙌
Pass 5: 7 8 5 9 13 19 22 31
7 5 8 9 13 19 22 31 -> swap
Total swaps in pass 5 = 1
𝐨
𝐨𝐥
𝐮𝐥
Pass 6: 7 5 8 9 13 19 22 31
5 7 8 9 13 19 22 31 -> swap
𝐚𝐰
Total swaps in pass 6 = 1
𝐥𝐌
Pass 7: 5 7 8 9 13 19 22 31
No swaps.
𝐮𝐞
𝐦
Sorted List: 5, 7, 8, 9, 13, 19, 22, 31
𝐒𝐚
Total Number of Swaps(Pass 1 to 7) = 14
🕊❤️🙌
𝐨
𝐨𝐥
𝐮𝐥
𝐚𝐰
𝐥𝐌
9. (a) (4 Marks) An array of n elements contains all but one of the integers from 1 to n + 1.
𝐮𝐞
(i) Give the best algorithm you can for determining which number is missing if the array is sorted.
𝐦
(ii) Give a reason for your choice.
𝐒𝐚
Answer:
Since the array is sorted, the best algorithm is Binary Search.
I will check the middle value and compare it with the expected value at that position.
● If the value at the middle is the same as its correct position (value = index + 1), I will
move to the right half.
● If not, I will search the left half.
● The missing number will be at position low + 1.
(ii) Reason:
Binary Search because it is faster than linear search.
● It has time complexity O(log n).
● This makes it the most efficient method for sorted arrays.
🕊
(b) (7 Marks)
❤️
Using your algorithm in (a), find the missing number from the array:
1 2 3 _ 5 6 7 8
🙌
Answer:
Given array: 1, 2, 3, 5, 6, 7, 8
Number of elements: n = 7
𝐨
Correct numbers should be from 1 to 8. So one number is missing.
𝐨𝐥
𝐮𝐥
Step 1:
𝐚𝐰
● low = 0, high = 6
● mid = (0 + 6)/2 = 3 → arr[3] = 5
𝐥𝐌
● Expected value = 4
𝐮𝐞
● Since 5 > 4 ⇒ missing number is on the left ⇒ high = 2
𝐦
𝐒𝐚
Step 2:
● low = 0, high = 2
● mid = (0 + 2)/2 = 1 → arr[1] = 2
● Expected = 2 ⇒ correct ⇒ move right ⇒ low = 2
Step 3:
● low = 2, high = 2
● mid = (2 + 2)/2 = 2 → arr[2] = 3 ⇒ correct ⇒ low = 3
Step 4:
● Now low = 3, high = 2 ⇒ stop.
✅ Missing number = low + 1 = 3 + 1 = 4
🕊❤️
Final Answer:
The missing number is 4.
🙌
𝐨
🙌❤️🕊
Thank you
𝐨𝐥
#[Samuel Mawulolo]
𝐮𝐥
𝐚𝐰
𝐥𝐌
𝐮𝐞
𝐦
𝐒𝐚
