# GTU Exam Papers Design and Analysis of Algorithms Dec 2010

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**B.E. Sem-V ^{th} Examination December 2010**

**Subject code: 150703**

**Subject Name: Design & Analysis of Algorithms**

Total Marks: 70

Instructions:

- Attempt all questions.
- Make suitable assumptions wherever necessary.
- 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.

2^{N}, n log n, n^{2}, 1 , n, log n, n!, n^{3}

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.

**(a) **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 06 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.

S_{1}=abbacdcba

S_{2}=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.