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

Enrollment No._______
Firstranker's choice
GUJARAT TECHNOLOGICAL UNIVERSITY

--- Content provided by FirstRanker.com ---

BE - SEMESTER-V (NEW) EXAMINATION - SUMMER 2019
Subject Code: 2150703 Date: 06/06/2019
Subject Name: Analysis and Design of Algorithms
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:

--- Content provided by FirstRanker.com ---

1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
MARKS
Q.1 (a) What is an algorithm? How does it differ from a flowchart? 03

--- Content provided by FirstRanker.com ---

(b) Give the difference between dynamic programming and the divide-and-conquer method. 04
(c) Explain Asymptotic notation. Arrange the growth rate of 2, n², 1, log n, n log n, 3ⁿ and n in increasing order of growth. 07
Q.2 (a) Differentiate greedy and dynamic programming. 03
(b) Find out the Θ-notation for the function: f(n)=27n²+16n. 04
(c) What is recurrence? Explain the recursion-tree method with a suitable example. 07

--- Content provided by FirstRanker.com ---

OR
(c) Write the Master theorem. Solve the following recurrence using it. 07
(1) T(n)=9T(n/3) +n (ii) T(n)=3T(n/4) + n log n
Q.3 (a) Use the Iteration method to solve recurrence T(n) = T(n-1) + 1, here T(1)=Θ(1). 03
(b) Explain general characteristics of greedy algorithms. 04

--- Content provided by FirstRanker.com ---

(c) Using dynamic programming find out the optimal sequence for the matrix chain multiplication of A_1x10, B_10x3, C_3x12, D_12x20 and E_20x7 matrices. 07
OR
Q.3 (a) Write the best and worst running time of the Insertion sort algorithm. Why does it differ? 03
(b) What are the steps for dynamic programming? Explain the principal of optimality. 04
(c) Determine LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0} 07

--- Content provided by FirstRanker.com ---

Q.4 (a) What is the string-matching problem? Define valid shift and invalid shift. 03
(b) Define P, NP, NP-complete and NP-hard problems. 04
(c) Explain 0/1 knapsack using a suitable example. 07
OR
Q.4 (a) Write pseudo-code for the Naive-String-Matching algorithm. 03

--- Content provided by FirstRanker.com ---

(b) Define spanning tree and MST. How is Kruskal’s algorithm different from Prim’s algorithm? 04
(c) Explain the fractional knapsack problem with an example. 07
Q.5 (a) Define graph, complete graph and connected graph. 03
(b) Differentiate BFS and DFS. 04
(c) Write and explain Dijkstra's algorithm with an example. 07

--- Content provided by FirstRanker.com ---

OR
Q.5 (a) Explain “P=NP ?” problem. 03
(b) Write just steps for Backtracking and Branch-and-Bound algorithms. 04
(c) Explain the travelling salesman problem. Prove that it is an NP-complete problem. 07
FirstRanker.com

--- Content provided by FirstRanker.com ---