Download GTU BE/B.Tech 2018 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) 2018 Winter 8th Sem Old 181604 Design And Analysis Of Algorithm Previous Question Paper

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ?VIII (OLD) EXAMINATION ? WINTER 2018
Subject Code: 181604 Date: 26/11/2018

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) Sort the letters of word ?DESIGN? in alphabetical order using Bubble sort
algorithm.
07
(b) What is algorithm? What do you mean by performance analysis of an algorithm?
Explain average case and worst case analysis with the help of suitable example.
07

Q.2 (a) Explain how to apply the divide and conquer strategy for sorting the elements
using quick sort.
07
(b) Explain asymptotic notation with the help of example. 07
OR
(b) Explain binary search algorithm with divide and conquer strategy and use the
recurrence tree to show that the solution to the binary search recurrence relation
is ? (log n).
07

Q.3 (a) Give and explain Prim?s algorithm for Minimum Spanning Tree and compare it
with Kruskal?s algorithm.
07
(b) Discuss Matrix Chain Multiplication with Suitable example. 07
OR
Q.3 (a) Compute Longest Common Subsequence for the strings:
A=
B=
07
(b) Explain accounting method of amortized analysis using stack operations. 07

Q.4 (a) Discuss how 8-queen problem can be solved using backtracking. 07
(b) Give the algorithm with example to solve 0/1 Knapsack Problem using Dynamic
Programming
07
OR
Q.4 (a) Explain assembly line scheduling with example by dynamic programming. 07
(b) Explain breadth first search algorithm with example. 07

Q.5 (a) Explain Rabin Karp string matching algorithm with an example. 07
(b) Explain the following terms:
A. P
B. NP
C. NP-Complete
D. NP-hard
07
OR
Q.5 (a) What is finite automata? How it can be sued in string matching? 07
(b) Give the algorithm for depth first search of a graph. Also define ?articulation
point of a graph and explain how to find it.
07
*************
FirstRanker.com - FirstRanker's Choice

This post was last modified on 20 February 2020