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

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

Seat No.: ________
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

---