GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-VIII (Old) EXAMINATION - WINTER 2019
--- Content provided by FirstRanker.com ---
Subject Code: 181604 Date: 27/11/2019Subject Name: Design And Analysis of Algorithm
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
Q.1 (a) What do you mean by performance analysis of an algorithm? Explain average case, worst case and best case analysis with the help of suitable example. [07]
(b) Define: (1) Algorithm (2) Heap Tree (3) Time complexity (4) Space complexity (5) Set (6) Function (7) Relation [07]
Q.2 (a) Define an amortized analysis. Briefly explain its different techniques. Carry out aggregate analysis for the problem of implementing a k-bit binary counter that counts upward from 0. [07]
--- Content provided by FirstRanker.com ---
(b) Sort the letters of word “EDUCATION” in alphabetical order using insertion sort. [07]OR
(b) Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, and 40. [07]
Q.3 (a) Multiply 981 by 1234 by divide and conquer method. [07]
(b) Discuss Assembly Line Scheduling problem using dynamic programming with example. [07]
--- Content provided by FirstRanker.com ---
OR
Q.3 (a) Describe longest common subsequence problem. Find longest common subsequence of following two strings X and Y using dynamic programming. X=abbacdcba, Y=bcdbbcaac. [07]
(b) Define minimum spanning tree. Find minimum spanning tree using Prim’s algorithm of the following graph. [07]
Q.4 (a) For the following chain of matrices find the order of parenthesization for the optimal chain multiplication (15,5,10,20,25) [07]
(b) Solve the following Knapsack Problem using greedy method. Number of items = 5, knapsack capacity W = 100, weight vector = {50, 40, 30, 20, 10} and profit vector = {1, 2, 3, 4, 5} [07]
--- Content provided by FirstRanker.com ---
OR
Q.4 (a) Following are the details of various jobs to be scheduled on multiple processors such that no two processes execute at the same on the same processor. [07]
Jobs I1 I2 I3 J4 J5 J6 J7
Start time 0 3 6 9 7 1 6
Finish time 2 7 7 11 10 5 8
--- Content provided by FirstRanker.com ---
(b) 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]
Q.5 (a) Explain: Acyclic Directed Graph, Articulation Point, Dense Graph, Breadth First Search Traversal, And Depth First Search Traversal. [07]
(b) Explain in Brief: P-Problem, NP-Problem, Polynomial reduction. [07]
OR
--- Content provided by FirstRanker.com ---
Q.5 (a) Explain Backtracking Method. What is N-Queens Problem? Give solution of 8 Queens Problem using Backtracking Method. [07]
(b) Show the comparisons the naive string matcher makes for the pattern P=0001 in the text T=000010001010001 [07]
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE/B.Tech 2019 Winter Question Papers || Gujarat Technological University