M.Sc-M.Sc Computer Science 1st Sem CS 11 - 104 : Design And Analysis Of Algorithms(University of Pune, Pune-2013)
M.Sc. (Semester - I)
SEAT No. :
[Total No. of Pages : 4
COMPUTER SCIENCE
CS 11 - 104 : Design And Analysis Of Algorithms
(2008 Pattern)
Time : 3 Hours] [Max. Marks : 80
Instructions to the candidates :
1) All questions are compulsory.
2) Neat diagrams must be drawn wherever necessary.
3) Figures to the right indicate full marks.
4) Assume suitable data, if necessary.
Q1) Attempt all of the following : [8 × 2 = 16]
Name sorting algorithm which use divide & conquer strategy.
Define NP-hard class & give an example of decision problem that is NP-
hard
Give the implicit and explicit constraints of 8 Queen’s problem.
DefineΩ notation. Is 3n + 2 =Ω (n). Justify.
What do you mean by minimum spanning tree.
Define principle of Optimality? State one essential difference between
greedy method and dynamic programming.
Show that there is no solution to the 2-queens.
Define live node and dead node.
P.T.O.
Q2) Attempt any four of the following : [4× 5 = 20]
Write insertion sort algorithm and derive its best case and worst case
running time.
Let A [1 .... n] be an array of integer write an efficient algorithm to count
occurrences of given integer using divide and conquer strategy what is its time complexity.
Consider the following instance for job scheduling with deadlines
problems where n = 6. P = (20, 15, 10, 7, 5, 3), d = (3, 1, 1, 3, 1, 3). Give solution obtained using fast greedy method that uses set representation.
Explain string editing problem for X = ( b, b, a, b, a) and Y = (a, b, a, a)
give the matrix of values computed in bottom-up manner.
Using Bellman ford algorithm find length of shortest path from source z
to all other vertices.
Q3) Attempt any four of the following : [4 × 5 = 20]
a) What are the minimum and maximun number of element in a heap of
height h? Is an sorted array, a min heap? Justify.
b) Use strassen’s algorithm to compute the matrix product of following
matrix giving each computational step
⎡ 4 3⎤ ⎡ 3-2⎤
A=⎢ ⎥ B=⎢ ⎥
⎢ 5 6⎥⎣ ⎦
⎢-4 2⎥⎣ ⎦
c) What is best way to multiply a chain of matrices with dimensions that are
13 × 5 , 5 × 89, 89 × 3, 3 × 34. respectively.
[4339] - 14 2
d) Find all possible solution when the following graph is coloured using
exactly 3 colours
e) Explain the function that characterize a non-deterministic algorithm.
Q4) Attempt any four of the following: [4 × 6 = 24]
a) Find out the maximum flow from the network where S is source and T is
sink.
b) Give BFS and DFS for the following graph. Show all steps (Start at
vertex A)
c) What is Travelling salesman problem. Solve the following TSP instance
using Dynamic programming method.
⎡¥ 7 3 12 8⎤
⎢ ⎥
⎢ 3¥ 6 14 9⎥
⎢ ⎥
⎢ 5 8¥ 6 18⎥
⎢ ⎥
⎢ 9 3 5¥ 11⎥
⎢ ⎥
⎢18 14 9 8¥⎥
⎣ ⎦
[4339] - 14 3
Describe LCBB method. Apply it to solve following instance of 0/1
Knapsack problem. w = (3, 4, 6, 2, 5), p = (15, 12, 10, 8, 6) m = 14.
Give the recurrence relation for the value of the optimal solution when
longest common subsequence problem is to be solved using dynamic programming method Give the matrix of the values computed while determining LCS of the following string.
X=BDCABA
Y=AB C B DAB
Define sum of subset problem? Let the weight given the w = (5, 7, 10,
12, 15, 17) and m = 22 Draw the state space tree for the above problem to find all subsets that sum to 22.
| Earning: Approval pending. |
