GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-V (NEW) EXAMINATION - WINTER 2018
--- Content provided by FirstRanker.com ---
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:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
MARKS
Q.1 (a) Define Algorithm, Time Complexity and Space Complexity. 03
(b) Differentiate branch and bound and back tracking algorithm. 04
--- Content provided by FirstRanker.com ---
(c) Analyze Selection sort algorithm in best case and worst case. 07
Q.2 (a) Solve the recurrence T(n) = 7T(n/2) + n 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
--- Content provided by FirstRanker.com ---
(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
--- Content provided by FirstRanker.com ---
Q.3 (a) Find out the NCR using Dynamic Method. 03
(b) Find single source shortest path using Dijkstra’s algorithm from 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
--- Content provided by FirstRanker.com ---
(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
--- Content provided by FirstRanker.com ---
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
(c) Explain naive 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
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE/B.Tech 2018 Winter Question Papers || Gujarat Technological University
--- Content provided by FirstRanker.com ---