1. Assessment

The tasks contribute 10% to the overall assessment of INT102

2. Submission

Please complete the assessment tasks using Microsoft Word and submit via Learning Mall.

3. Deadline

6-April-2023, Thursday17:30.

Question 1 (15 marks)

Consider the following function:f(n) = 6n + 3n2 + n log n + 3  

(a) State the order of magnitude (in Big-O notation) of the function. (5 marks)

(b) Prove that the functionf(n) is of the order of magnitude as you stated above. (10 marks)

Question 2 (20 marks)

Consider the following recursive function

(1                   if     0  n  3

f (n) =〈

f (n - 1) + f (n - 2) + f (n - 3)

if     n > 4

(a) Write a recursive (top-down) algorithm to compute it. (10 marks)

(b) What is the complexity of your algorithm (in big-O notation)?  (10 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 to n − 2 do

for j = n- 1 downto i+1 do

if A[j ]<A[j- 1 ] swap A[j ] and A[j - 1]

(a) What is the number of swapping operations needed to sort the numbers A[0..5]=[3 ，4 ，5， 3 ，4 ，5] 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 (10 marks)

Consider the following graph G.

a                         b                         c

d                          e                         f

(a) Give the adjacency matrix and adjacency list of the graph G. (5 marks)

(b) Give the incidence matrix and incidence list of the graph G.  (5 marks)

Question 5 (20 marks)

Consider the graph

a                 b                c               d

e                 f                g               h

(a) Starting at the vertex a and resolving ties by the vertex alphabetical order traverse the graph by breadth-first-search (BFS) and construct the corresponding BFS tree.  (10 marks)

(b) Starting at the vertex a and resolving ties by the vertex alphabetical order traverse the graph by depth-first-search (DFS) and construct the corresponding DFS tree.  (10 marks)

Question 6 (20 marks)

Consider the following graph G. The label of an edge is the cost of the edge.

a

b

6

c

d