Question $4$

A software developer needs to solve the following problem: given the adjacency

matrix of an undirected weighted graph, find the value of the k$-$th minimum cost

edge. Assume that all edge weights are different, non$-$negative integer numbers,

and not greater than $999.$ The number $1000($one thousand$)$ signals the absence of

and edge.

For example, for the graph represented by the following adjacency matrix M:

The $1^{st}$ minimum $($that is$,k=1)$ is $1,$ the second minimum $(k=2)$ is $3,$ the third

minimum $(k=3)$ is $4,$ and so on$.$

The algorithm to design must take as input arguments the adjacency matrix $($M$),$ its

number of nodes $(N)$ and the value of $k.$ It must return the value of the $k-$th minimum cost edge.

The software developer came up with these two algorithms to solve the problem:

Algorithm $1$:

$1.$ Make a copy of the adjacency matrix. Call the copy M$\_$copy.

$2.$ Create a variable, called min, where the minimum value is recorded

$3.$ Create a variable, called count. Initialise its value to $0$

$4.$ Visit every element of M$\_$copy, from top to bottom, from left to right and

record the minimum value in min

$5.$ Once the minimum value is found, increase the variable count by one unit

$6.$ If the condition count$==$k is true, return the value of min. Otherwise, delete

the minimum value from M$\_$copy $($write number $1000$ in the corresponding

positions$)$ and repeat steps $2-6$

Algorithm $2$:

$$ Create a min$-$heap storing the values of all edges

$$ Perform EXTRACT$\_$MIN k times. The value last extracted is the k$-$th

minimum.

UL$20/0032$ Page $13$ of $13$

$($a$)$ Write the pseudocode of Algorithm $1[8]$

$($b$)$ Write the pseudocode of Algorithm $2.$ Assume you already have

implemented the min$-$heap functions:

$$ INSERT$($heap$,$x$)$:insert number x into the heap. Worst$-$case Theta$($logN$)$

$$ BUILD$\_$HEAP$($A$)$: build a min heap in place. Worst$-$case Theta$($N$)$

$$ EXTRACT$\_$MIN$($heap$)$: return the minimum value stored in the min$-$heap.

Worst$-$case Theta$($logN$)$

That is$,$ you can use these functions with no need to write the pseudocode for

them. $[8]$

$($c$)$ What are the worst$-$case time complexities of A$1$ and A$2?$ Use Theta$-$

notation. Justify your findings. $[8]$

$($d$)$ What algorithm do you recommend for implementation? Justify in terms of

worst$-$case time complexity.