# GTU Exam papers Design and Analysis of Algorithms

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**B.E. Sem-V****th ****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.**

**Q.1 (a) **Answer the following.

(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

**Q.2 (a) **Answer the following

(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

**(b) **Answer the following.

(i) Explain Branch and Bound Technique in brief.

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

**Q.5 (a) **Answer the following.

(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**

**Q.5 (a) **Answer the following:

(i) Give the characteristics of Greedy Algorithms.

(ii)Define: Directed Acyclic Graph, Dense graph, Sparse graph, Preconditioning.

**(b) **Explain Rabin-Karp method for string matching and also give the algorithm. ** **