GTU BE 5th Semester 150703 Design and Analysis of Algorithms Summer 2018 Question Paper

1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE – SEMESTER ?V (OLD) – EXAMINATION ? SUMMER 2018
Subject Code:150703 Date:30/04/2018
Subject Name:Design and Analysis of Algorithms
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) Explain why analysis of algorithm is important? Explain: Worst Case, Best Case
& Average Case Complexity with suitable example.
07
(b) Explain linear inequality and linear equations. 07

Q.2 (a) Explain how multiplication of large integers can be done efficiently by using
divide and conquer method.
07
(b) Write an algorithm for selection sort and show that the time complexity of this
algorithm is quadratic.
07
OR
(b) Why amortized analysis is required? Explain any two method of amortized
analysis with suitable example.
07

Q.3 (a) Write Quick sort algorithm and derive the worst case time complexity of quick
sort algorithm.
07
(b) Explain Knapsack problem using greedy method with example. 07
OR
Q.3 (a) Explain LCS problem using dynamic programming with suitable example. 07
(b) Design and explain Dijkstra?s shortest path algorithm 07

Q.4 (a) Explain Backtracking concept and apply the same on 8-queen problem. 07
(b) Describe an assembly line scheduling problem and give dynamic programming
algorithm to solve it.
07
OR
Q.4 (a) What is Articulation Point? Explain how to find an Articulation Point of the graph
with suitable example.
07
(b) Explain Branch and Bound technique with suitable example. 07

Q.5 (a) Explain naive string matching algorithm with example. 07
(b) Explain the concept of P, NP and NP-complete problem 07
OR
Q.5 (a) Explain Breadth First Traversal Method for Graph with algorithm. 07
(b) Explain Floyd?s algorithm for finding out shortest path with example. 07
*************