Q1.

a) Bob loves foreign languages and wishes to plan his course schedule to take the given nine language courses:

LA15, LA16, LA22, LA31, LA32, LA126, LA127, LA141 and LA169.
The course prerequisites are:

LA15: None, LA6: LA15, LA22: None, LA31: LA15, LA32: LA16 & LA31,
LA126: LA22 & LA32, LA127: LA16, LA141: LA22 & LA16, LA169: LA32.

By using the Graphs, find out a sequence of courses which permits Bob to satisfy all the prerequisites.

b) Draw a graph with 6 vertices which has unique ordering of vertices if topologically sorted.

c) Let G be an undirected connected graph. Give a proficient algorithm to find out the second best minimum spanning tree of G.

Q2.

a) prepare Counting Sort algorithm. Describe the operation of counting sort on the given array:

A = {7, 1, 3, 1, 2, 4, 5, 7, 2, 4, 3}

b) describe an algorithm which, given n integers in the range 1 to k, preprocesses its input and then answers any query regarding how many of the n integers fall in the range [a..b] in O(1) time. Avoid the preprocessing time.

c) prepare an algorithm to determine the Kth smallest element from the set of n different numbers without sorting it.