# GTU Exam papers Design and Analysis of Algorithms

GUJARAT TECHNOLOGICAL UNIVERSITY

B.E. Sem-Vth Examination December 2010

Subject code:15 03

Subject Name: Design & Analysis of Algorithms

Instructions:

1. Attempt all questions.

2. Make suitable assumptions wherever necessary.

3. Figures to the right indicate full marks.

(i)What is an algorithm? Explain various properties of an algorithm.

(ii) Explain: Worst Case, Best Case & Average Case Complexity.

(iii)Define: Directed Acyclic Graph, Principle of Optimality.

(iv) Explain P and NP Problems giving examples.

(b) Arrange following rate of growth in increasing order.

2N, n log n, n2, 1 , n, log n, n!, n3

(i)Compare Dynamic Programming Technique with Greedy Algorithms.

(ii) Give the recursive algorithm to find Fibonacci sequence. Comment on the complexity of the algorithm.

(b) Explain how to apply the divide and conquer strategy for sorting the elements using quick sort with example.

OR

(b) Explain the use of Divide and Conquer Technique for Binary Search Method.

Give the algorithm for Binary Search Method. What is the complexity of Binary Search Method?

Q.3 (a) Give and Explain the Prim’s Algorithm to find out Minimum Spanning Tree with illustration.

(b) Write an algorithm of Selection Sort Method. Give its complexity.

(c) What do you mean by Asymptotic Notations? Explain.

OR

Q.3 (a) Give and Explain the Kruskal’s Algorithm to find out Minimum Spanning Tree with illustration.

(b) Explain why the Heap sort method is called an efficient sorting algorithm.

Sort the following data using Heap sort method.

65, 77, 5, 25, 32, 45, 99, 83, 69, 81

Q.4 (a) Solve the following 0/1 Knapsack Problem using Dynamic Programming. There

are five items whose weights and values are given in following arrays.

Weight w[] = { 1,2,5,6,7 }

Value v[] = { 1,6,18, 22, 28 }

Show your equation and find out the optimal knapsack items for weight capacity of 11 units.

(b) Give the algorithm for Depth First Search of a Graph. Also define “Articulation Point” of the graph and explain how to find it.

OR

Q.4 (a) Explain how to find out Longest Common Subsequence of two strings using

Dynamic Programming method.Find any one Longest Common Subsequence

of given two strings using Dynamic Programming.

S1=abbacdcba

S2=bcdbbcaac

(i) Explain Branch and Bound Technique in brief.

(ii) Explain “minimax” principle with its use.

(i) Compare NP-Hard with NP-Complete problems.

(ii)Give the algorithm to solve Tower of Hanoi Problem.

Comment on the complexity of the algorithm.

(b) Explain the use of Backtracking method for solving Eight Queens Problem giving its algorithm

OR