FirstRanker Logo

FirstRanker.com - FirstRanker's Choice is a hub of Question Papers & Study Materials for B-Tech, B.E, M-Tech, MCA, M.Sc, MBBS, BDS, MBA, B.Sc, Degree, B.Sc Nursing, B-Pharmacy, D-Pharmacy, MD, Medical, Dental, Engineering students. All services of FirstRanker.com are FREE

📱

Get the MBBS Question Bank Android App

Access previous years' papers, solved question papers, notes, and more on the go!

Install From Play Store

Download GTU BE/B.Tech 2019 Winter 8th Sem Old 181604 Design And Analysis Of Algorithm Question Paper

Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2019 Winter 8th Sem Old 181604 Design And Analysis Of Algorithm Previous Question Paper

This post was last modified on 20 February 2020

This download link is referred from the post: GTU BE/B.Tech 2019 Winter Question Papers || Gujarat Technological University


FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-VIII (Old) EXAMINATION - WINTER 2019

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

Subject Code: 181604 Date: 27/11/2019
Subject Name: Design And Analysis of Algorithm
Time: 02:30 PM TO 05:00 PM Total Marks: 70

Instructions:

  1. Attempt all questions.
  2. --- Content provided by FirstRanker.com ---

  3. Make suitable assumptions wherever necessary.
  4. Figures to the right indicate full marks.

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

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]

FirstRanker.com


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


This download link is referred from the post: GTU BE/B.Tech 2019 Winter Question Papers || Gujarat Technological University