Final (AY23/24)

Problems

Question paper without answers:

113KB

final-2324-s1.pdf

PDF

Open

Question without Answers

Question paper with answers:

149KB

final-2324-s1-with-comments.pdf

PDF

Open

Question with Answers

11. Sorting

Insertion sort is fast when it comes to sorting an almost sorted list.

Here is the table summarise the best-case, worst-case time complexity for different sorting algorithms:

Sorting algorithm	Sorted array (best case)	Inversely sorted array (worst case)	General array (average case)
Bubble Sort	0	$O(n^2)$	$O(n^2)$
Insertion Sort	0	$O(n^2)$	$O(n^2)$
Selection Sort	$O(n)$	$O(n)$	$O(n)$

12. Sorting

Notice that in this question, we are talking about the number of swaps, not the running time. So, for the selection sort we are always making $n$ times of swap.

Below is the table summarises the number of swap needed for different sorting algorithms:

Sorting algorithm	Sorted array (best case)	Inversely array (worst case)	General array (average case)
Bubble Sort	0	$O(n^2)$	$O(n^2)$
Insertion Sort	0	$O(n^2)$	$O(n^2)$
Selection Sort	$O(n)$	$O(n)$	$O(n)$

16. Recursion

This kind of sequence (each binary number is one-bit different from its previous) is called grey code! Amazing right!

In this problem, it utilises a hidden information: that is the string is intialized to be all 0! So, it is safe for the first line of our recursion to be just generate(str, n, k + 1) since once it reaches the end, it will print all 0.

Then our idea may be a bit clearer, we modify our current bit str[k] to be different from what we print out previously, and then print it out by calling generate(str, n, k + 1) again.

generate(str, n, k + 1);
str[k] = (str[k] == '0') ? '1' : '0';
generate(str, n, k + 1);

To make our mind clearer, Line 1 is to generate the "previous" binary string, then Line 2 modifies the "next" binary string to be exactly one bit different from the previous and then print it out calling the substring recursively.