IGNOU MCS-31 - Design and Analysis of Algorithms

Q1: For a problem P, two algorithms A and B have time complexities T1(n) = 5n2 and T2 (n) = 100nlogn respectively. Find the range for n, the size of instance of the given problem P, for which A is more efficient than B. Q2: Solve the following recurrence equations: (i) T(n) = 2T(n/2) + 0(n) (ii) T(n) = T(n - 1) + 0(n) Q3: Write a recursive function in C language to calculate the sum of all digits in a long integer provided as input. Q4: Show stepwise sorting of elements using Heapsort algorithm to the following max heap. Q5: Write a Turing machine to recognize the language of all strings of even length over the alphabet {a, b}. Q6: Define ambiguity in Context-Free Grammar (CFG). Prove that the following grammar is ambiguous. E →>E+E/E*E/a Q7: Use Prim's algorithm to construct a minimum spanning tree for the following graph. (use starting node A) Q8: Discuss the relationship between class P, NP, NP complete and NP Hard problems with suitable example of each class. Q9: Define fractional Knap-Sack problem, and give a greedy algorithm to solve this problem efficiently. Q10: Give an algorithm for topological sort. Obtain a topological ordering for the following graph: