B.Sc. Computer Science IV (Fourth) Semester Examination 2015-16
Course Code: CSC403 Paper ID: 0834227
Algorithm Design
Time: 3 Hours Max. Marks: 70 Max Marks: 75
Note: Attempt six questions in all. Q. No. 1 is compulsory.
1. Answer any five of the following (limit your answer in 50 words). (4x5=20)
a) Prove that running Time T(n) =n3 + 20n + 1 is O (n3).
b) Solve following Recurrence Equation
T(n) = 16T (n/4) + n3 using master’s method.
c) What are the operations that can be performed on disjoint set data structures?
d) What do you understand by Branch and Bound technique? Give example.
e) Consider the following undirected graph.
Simulates the BFS algorithms on it, if starting node is N.
f) What is string matching problem? Explain with suitable example.
g) Suppose that a node x is inserted into a red-black tree with RB-insert and then immediately deleted with RB-delete. Is the resulting red-black tree the same as the initial red-black tree? Justify your answer.
h) What do you understand by Traveling Salesman Problem?
2. Explain merge sort algorithm with example and find the average case complexity of the algorithm. (10)
3. Show the result of inserting the following items in an empty B-tree of order 5
35, 36, 38, 86, 15, 55, 40, 08, 30, 16, 39, 17, 23, 53, 37, 43, 75, 48. (10)
4. Compute the optimal sequence for the multiplication operation of A5x4 B4x6 C6x2 D2x7 matrices using dynamic programming. (10)
5. Define the minimum cost spanning tree. Use Prim’s algorithm to find out the minimum cost spanning tree of the following weighted graph. (10)
6. Define binary heap. What is max heap property? Construct a binary max heap for the following data items: 4 6 8 2 5 7 1 3 9. (10)
7. Using Dijkstra’s shortest path algorithm, find out a least cost path to all other nodes for A, C and F for the following graph. . (10)
8. Define NP, NP-hard and NP-complete class of problems. Give example of each. (10)