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

FirstRanker.com

Subject Code: 2150703

GUJARAT TECHNOLOGICAL UNIVERSITY

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

BE- SEMESTER-V (NEW) EXAMINATION - WINTER 2020

Subject Name: Analysis and Design of Algorithms

Time: 10:30 AM TO 12:30 PM

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.

Q.1

1. Define O, Ω, Θ notations with example. (03)
2. Sort following functions in increasing order of running time for large values of n: n, log₂n, 2ⁿ, nlogn, n². (03)

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

3. (i) What are the different parameters to analyze any algorithm? (04)
   (ii) Solve the following using Master’s theorem:
   A. T(n) = 2T(n/4) + 1
   B. T(n) = 3T(n/3) + n

Q.2

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

1. Explain Master Theorem for all three cases. (03)
2. (i) What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine? (04)
   (ii) What is meaning of T(n) = O(1). Explain with suitable example.
3. Given the four matrices P₅x₄, Q₄x₆, R₆x₂, T₂x₇: Find the optimal sequence for the computation of multiplication operation. (07)

Q.3

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

1. Mention the parameters for finding suitable algorithm among many candidate algorithms. Justify parameter with suitable example. (03)
2. i. Which version of algorithm is preferred when memory resources are limited, Iterative or recursive? Justify your answer. (04)
   ii. An asymptotically fast algorithm running on a slow computer is better than an asymptotically slow algorithm running on a fast computer for larger input size. (True/False) Justify your answer with supporting arguments.
3. Analyze Selection sort and Insertion Sort algorithms in best case and worst case scenarios. (07)

Q.4

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

1. Merge sort algorithm have similar time complexity in best, average and worst case. (True/False). Justify your answer. (03)
2. Differentiate between greedy approach and Dynamic approach. (04)
3. How the selection of pivot affects the performance of Quick Sort? Discuss all possible scenarios. (07)

Q.5

1. How to solve knapsack problem using dynamic programming? (03)

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

2. Given two strings from 26 symbols set, X="BITTER", Y = "BUTTER" obtain the longest common subsequence. (04)

Date: 22/01/2021

FirstRanker.com

Total Marks: 56

Q.6

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

1. Explain the concept of amortized analysis with suitable example. (03)
2. Generate Huffman Code for symbols with probability as A1(0.5), A2(0.25), A3(0.125), A4(0.0625), A5(0.0625). (04)
3. Find the all pair shortest path using Floyd-Warshall Algorithm for directed graph. (07)

Q.7

1. How to solve 0-1 knapsack problem using dynamic programming? Consider Items having Value(Rs.)={60, 100, 120}, Weight(KG)={10, 20, 30} respectively, Weight Capacity = 50 KG. (03)

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

2. Define terms: Articulation Point, Isolated, Adjacency (04)
3. Solve the following Task Assignment problem for minimization using following cost matrix. (Cost matrix represents cost of Task T performed by Person P. (07)
   

   	T1	T2	T3
   P1	10	20	25
   P2	20	23	26
   P3	12	16	25

Q.8

1. Find minimum spanning tree for the following undirected weighted graph using Kruskal’s algorithm. (03)

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

2. What is the significance of Hashing in Rabin-Karp Pattern matching algorithm? (04)
3. Draw the Finite automata which accepts String over 26 letter alphabet of {A..Z} : ACACAGA (07)

Explain the concept of P, NP and NP-complete problem

FirstRanker.com

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