1
acnvSeat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA INTEGRATED SEMESTER-IX EXAMINATION-WINTER 2017
Subject Code: 4490601
Subject Name: Design and Analysis of Algorithms Date: 02-11-2017
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

What to do you mean by algorithm analysis? Explain all the asymptotic notations used for analyzing algorithms.
05
Arrange the following rate of growth in increasing order 2n n log n2 log n3
02

Do as directed.
Write and apply bubble sort algorithm for sorting data

04
Define optimal solution, Feasible solution and principle of Optimality
03
Q.2

What is divide and conquer technique? How it is used for Binary Search technique? Give the limitations for D&C.
07

Explain how multiplication of numbers can be done using Explain it by giving the steps to multiply 2345 and 2431.
07
OR

Give the algorithm to find the square root of a number. Can we use divide and conquer strategy for it?
07
Q.3

Define MST. Explain the Prim's Algorithm to find the MST giving example. Compute its time complexity.
07

Given coins of denominations 2,4 and 5 with amount to be pay is 7. Find optimal number of coins and sequence of coins used to pay the given amount using dynamic method.
04
Compare and contrast Greedy and dynamic algorithms
03
OR
Q.3

Explain Dijkstra's algorithm to find minimum distance of all nodes from a given node.
07

Explain algorithm to multiply chain of matrices using dynamic programming method with example. Consider the sequence of 4 matrices as
07
Q.4

Explain Rod cutting problem. Give its algorithm and compute its time complexity.
07

Explain Depth first Search Traversal method give its algorithm and compute its time complexity. Also give the difference between DFS BFS
07
OR
Q.4

Explain Back tracking . What is N-Queen's problem? Give the solution for 4-Queen's problem. Compute its time complexity.
07

What do you mean by Knapsack problem? Give the difference between fractional knapsack and 0-1 knapsack problem. Give the algorithm for greedy knapsack.
07
Q.5

Define and explain NP, NP complete and NP Hard problems.
07
2

Compute the computation time for the statement t3 in the following code fragment
for I 1 to n

for j=1 to n


………………….t3


04
Write a brief note on branch and bound technique
03
OR
Q.5

Define Recursion. Give the limitations of recursion. How to compute the time complexity of recursive algorithms?
07

Explain Job sequencing problem. Explain it using proper example. Give its time complexity.
07