This download link is referred from the post: GTU BE 2019 Summer Question Papers || Gujarat Technological University
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER- V(OLD) EXAMINATION - SUMMER 2019
--- Content provided by FirstRanker.com ---
Subject Code:150703 Date:31/05/2019
Subject Name:Design And Analysis Of Algorithms
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) Define Algorithm. Discuss factors affecting time complexity of an algorithm. 07
(b) Explain Big Oh (O), Omega (Ω) and Theta (Θ) asymptotic notations. 07
--- Content provided by FirstRanker.com ---
Q.2
(a) Apply merge sort algorithm on array A = {2,7,3,5,1,9,4,8}. What is time complexity of merge sort in worst case? 07
(b) Define Minimum Spanning Tree. Use Krushkal’s algorithm to find Minimum Spanning Tree of given graph 07
OR
(b) Discuss any two methods of amortized analysis in detail 07
--- Content provided by FirstRanker.com ---
Q.3
(a) Write greedy algorithm for job scheduling problem. Derive its time complexity. 07
(b) Write divide and conquer algorithm to solve Exponential problem. Also solve 2n using same algorithm. 07
OR
(a) Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B = “bacac” 07
--- Content provided by FirstRanker.com ---
(b) Explain Depth First Search algorithm for a graph with example. Also explain Tree Edges, Back Edges and Cross Edges 07
Q.4
(a) Solve making change problem using dynamic programming Given amount N=8, and denominations d = {1, 3, 5, 6} 07
(b) What is backtracking? How 4-Queen problem is solved using backtracking? 07
OR
--- Content provided by FirstRanker.com ---
(a) Sort given array A = {27, 46, 11, 95, 67, 32, 78} using insertion sort algorithm. Also perform best case and worst case analysis of insertion sort algorithm. 07
(b) How Rabin Karp algorithm performs string matching? Explain with example. 07
Q.5
(a) Explain P Problem, NP Problem and NP Complete Problem. 07
(b) Write Naive string matching algorithm. Find its time complexity and perform string matching for given pattern P = “ACD” Text T = “CACDACAACDAC” 07
--- Content provided by FirstRanker.com ---
Q.5
(a) Explain in brief: Articulation Point, Directed Acyclic Graph, Recurrence Relations 07
(b) Explain how to solve knapsack problem using greedy algorithms 07
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE 2019 Summer Question Papers || Gujarat Technological University