Download GTU B.Tech 2020 Winter 5th Sem 3150703 Analysis And Design Of Algorithms Question Paper

Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Winter 5th Sem 3150703 Analysis And Design Of Algorithms Previous Question Paper

Seat No.: ________
Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER?V (NEW) EXAMINATION ? WINTER 2020
Subject Code:3150703 Date:29/01/2021
Subject Name:Analysis & Design of Algorithms
Time:10:30 AM TO 12:30 PM Total Marks: 56
Instructions:
1. Attempt any FOUR questions out of EIGHT questions.

2. Make suitable assumptions wherever necessary.

3. Figures to the right indicate full marks.


MARKS
Q.1 (a) What is an algorithm? Why analysis of algorithm is required?
03

(b) What is asymptotic notation? Find out big-oh notation of the f(n)=
04
3n2+5n+10

(c) Write an algorithm for insertion sort. Analyze insertion sort algorithm
07
for best case and worst case.


Q.2 (a) What is the difference between selection sort and bubble sort?
03

(b) Write iterative and recursive algorithm for finding the factorial of N.
04
Derive the time complexity of both algorithms.

(c) Solve following recurrence relation using iterative method
07
T(n)=2T(n / 2) + n
Q.3 (a) How divide and conquer approach work?
03

(b) Trace the quick sort for data A = {6,5,3,11,10,4,7,9}
04

(c) Explain master theorem and solve the recurrence T(n)=9T(n/3)+n with
07
master method




Q.4 (a) Write the characteristics of greedy algorithm.
03

(b) Trace the merge sort for data A = {6,5,3,11,10,4,7,9}
04

(c) Find minimum spanning tree for the given graph in fig-1 using prim's
07
algorithm



Fig-1
Q.5 (a) How huffman code is memory efficient compare to fixed length code?
03

(b) Give difference between greedy approach and dynamic programming.
04

(c) Find the Huffman code for each symbol in following text
07
ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE



Q.6 (a) What is principal of optimality? Explain its use in Dynamic
03
Programming Method.

(b) Find out minimum number of multiplications required for multiplying:
04
A[1 ? 5], B[5 ? 4], C[4 ? 3], D[3 ? 2], and E[2 ? 1].

(c) Solve following knapsack problem using dynamic programming
07
algorithm with given capacity W=5, Weight and Value are as follows :
1

---

(2,12),(1,10),(3,20),(2,15)
Q.7 (a) What is finite automata? How it can be used in string matching?
03

(b) Differentiate BFS and DFS
04

(c) Explain Backtracking Method. What is N-Queens Problem? Give
07
solution of 4-Queens Problem using Backtracking Method.



Q.8 (a) Explain Minimax principal.
03
(b) Define P, NP, NP-complete, NP-Hard problems.
04
(c) Explain rabin-karp string matching algorithm.
07

*************
2

---