1.Figures for below questions.

.

(a) Suppose we start with the heap and insert 14 into this heap, show what will be the resulting heap.

(b) Suppose we start with the heap and do a single ExtractMax operation, show what will be the resulting heap.

(c) Simulate breadth first search on the graph shown in Fig HW2Q1c. You can assume that the starting vertex is 1, and the neighbors of a vertex are examined in increasing numerical order (i.e. if there is a choice between two or more neighbors, we pick the smaller one). You have to show: both the order in which the vertices are visited and the breadth first search tree.

(d) On the same graph, i.e. the graph in Fig HW2Q1c, simulate depth first search . You can assume that the starting vertex is 1, and the neighbors of a vertex are examined in increasing numerical order (i.e. if there is a choice between two or more neighbors, we pick the smaller one). You have to show: both the order in which the vertices are visited and the depth first search tree.

(e) What is the topological order on the graph shown in Fig HW2Q1e, assuming that the starting vertex is 1, and the neighbors of a vertex are examined in increasing numerical order. Please note that I am asking specifically what will be the topological order produced by this algorithm i.e. it is not enough just to show another topological order.

(f) Trace the execution of Kruskals algorithm on the graph shown in Fig HW2Q1f. Show the connected components each time a new edge is added.

Questions are from algorithm analysis &design course

HW 2 Figures 5 Fig HW2Q1c Fig HW2Q1e 3 3 Fig HW2Qif