Construct the min-heap

1. (a) Construct the min-heap for the following list of values using the
Insert algorithm. Illustrate, step by step, how the min-heap tree
develops from the list of values.
[6, 3, 4, 20, 10, 1]
(8 marks)
(b) Both depth first search (DFS) and breath first search (BFS) can be
extended to depth first tree (DFT) and breath first tree (BFT) to
construct a spanning tree. Consider the following graph.
(i) Starting at vertex ‘a’, list the vertices and edge that are visited
using DFS and DFT respectively. Sketch the DFT spanning tree.
(6 marks)
(ii) Starting at vertex ‘a’, list the vertices and edge that are visited
using BFS and BFT respectively. Sketch the BFT spanning tree.
(6 marks)
2. Trace the steps of applying the divide and conquer (D&C) max-min
algorithm to find the maximum and minimum element of
[10, 7, 3, 4, 20, 15, 12, 9, 4, 13, 2, 21].
(7 marks)
c
a b
f
d
e k
i h
g
(b) Given a set of points in 2D, with Li = (xi, yi), i=1, … 7, explain how
a convex hull algorithm is used to obtain a convex hull. Illustrate the
steps of constructing a convex hull, using the set of points below.
(13 marks)
3. State the principle of optimality in the Dynamic Programming
technique. Using this optimality criterion, calculate the transitive
closure matrix when Warshall’s algorithm is applied to the following
graph. Show all the intermediate matrices, identifying the vertices
considered in each step.
(12 marks)
(b) (i) The recurrence relation for the time complexity of the divide
and conquer (D&C) matrix multiplication algorithm is given by: