This download link is referred from the post: GTU BE 2020 Summer Question Papers || Gujarat Technological University
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:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
Q.1
- (a) Define the terms:
- Principal of Optimality
- Feasible solution
- Quantifier
MARKS 03
--- Content provided by FirstRanker.com ---
- (b) Analyze Binary search algorithm in best and worst case.
04
- (c) Define Asymptotic notation. Arrange the following functions in increasing order of growth: 2n, n2, 1, log n, n log n, 3n and n.
07
--- Content provided by FirstRanker.com ---
Q.2
- (a) Define the function types:
- One-to-One
- Into (Injective)
- Onto (Surjective)
03
--- Content provided by FirstRanker.com ---
- (b) What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?
07
- (c) Analyze Quick sort algorithm in best and worst case.
07
--- Content provided by FirstRanker.com ---
Q.3
- (a) Analyze insertion sort algorithm in best and worst case.
03
- (b) Differentiate divide and conquer approach with dynamic programming approach.
04
- (c) Solve the following recurrence using Master Theorem: T(n) = 9T(n/3) + n.
04
--- Content provided by FirstRanker.com ---
OR
- (a) Write equation for Matrix Chain Multiplication using Dynamic programming.
07
- (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
- (c) Differentiate greedy programming approach with dynamic programming approach.
04
--- Content provided by FirstRanker.com ---
Q.4
--- Content provided by FirstRanker.com ---
- (a) Solve the following recurrence using Master Theorem: T(n) = T(n/3) + 1.
03
- (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
- (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
- (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
--- Content provided by FirstRanker.com ---
- (c) Find minimum spanning tree using Prim’s algorithm of the following graph.
07
Q.5
- (a) Explain the naive string matching algorithm.
03
--- Content provided by FirstRanker.com ---
- (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 encounter in the text T = 3141592653589793 when looking for the pattern P = 26?
07
--- Content provided by FirstRanker.com ---
OR
- (a) Explain polynomial-time reduction algorithm.
03
- (b) Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is non-Hamiltonian.
04
- (c) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 Queens Problem using Backtracking Method.
07
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE 2020 Summer Question Papers || Gujarat Technological University