Q-1 Sort the following array using Insertion and Selection Sort: 6, 2, 9, 11, 9, 3,7 Q-2 (5 Marks) Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m 11 using open addressing with linear probing, we use the hash function h{k, i) = (k+i) mod m. Q-3 i. List the nodes visited in the order of a {Depth First Search, Breadth First Search} of the (5 Marks) given Tree 10 11 12 ii. Draw the graph of the following 5 X 5 matrix: W=[01100,10011, 00101,01 001,01010], give the in-degree and out-degree of cach node. Q-4 (7.5 Marks) Answer the following questions: i. Consider A, B, C, D, E and F are six different tourism places in Islamabad. Here we are assuming that you are availing Uber facility in order to cover the distance and visit various places. Let's assume that your starting point is C, find the shortest routes to other places of Islamabad using Dijkstra's algorithm. A 4 2 B F 1 1 8 E D ii. Convert the following equation to the infix notation using any methodology of your choice. ABC*D-E / + F + Q-5 (7.5 Marks) Answer the following questions: i. Find MST of following given graph using Prims as well as Kruskals Algorithm. And prove which method is best in terms of space and time. 3 N 1 A 6 2 F ii. Sort the following array in alphabetic order using Heap sort:IC, O, M, P, U, T, E, R]