B.E-B.E Computer Engineering OtherANALYSIS OF ALGORITHMS (Karunya University, Coimbatore-2012)

Reg. No. ________                                                                                                                                                   

Karunya University

(Karunya Institute of Technology and Sciences)

(Declared as Deemed to be University under Sec.3 of the UGC Act, 1956)

 

End Semester Examination – November/ December - 2012

 

Subject Title: ANALYSIS OF ALGORITHMS                                                                                Time: 3 hours

Subject Code:            09CS207                                                                                                                Maximum Marks: 100          

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              

Answer ALL questions

PART – A (10 x 1 = 10 MARKS)

 

1.         What is recursion?

2.         Mention any two important problem types.

3.         The time complexity of sequential search in worst case is ________.

4.         What is a full binary tree?

5.         Mention the properties of a heap.

6.         Name the data structure used in DFS.

7.         What is hashing?

8.         What is transform and conquer?

9.         List any two applications of Huffman trees.

10.       Name any two NP complete problems.

 

PART – B (5 x 3 = 15 MARKS)

 

11.       What are the steps involved in the analysis framework?

12.       Define Brute force approach?

13.       What are 2-3 trees? Give an example.

14.       Define Transitive closure.

15.       What is the problem faced while using variable-length encoding and how can it be avoided?

 

PART – C (5 x 15 = 75 MARKS)

 

16.       Explain about the fundamentals of Algorithmic problem solving.

(OR)

17.       Discuss the Asymptotic notations with efficiency classes and examples.

 

18.  Write and explain the Quick sort algorithm.

(OR)

19.  Define Brute force string matching. Explain the algorithm for Brute force string matching.

 

20. Define Topological sort. Explain why Topological sort is not possible in a graph, which contains cycles. Give the algorithm for topological sort.

(OR)

21. Explain with an example how Heap sort is carried out.

 

22.       Write down the Warshall’s algorithm and explain it with an example.

(OR)

23.       Construct a B-tree of order of 5 for the following list of elements:

            1 12 8 2 25  5 14 28 17 7 52 16   48   68   3   26 29 53 5 45.

 

24.       Write and explain Dijkstra’s algorithm with example.

(OR)

25.       Give a detailed account on P, NP-complete and NP-Hard problems.

Earning:  ₹ 5.15/-