GTU Analysis And Design Of Algorithms - December 2015 Exam Question Paper

GTU Computer Engineering (Semester 5)
Analysis And Design Of Algorithms
December 2015

Total marks: --
Total time: --

INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Define following terms
(i) Quantifier
(ii) Algorithm
(iii) Big "Oh" Notation
(iv) Big "Omega" Notation
(v) "Theta" Notation

7 M

1(b) Explain an algorithm for Selection Sort Algorithm. Derive its best case, worst case and average case time complexity.

7 M

2(a) Write the Prim's Algorithm to find out Minimum Spanning Tree. Apply the same and find MST for the graph given below.

7 M

Solved any one question from Q.2(b) & Q.2(c)

2(b) What is recurrence? Solve recurrence equation T (n) =T (n-1) + n using forward substitution and backward substitution method.

7 M

2(c) Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.

7 M

Solved any one question from Q.3 & Q.4

3(a) Write Huffman code algorithm and Generate Huffman code for following

Letters	A	B	C	D	E
Frequency	24	12	10	8	8

7 M

3(b) Write an algorithm for quick sort and derive best case, worst case using divide and conquer technique also trace given data (3, 1, 4, 5, 9, 2, 6, 5)

7 M

4(a) Write equation for Chained matrix multiplication using Dynamic programming. Find out optimal sequence for multiplication:
A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesization of matrices.

7 M

4(b) Using greedy algorithm find an optimal schedule for following jobs with n=6.
Profits: (P1, P2, P3, P4, P5, P6) = (20, 15, 10, 7, 5, 3)
Deadline: (d1, d2, d3, d4, d5, d6) =(3, 1, 1, 3, 1, 3)

7 M

Solved any one question from Q.5 & Q.6

5(a) Explain Depth First Traversal Method for Graph with algorithm with example.

7 M

5(b) Explain how to find out Longest Common Subsequence of two strings using Dynamic Programming method. Find any one Longest Common Subsequence of given two strings using Dynamic Programming.
X=abbacdcba
Y=bcdbbcaac

7 M

6(a) Explain Breath First Traversal Method for Graph with algorithm with example.

7 M

6(b) Solve Making Change problem using Dynamic Programming. (Denominations: d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.

7 M

Solved any one question from Q.7 & Q.8

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

7 M

7(b) What is Finite Automata? Explain use of finite automata for string matching with suitable example.

7 M

8(a) Define P, NP, NP complete and NP-Hard problems. Give examples of each.

7 M

8(b) Give and explain Rabin-Carp string matching algorithm with example.

7 M

More question papers from Analysis And Design Of Algorithms

SPONSORED ADVERTISEMENTS