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

FirstRanker.com

A Firstranker's choice

GUJARAT TECHNOLOGICAL UNIVERSITY

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

BE - SEMESTER- V EXAMINATION - SUMMER 2020

Date: 26/10/2020

Subject Code: 2150703

Subject Name: ANALYSIS AND DESIGN OF ALGORITHMS

Total Marks: 70

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

Time: 02:30 PM TO 05:00 PM

Instructions:

1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

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

Q.1

1. (a) Define the terms:
   1. Principal of Optimality
   2. Feasible solution
   3. Quantifier

   MARKS 03

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

2. (b) Analyze Binary search algorithm in best and worst case.

   04

3. (c) Define Asymptotic notation. Arrange the following functions in increasing order of growth: 2ⁿ, n², 1, log n, n log n, 3ⁿ and n.

   07

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

Q.2

1. (a) Define the function types:
   1. One-to-One
   2. Into (Injective)
   3. Onto (Surjective)

   03

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

2. (b) 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?

   07

3. (c) Analyze Quick sort algorithm in best and worst case.

   07

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

Q.3

1. (a) Analyze insertion sort algorithm in best and worst case.

   03

2. (b) Differentiate divide and conquer approach with dynamic programming approach.

   04

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

3. (c) Solve the following recurrence using Master Theorem: T(n) = 9T(n/3) + n.

   04

OR

1. (a) Write equation for Matrix Chain Multiplication using Dynamic programming.

   07

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

2. (b) Find out optimal sequence for multiplication: A1 [5 x 4], A2 [4 x 6], A3 [6 x 2], and A4 [2 x 7]. Also give the optimal solution.

   03

3. (c) Differentiate greedy programming approach with dynamic programming approach.

   04

Q.4

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

1. (a) Solve the following recurrence using Master Theorem: T(n) = T(n/3) + 1.

   03

2. (b) Using greedy algorithm find an optimal schedule for following jobs with n=6. Profits: (P1, P2, P3, P4, P5, P6) = (20, 15, 10, 7, 5, 3) Deadline: (d1, d2, d3, d4, d5, d6) = (3, 1, 1, 3, 1, 3).

   04

3. (c) Define and explain P and NP problems with suitable example. Solve the following Knapsack Problem using greedy method. Number of items = 7, knapsack capacity W = 15, weight vector = {2, 3, 5, 7, 1, 4, 1} and profit vector = {10, 5, 15, 7, 6, 18, 3}.

   07

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

OR

1. (a) Define and explain NP-complete and NP-hard problems with suitable example.

   03

2. (b) Explain Dijkstra’s algorithm to find the shortest path.

   04

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

3. (c) Find minimum spanning tree using Prim’s algorithm of the following graph.

   07

Q.5

1. (a) Explain the naive string matching algorithm.

   03

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

2. (b) Differentiate between depth first search and breadth first search.

   04

3. (c) Working modulo q=11. How many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when looking for the pattern P = 26?

   07

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

OR

1. (a) Explain polynomial-time reduction algorithm.

   03

2. (b) Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is non-Hamiltonian.

   04

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

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

   07

FirstRanker.com