Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Summer 5th Sem 2150703 Analysis And Design Of Algorithms Previous Question Paper

Enrolment No.___________

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**BE - SEMESTER? V EXAMINATION ? SUMMER 2020**

**Subject Code: 2150703**

**Date:26/10/2020**

**Subject Name: ANALYSIS AND DESIGN OF ALGORITHMS**

**Time: 02:30 PM TO 05:00 PM**

**Total Marks: 70**

**Instructions:**

**1. Attempt all questions.**

**2. Make suitable assumptions wherever necessary.**

**3. Figures to the right indicate full marks.**

**MARKS**

**Q.1 (a)**Define the terms:

**03**

1) Principal of Optimality 2) Feasible solution 3) Quantifier

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

**04**

**(c)**Define Asymptotic notation. Arrange the following functions in increasing

**07**

order of growth.

2n, n2, 1, log n, n log n, 3n and n.

**Q.2 (a)**Define the function types:

**03**

1) One-to-One 2) Into (Injective) and 3) Onto (Surjective)

**(b)**What is the smallest value of

**n**such that an algorithm whose running time is

**04**

100n2 runs faster than an algorithm whose running time is 2n on the same

machine?

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

**07**

**OR**

**(c)**Analyze insertion sort algorithm in best and worst case.

**07**

**Q.3 (a)**Differentiate divide and conquer approach with dynamic programming

**03**

approach.

**(b)**Solve the following recurrence using Master Theorem.

**04**

T(n)=9T(n/3) + n.

**(c)**Write equation for Matrix Chain Multiplication using Dynamic programming.

**07**

Find out optimal sequence for multiplication:

A1 [5 ? 4], A2 [4 ? 6], A3 [6 ? 2], and A4 [2 ? 7]. Also give the optimal

solution.

**OR**

**Q.3 (a)**Differentiate greedy programming approach with dynamic programming

**03**

approach.

**(b)**Solve the following recurrence using Master Theorem.

**04**

T(n) = T(2n/3) + 1.

**(c)**Using greedy algorithm find an optimal schedule for following jobs with n=6.

**07**

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).

**Q.4 (a)**Define and explain P and NP problems with suitable example.

**03**

**(b)**Solve the following Knapsack Problem using greedy method. Number of

**04**

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}.

**(c)**Find minimum spanning tree using Krushkal's algorithm of the following

**07**

graph.

1

**OR**

**Q.4 (a)**Define and explain NP-complete and NP-hard problems with suitable example.

**03**

**(b)**Explain Dijkstra's algorithm to find the shortest path.

**04**

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

**07**

**Q.5 (a)**Explain the naive string matching algorithm

**03**

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

**04**

**(c)**Working modulo q = 11. How many spurious hits does the Rabin-Karp matcher

**07**

encounter in the text T = 3141592653589793 when looking for the pattern P

=26?

**OR**

**Q.5 (a)**Explain polynomial-time reduction algorithm.

**03**

**(b)**Prove that if G is an undirected bipartite graph with an odd number of vertices,

**04**

then G is non-Hamiltonian.

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

**07**

Queens Problem using Backtracking Method.

*****************

2

This post was last modified on 04 March 2021