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
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VIII (Old) EXAMINATION ? WINTER 2019
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. Make suitable assumptions wherever necessary.
3. 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
(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
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
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
FirstRanker.com - FirstRanker's Choice
1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VIII (Old) EXAMINATION ? WINTER 2019
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. Make suitable assumptions wherever necessary.
3. 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
(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
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
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
2
Show schedule of these jobs on minimum number of processors using greedy
approach.
(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
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 - FirstRanker's Choice
This post was last modified on 20 February 2020