Deign and Analysis of Algorithms - Semester Paper

School of Computer Science, Engineering and Applications

BHARTHIDASAN UNIVERSITY

APRIL 2011 - IVth Semester

DESIGN AND ANALYSIS OF ALGORITHMS

Date fo Exam : 04/05/12

INSTRUCTIONS :

Part - A : Answer all Questions

Part - B : Answer all Questions, either (a) or (b), one only

Part - C : Answer any Three only

PART - A

1. Define Order of notation.

2. What is the space Complexity for the Quick Sort ?

3. How will you analyze efficiency of Recurcive Algorithms ?

4. What is meant by Emphirical Analysis of an Algorithm ?

5. What are the merits and demerits of Merrge sort ?

6. What is the general Procedure od Dynamic Programming ?

7. What is the complexity of Floyd's Algorithm ?

8. Sate is Backtracking always produces optimal solution .

9. What are the additional items required for Branch and Bound compared to Backtracking technique ?

10. Differentiate between Backtracking and Branch and Bound techniques

PART - B

11. (a) Discuss the fundamentals of algorithmic probelm solving Algorithm [OR]

11. (b) Write a note on Asymptotic Notations.

12. (a) Explain the Mathematical Analysis of recurcive algorithm for finding the factorial of the given number [OR]

12. (b)  Explain the Mathematical Analysis of Nnn-Recurcive algorithm for finding the Fibonacci Numbers

13. (a) Write the procedure for Binary Search and Expalin with an example [OR]

13. (b) Explain any one Representation of Graph with Example

14. (a) Fine the minimum Spanning tree using Prim's Algorithm with your own Example [OR]

14. (b) Sort the numbers with Heap Sort : 23,12,54,45,78,17,90,57,89,67

15. (a) Draw a portion of the State space tree and perform backtracking search for n = 4 in the n - Queen Problem. [OR]

15. (b) Write the procedure for the sum of Subset problem

PART - C

16. Discuss algorith design and analysis process

17. Discuss the general plan for the emphirical analysis of the algorithm Efficiency

18. A) Explain the Merge Sort with the Algorithm and Complexities

      B) Sort the numbers using merge sort : 8,3,2,9,7,1,5,4

19. Illustrate Single Source shortest path problem, write and expalin Dijkstra's algorithm with example

20. Solve the instance of the Knapsack Problem by the Branch and Bound algorithm - Knapsack Weight W = 10

Item Weight Value Value /Weight

1       4           $40     10 

2       7           $42     6

3       5           $25     5

4       3           $12     4

TAGS : Sem 4, Semester Paper, Semester Question Paper, April 2012, Deign and Analysis of Algorithms