GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-VIII (OLD) EXAMINATION — WINTER 2018
--- Content provided by FirstRanker.com ---
Subject Code: 181604 Date: 26/11/2018
Subject Name: Design And Analysis Of Algorithm
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
Q.1
(a) Sort the letters of word “DESIGN” in alphabetical order using Bubble sort algorithm. (07)
(b) What is algorithm? What do you mean by performance analysis of an algorithm? Explain average case and worst case analysis with the help of suitable example. (07)
--- Content provided by FirstRanker.com ---
Q.2
(a) Explain how to apply the divide and conquer strategy for sorting the elements using quick sort. (07)
(b) Explain asymptotic notation with the help of example. (07)
OR
(b) Explain binary search algorithm with divide and conquer strategy and use the recurrence tree to show that the solution to the binary search recurrence relation is O (log n). (07)
--- Content provided by FirstRanker.com ---
Q.3
(a) Give and explain Prim’s algorithm for Minimum Spanning Tree and compare it with Kruskal’s algorithm. (07)
(b) Discuss Matrix Chain Multiplication with Suitable example. (07)
OR
Q.3
--- Content provided by FirstRanker.com ---
(a) Compute Longest Common Subsequence for the strings:
A=<X,Y,Z,Y,T,X,Y>
B=<Y,T,Z,X,Y,X> (07)
(b) Explain accounting method of amortized analysis using stack operations. (07)
Q.4
--- Content provided by FirstRanker.com ---
(a) Discuss how 8-queen problem can be solved using backtracking. (07)
(b) Give the algorithm with example to solve 0/1 Knapsack Problem using Dynamic Programming (07)
OR
Q.4
(a) Explain assembly line scheduling with example by dynamic programming. (07)
--- Content provided by FirstRanker.com ---
(b) Explain breadth first search algorithm with example. (07)
Q.5
(a) Explain Rabin Karp string matching algorithm with an example. (07)
(b) Explain the following terms: (07)
A. P
--- Content provided by FirstRanker.com ---
B. NP
C. NP-Complete
D. NP-hard
OR
Q.5
--- Content provided by FirstRanker.com ---
(a) What is finite automata? How it can be sued in string matching? (07)
(b) Give the algorithm for depth first search of a graph. Also define “articulation point of a graph and explain how to find it. (07)
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE/B.Tech 2018 Winter Question Papers || Gujarat Technological University