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 calculate the second best minimum spanning tree of G.
Q2.
a) Write 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) Explain 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) Write an algorithm to determine the Kth smallest element from the set of n different numbers without sorting it.