Download GTU BE/B.Tech 2018 Winter 5th Sem New 2150703 Analysis And Design Of Algorithms Question Paper

Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2018 Winter 5th Sem New 2150703 Analysis And Design Of Algorithms Previous Question Paper

www.FirstRanker.com
1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ?V (NEW) EXAMINATION ? WINTER 2018
Subject Code:2150703 Date:27/11/2018

Subject Name:Analysis and Design of Algorithms

Time: 10:30 AM TO 01:00 PM Total Marks: 70

Instructions:

1. Attempt all questions.

2. Make suitable assumptions wherever necessary.

3. Figures to the right indicate full marks.


MARKS

Q.1 (a) Define Algorithm, Time Complexity and Space Complexity. 03
(b) Differentiate branch and bound and back tracking algorithm. 04
(c) Analyze Selection sort algorithm in best case and worst case. 07

Q.2 (a) Solve the recurrence T(n) = 7T(n/2) + n
3
03
(b) Explain: Articulation Point, Graph, Tree 04
(c) Write Merge sort algorithm and compute its worst case and best-case
time complexity. Sort the List G,U,J,A,R,A,T in alphabetical order
using merge sort.
07
OR
(c) Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42)
find the maximum profit using dynamic method.
07
Q.3 (a) Differentiate the Greedy And Dynamic Algorithm. 03
(b) Demonstrate Binary Search method to search Key = 14, form the array
A=<2,4,7,8,10,13,14,60> .
04
(c) Solve Making change problem using dynamic technique. d1 = 1, d2=2,
d3=4, d4=6, Calculate for making change of Rs. 10.
07
OR
Q.3 (a)
Find out the NCR (
5
3
)Using Dynamic Method.
03
(b) Find single source shortest path using Dijkstra?s algorithm form a to e.

04
(c) For the following chain of matrices find the order of parenthesization
for the optimal chain multiplication (13,5,89,3,34).
07
Q.4 (a) Explain Tower of Hanoi Problem, Derive its recursion equation and
computer it?s time complexity.
03
(b) Explain finite automata algorithm for string matching. 04
(c) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} 07
OR
Q.4 (a) Explain Principle of Optimality with example. 03
(b) Define BFS. How it is differ from DFS. 04
(c) Solve the following instance of knapsack problem using Backtracking
Technique. The Capacity of the Knapsack W = 8 and w = (2,3,4,5) and
value v = (3,5,6,10)
07
Q.5 (a) Draw the state space tree Diagram for 4 Queen problem. 03
(b) Define P, NP, NP-Hard and NP-Complete Problem. 04

www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
FirstRanker.com - FirstRanker's Choice
www.FirstRanker.com
1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ?V (NEW) EXAMINATION ? WINTER 2018
Subject Code:2150703 Date:27/11/2018

Subject Name:Analysis and Design of Algorithms

Time: 10:30 AM TO 01:00 PM Total Marks: 70

Instructions:

1. Attempt all questions.

2. Make suitable assumptions wherever necessary.

3. Figures to the right indicate full marks.


MARKS

Q.1 (a) Define Algorithm, Time Complexity and Space Complexity. 03
(b) Differentiate branch and bound and back tracking algorithm. 04
(c) Analyze Selection sort algorithm in best case and worst case. 07

Q.2 (a) Solve the recurrence T(n) = 7T(n/2) + n
3
03
(b) Explain: Articulation Point, Graph, Tree 04
(c) Write Merge sort algorithm and compute its worst case and best-case
time complexity. Sort the List G,U,J,A,R,A,T in alphabetical order
using merge sort.
07
OR
(c) Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42)
find the maximum profit using dynamic method.
07
Q.3 (a) Differentiate the Greedy And Dynamic Algorithm. 03
(b) Demonstrate Binary Search method to search Key = 14, form the array
A=<2,4,7,8,10,13,14,60> .
04
(c) Solve Making change problem using dynamic technique. d1 = 1, d2=2,
d3=4, d4=6, Calculate for making change of Rs. 10.
07
OR
Q.3 (a)
Find out the NCR (
5
3
)Using Dynamic Method.
03
(b) Find single source shortest path using Dijkstra?s algorithm form a to e.

04
(c) For the following chain of matrices find the order of parenthesization
for the optimal chain multiplication (13,5,89,3,34).
07
Q.4 (a) Explain Tower of Hanoi Problem, Derive its recursion equation and
computer it?s time complexity.
03
(b) Explain finite automata algorithm for string matching. 04
(c) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} 07
OR
Q.4 (a) Explain Principle of Optimality with example. 03
(b) Define BFS. How it is differ from DFS. 04
(c) Solve the following instance of knapsack problem using Backtracking
Technique. The Capacity of the Knapsack W = 8 and w = (2,3,4,5) and
value v = (3,5,6,10)
07
Q.5 (a) Draw the state space tree Diagram for 4 Queen problem. 03
(b) Define P, NP, NP-Hard and NP-Complete Problem. 04

www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
www.FirstRanker.com
2
(c) Find out the Minimum Spanning Tree using Kruskal Algorithm for
given Graph.

07
OR
Q.5 (a) Explain na?ve string matching algorithm with example. 03
(b) Explain DFS algorithm in brief. 04
(c) Find all pair of shortest path using Floyd?s Algorithm for given graph

07

*************
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
FirstRanker.com - FirstRanker's Choice