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

FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER- V (New) EXAMINATION - WINTER 2019

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

Subject Code: 2150703 Date: 25/11/2019
Subject Name: Analysis and Design of Algorithms
Time: 10:30 AM TO 01:00 PM Total Marks: 70

Instructions:
1. Attempt all questions.

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

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

MARKS

Q.1 (a) Find Omega (O) notation of function f(n)=2n²+ 6 n² + 6n. 03
(b) Define Big-oh and Theta notations with graph. 04

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

(c) Write sequential search algorithm and analyze it for worst case time 07
complexity. Represent its time complexity using Big-oh (O) notation.

Q.2 (a) Find upper bound of function f(n)=lg(n²) + n² lg n. 03
(b) If P(n)=a₀+ a₁n+ a₂n²+ ...... + a_mn^m then prove that P(n) = 04
O(n^m). Here a₀, a₁, a₂ .....a_m are constants and a_m>0.

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

(c) Solve following recurrence relation using suitable method and express 07
your answer using Big-oh (O) notation.
T(n) = T(n/3) + T(2n/3) + O(n)

OR

(c) Solve following recurrence relation using suitable method and express 07

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

your answer using Big-oh (O) notation:
T(n) =2 T(n/2) + n²

Q.3 (a) If T₁(n)=O(f(n)) & T₂(n) = O(g(n)) then prove that T₁(n) + T₂(n) = 03
max(O(g(n)), O(f(n))).
(b) Illustrate the working of the quick sort on input instance: 25, 29, 30, 04

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

35, 42, 47, 50, 52, 60. Comment on the nature of input i.e. best case,
average case or worst case.
(c) Write greedy algorithm for activity selection problem. Give its time 07
complexity. For following intervals, select the activities according to
your algorithm. I₁ (1-3), I₂ (0-2), I₃ (3-6), I₄ (2-5), I₅ (5-8), I₆ (3-10), I₇

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

(7-9).

OR

Q.3 (a) Arrange following growth rates in increasing order. 03
O(n^1/2), O(n^1/3), O(n² lg n), O(n^1/4), O(n²), O(n!), O(vn), O(n³), O(2ⁿ)

(b) Illustrate the working of the merge sort algorithm on input instance: 04

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

10, 27, 30, 88, 17, 98, 42, 54, 72, 95. Also write best case time
complexity of merge sort algorithm.

FirstRanker.com

Q.4 (a) What is Principle of Optimality? Explain it with example. 03
(b) Consider the instance of the 0/1 (binary) knapsack problem as below 04

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

with P depicting the value and W depicting the weight of each item
whereas M denotes the total weight carrying capacity of the knapsack.
Find optimal answer using greedy design technique. Also write the
time complexity of greedy approach for solving knapsack problem.
P=[40 10 50 30 60] W=[80 10 40 20 90] M=110

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

(c) Find the optimal way of multiplying following matrices using dynamic 07
programming. Also indicate optimal number of multiplications
required.
A:3x2, B:2x5, C:5x4, D:4x3, E:3x3

OR

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

Q.4 (a) Explain depth first traversal using suitable example. 03
(b) Explain Binomial Coefficient algorithm using dynamic programming. 04
(c) Find the longest common subsequence for the following two sequences 07
using dynamic programming. Show the complete process.
X =100101001

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

Y =101001

Q.5 (a) Define P and NP problems. Also give example of each type of problem. 03
(b) Draw the state space tree diagram for 4 Queen problem and also show 04
the tree after applying backtracking.
(c) Explain Rabin — Karp algorithm with example. What is expected 07

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

running time of this algorithm?

OR

Q.5 (a) Define NP-Complete and NP-Hard problems. Also give examples. 03
(b) Explain the naive string matching algorithm. 04
(c) State whether Hamiltonian problem is a NP-Complete problem? 07

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

Justify your answer.

FirstRanker.com