1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
BE SEMESTER- V • EXAMINATION WINTER 2016
Subject Code: 150703 Date: 19/11/2016
Subject Name: Design and Analysis of Algorithms
Time: 10:30AM 01:00PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1

Explain all asymptotic notations used in algorithm analysis.
07

What is Recursion? Give Recursive algorithm for Tower of Hanoi Problem and give analysis of it.
07
Q.2

Explain Greedy method in detail with example and differentiate it with dynamic method.
07

Differentiate BFS and DFS.
07
OR

What is an amortized analysis? Explain accounting method and aggregate analysis with suitable example.
07
Q.3

Explain Prim's algorithm with example for construction of MST.
07

Explain Rabin-Karp Algorithm for string matching and give it complexity.
07
OR
Q.3

Explain Kruskal's algorithm with example for construction of MST.
07

Given the four matrix find out optimal sequence for multiplication
07
Q.4

Discuss and derive an equation for solving the 0/1 Knapsack problem using dynamic programming method. Design and analyze the algorithm for the same.
07

Solve following knapsack problem using dynamic programming algorithm with given capacity Weight and Value are as follows
07
OR
Q.4

Explain the use of Divide and Conquer Technique for Binary Search Method. What is the complexity of Binary Search Method?
07

Explain in Brief:
Travelling Salesman Problem, Recurrence Equations, Relation, Approximation Algorithms.
07
Q.5

Explain Strasson's algorithm for matrix multiplication.
07

What is a finite automaton? Discuss how a finite automaton is used for string matching?
07
OR
Q.5

Explain Backtracking Method. What is N-Queens Problem? Give solution of 4-Queens Problem using Backtracking Method.
07

Write a brief note on NP-completeness and the classes-P, NP and NPC.
07