**GTU previous years question papers**

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**BE- V****th ****SEMESTER–EXAMINATION – MAY/JUNE – 2012**

**Subject code: 15 **

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

** **

**Instructions:**

**1. Attempt all questions.**

**2. Make suitable assumptions wherever necessary.**

**3. Figures to the right indicate full marks.**

**Q.1 **Answer the following.

Compare Iterative and Recursive algorithm to find out Fibonacci series.

Explain why analysis of algorithms is important? Explain: Worst Case, Best Case

& Average Case Complexity.

Explain characteristics of Greedy Algorithm.

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.

To download engineering ebooks, medical ebooks, management ebooks, free ebooks please visit www.kopykitab.com