Module: INT102 Assignment1
1. Assessment
The tasks contribute 10% to the overall assessment of INT102
2. Submission
Please complete the assessment tasks using PDF and submit via Learning Mall.
3. Deadline
19-April-2024, Friday 17:30.
Question 1 (15 marks)
Consider the following function:
(a) State the order of magnitude (in Big-O notation) of the function. (5 marks)
(b) Prove that the function f(n) is of the order of magnitude as you stated above. (10 marks)
Question 2 (30 marks)
The time complexity of the merge sort algorithm can be described by the following recurrence for T(n).
(a) Explain the recurrence in terms of Divide and Conquer design technique. [15 marks] (b) Prove that T(n) = O(n log n) (Guess: T(n) < 2 n log n). [15 marks]
Question 3 (15 marks)
Given the Bubble sort algorithm as below:
ALGORITHM BubbleSort(A[0..n − 1])
//Sorts a given array by bubble sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in ascending order
for i=0 ton − 2 do
for j = n- 1 downto i+1 do
if A[j ]
(a) What is the number of swapping operations needed to sort the numbers A[0..5]=[2, 4, 6, 2, 4, 6] in ascending order using the Bubble sort algorithm? (6 marks)
(b) What is the number of key comparisons needed to sort the numbers A[0..5]= [3, 4, 5, 3, 4, 5] in ascending order using the Bubble sort algorithm? (9 marks)
Question 4 (20 marks)
Consider the following graph G.
(a) Give the adjacency matrix and adjacency list of the graph G. (10 marks)
(b) Give the incidence matrix and incidence list of the graph G. (10 marks)
Question 5 (20 marks)
Consider the following graph G. The label of an edge is the cost of the edge.
(a) Using Prim's algorithm, draw a minimum spanning tree (MST) of the graph Also write down the change of the priority queue step by step and the order in which the vertices are selected. Is the MST drawn unique? (i.e., is it the one and only MST for the graph?) [7 marks]
(b) Using Kruskal’s algorithm, draw a minimum spanning tree (MST) of the graph G. Write down the order in which the edges are selected. Is the MST drawn unique? (i.e., is it the one and only MST for the graph?) (7 marks)
(c) Referring to the same graph above, find the shortest paths from the vertex “ to all other vertices in the graph G using Dijkstra’s algorithm. Show the changes of the priority queue step by step and give the order in which edges are selected. (6 marks)
N.B. There maybe more than one solution. You only need to give one of the solutions.