GTU Exam Paper Designer and Analysis of Algorithms June 2012
GUJARAT TECHNOLOGICAL UNIVERSITY
BE- Vth SEMESTER-EXAMINATION – MAY/JUNE – 2012
Subject code: 150703
Subject Name: Design and Analysis of Algorithms
Total Marks: 70
Instructions:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
Q.1 Answer the following.
(i) Compare Iterative and Recursive algorithm to find out Fibonacci series.
Explain why analysis of algorithms is important? Explain: Worst Case, Best Case
(ii) & Average Case Complexity.
(iii) Explain characteristics of Greedy Algorithm.
(iv) What is Principle of Optimality? Explain its use in Dynamic Programming Method.
Q.2 (a) Write a program/algorithm of Selection Sort Method. What is Complexity of the method?
(b) Explain Quick Sort Method with example.
OR
(b) What is Divide and Conquer Technique? Give the use of it for Binary Searching Method.
Q.3 (a) Define Minimal Spanning Tree(MST). Explain Krushkal’s Algorithm to find MST with example.
(b) Solve Making Change problem using Dynamic Programming. (denominations: d1=1,d2=4,d3=6). Give your answer for making change of Rs. 8.
OR
Q.3 (a) Explain Dijkstra’s algorithm to find minimum distance of all nodes from a given node. (Greedy algorithm)
(b) Solve the following Knapsack Problem using Dynamic Method. Write the equation for solving above problem.
n = 5, W = 100
| Object | 1 |
2 |
3 |
4 |
5 |
| Weight (w) 10 | 20 |
30 |
40 |
50 |
|
| Value (v) | 20 | 30 |
66 |
40 |
60 |
Q.4 (a) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- Queens Problem using Backtracking Method.
(b) Explain Breadth First Traversal Method for Graph with algorithm.
OR
Q.4 (a) Explain Chained Matrix Multiplication with example.
(b) Define: Acyclic Directed Graph, Articulation Point, Dense Graph, Sparse Graph.
(c) Explain Min Max Principle.
Q.5 (a) Explain in Breif:
P Problem, NP Problem, Heap Tree, Travelling Salesman Problem (b) Explain finite automata for string matching.
OR
Q.5 (a) Explain Rabin- carp method for string matching and also give the algorithm.
(b) What is Recursion? Give the implementation of Tower of Hanoi problem using Recursion.
(c) Define :Big Oh, Big Omega and Big Theta Notation.