1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
INTEGRATED MCA SEMESTER-IX EXAMINATION WINTER-2018
Subject Code: 4490601 Date: 15-11-2018
Subject Name: Design and Analysis of Algorithms
Time: 10.30 am to 1.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

Do as Directed
1. The Complexity of merge sort is log
2. What are the two main measures for the efficiency of an algorithm?
3. Define Algorithm.
4. Define Optimal Solution and Feasible Solution
5. What is the complexity to add and delete element from bit vector.
6. Define Directed Acyclic graph
7. Define Minimum Spanning Tree.
07

Explain how multiplication of large integers can be done efficiently by using divide and conquer method.
07
Q.2

Define order notation. What is the use of it? What are the various order notations are available? Explain any one of them with example
07

Explain difference between divide and conquer method and dynamic programming. Explain Stressen's Multiplication and compare the time Complexity of that algorithm with regular matrix multiplication.
07
OR

Explain Merge sort using divide and conquer method and computer its worst case running time.
07
Q.3

Give and explain Kruskal's algorithm for Minimum Spanning Tree and compare it with Prim's algorithm.
07

Using greedy algorithm find an optimal schedule for following jobs with n=7 profits and deadline
07
OR
Q.3

Write a brief note on Union-Find Data Structure.
07

Define greedy algorithm and explain the knapsack problem. Find the optimal solution to the knapsack instance n=3 and
07
Q.4

Compare DFS And BFS algorithms. Write an algorithm of BFS.
07

Write a brief note on MutiStage graph using dynamic Programming
07
OR
Q.4

Using algorithm find an optimal parenthesization of a matrix chain product
whose sequence of dimension is use dynamic
programming).
07

Using algorithm determine an Longest Common Sequence of and (use dynamic programming).
07
2
Q.5

Answer the following
1. Explain with example how backtracking algorithm useful in solving
Hamiltonian cycle problem.
2. Find all possible solution for the 4 queen's problem using backtracking.
03
04

Explain 8-puzzle problem in detail.
07
OR
Q.5

1. Compare Branch-bound and Backtracking.
2. Write a brief note on Travelling Salesman Problem. If every city is connected with every other city then find out the total number of edges for TSP of N cities.
03
04

Define NP, NP complete and NP-Hard problems. Give examples of each.
07