Download GTU B.Tech 2020 Winter 5th Sem 3150703 Analysis And Design Of Algorithms Question Paper

FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER-V (NEW) EXAMINATION - WINTER 2020

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

Subject Code:3150703 Date:29/01/2021
Subject Name:Analysis & Design of Algorithms
Time:10:30 AM TO 12:30 PM Total Marks: 56

Instructions:

1. Attempt any FOUR questions out of EIGHT questions.

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

2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

MARKS

Q.1 (a) What is an algorithm? Why analysis of algorithm is required? 03
(b) What is asymptotic notation? Find out big-oh notation of the f(n)= 04

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

3n*+5n+10
(c) Write an algorithm for insertion sort. Analyze insertion sort algorithm 07
for best case and worst case.

Q.2 (a) What is the difference between selection sort and bubble sort? 03
(b) Write iterative and recursive algorithm for finding the factorial of N. 04

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

Derive the time complexity of both algorithms.
(c) Solve following recurrence relation using iterative method 07
T(n)=2T(n/2)+n

Q.3 (a) How divide and conquer approach work? 03
(b) Trace the quick sort for data A = {6,5,3,11,10,4,7,9} 04

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

(c) Explain master theorem and solve the recurrence T(n)=9T(n/3)+n with 07
master method

Q.4 (a) Write the characteristics of greedy algorithm. 03
(b) Trace the merge sort for data A.{6,5,3,11,10,4,7,9} 04
(c) Find minimum spanning tree for the given graph in fig-1 using prim’s 07

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

algorithm

Fig-1

Q.5 (a) How huffman code is memory efficient compare to fixed length code? 03
(b) Give difference between greedy approach and dynamic programming. 04
(c) Find the Huffman code for each symbol in following text 07

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

ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE

Q.6 (a) What is principal of optimality? Explain its use in Dynamic 03
Programming Method.
(b) Find out minimum number of multiplications required for multiplying: 04
A[1 x 5], B[5 x 4], C[4 x 3], D[3 x 2], and E[2 x 1].

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

(c) Solve following knapsack problem using dynamic programming 07
algorithm with given capacity W=5, Weight and Value are as follows :

FirstRanker.com

Q.7 (a) What is finite automata? How it can be used in string matching? 03
(b) Differentiate BFS and DFS 04

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

(c) Explain Backtracking Method. What is N-Queens Problem? Give 07
solution of 4-Queens Problem using Backtracking Method.

Q.8 (a) Explain Minimax principal. 03
(b) Define P, NP, NP-complete, NP-Hard problems. 04
(c) Explain rabin-karp string matching algorithm. 07

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

FirstRanker.com