1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
BE SEMESTER-VIII EXAMINATION SUMMER 2017
Subject Code:181604 Date:04/05/2017
Subject Name: Design and Analysis of Algorithm (Department Elective II)
Time:10:30 AM to 01: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

Define the following terms:
1. Principle of Optimality
2. Directed Acyclic Graph
3. Minmax principle
4. Minimum Spanning Tree
5.
6. Set
7. Time Complexity
07

Explain Merge Sort algorithm. Derive the algorithmic complexity in Best case, Worst case and Average case analysis.
07
Q.2

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

Write an algorithm for Selection sort. Calculate the time complexity for each case.
07
OR

Differentiate the following:
1. Divide Conquer and Greedy Technique
2. Greedy Technique and Dynamic Programming Technique
07
Q.3

Give the properties of Heap Tree. Sort the following data with Heap Sort Method: 15,19,10,7,17,6
07

Solve the following knapsack problem With the given capacity W=5 using dynamic programming.
ITEM
WEIGHT
VALUE
1
2
12
2
1
10
3
3
20
4
2
15
07
OR
Q.3

Explain Kruskal's algorithm to find minimum spanning tree with an example. What is its time complexity?
07

Explain accounting method of amortized analysis using stack operations.
07
Q.4

Compute Longest Common Subsequence for the strings:

07
2


Explain breadth first search algorithm with example.
07
OR
Q.4

Compute Matrix Chain order for the following matrices:
A4(2x7)
07

Explain recursive algorithm of depth first search for directed graph.
07
Q.5

Explain Rabin-Karp method of string matching with example.
07

Discuss how 8-queen problem can be solved using backtracking.
07
OR
Q.5

Explain branch and bound technique with example.
07

Explain the following terms:
1. P
2. NP
3. NP-Complete
4. NP-hard
07