Question $4$

$4.$a

For a linear array with a circular buffer, what is the complexity in big O notation for adding an item and the complexity in big O notation for removing an item? Explain your answers.

$[4$ marks$]$

$4.$b

You are given two priority queues with $n$ integers each. Describe in words how you would efficiently merge them into one priority queue. What is the time complexity of your method in big O notation?

$[4$ marks$]$

$4.$c

Consider the directed granh $G$ shown below:

Consider the directed granh $G$ shown below:

i$.$ State whether $G$ is non$-$connected, weakly connected, or strongly connected.

Explain your answer.

$[2$ marks$]$

ii$.$ Write down the order in which the nodes are visited during depth$-$first traversal, starting at node $0.$ Include the symbol uarr wherever the traversal is forced to back up to a previous node $($as covered in lecture$).$ You can assume that adjacent nodes are selected in increasing order of their value.

$[4$ marks$]$

iii. How many arcs are there in the complementary graph of $G?$

$[2$ marks$]$

$4.$d

This question is about thn fnll $....$ina $+$ mn

i$.$ What is the sequence of nodes visited by the postorder traversal?

$[2$ marks$]$

ii$.$ How many zeros are there in the adjacency matrix representation of this tree?

$[2$ marks$]$

iii. You are given a pointer to the root node of the above tree. Describe a method to create a new tree where for each node $($in the whole tree$)$ you swap the left and right child nodes.

$[3$ marks$]$

$[$Total $25$ Marks$]$

iv$.$ How many subgraphs of $G$ are there that have exactly two nodes? Explain your

answer.