# GTU previous years question papers -BE- Sem-Vth -Design and Analysis of Algorithms -MAY/JUNE – 2012

GTU previous years question papers

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- Vth 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.

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:

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.