M.Sc-M.Sc Computer Science 1st Sem CS - 104 : Design and Analysis of Algorithms(University of Pune, Pune-2013)
M.Sc. (Semester - I)
COMPUTER SCIENCE
SEAT No. :
[Total No. of Pages : 4
CS - 104 : Design and Analysis of Algorithms
(2011 Pattern)
Time :3 Hours] [Max. Marks :80
Instructions to the candidates:-
All questions are compulsory.
Neat diagrams must be drawn wherever necessary. Figures to the right indicate full marks. All questions carry equal marks. Use of calculator is allowed.
Q1) Attempt any eight of the following : [ 8 × 2 = 16]
Define Big- Ohnotation . Is 2n+1 = O (2n) ?
What operations does heap data structure support and what is the growth
rate of these operations ?
Merge sort is in - place algorithm. Justify.
Greedy strategy may not always yield optimal solution. Justify.
What is optimal substructure property ? List any two problems which
satisfy this property.
What is the difference between tree edge and forward edge ?
Why bounding functions are useful in context of Branch and Bound
strategy ?
What is satisfiability problem ? State Cook's theorem.
Define interpolation problem.
Backtracking is Breadth First Search ( BFS) for solution. Justify.
P.T.O.
Q2) Attempt any four of the following : [4 × 4 = 16]
Consider the following algorithm :
Algorithm solve (n)
{
if ( n < 1) then return 1;
else
{
for i = 1 to n do
for j = 1 to n do
k = k+1;
for i = 1 to 4 do
solve (n/2) ;
}
}
Obtain the recurrence relation for the above algorithm. Determine its
time complexity.
Devise a divide and conquer strategy to determine the total number of
positive numbers in an array of n numbers.
Obtain a set of optimal Huffman codes for the messages
( m1, m2, m3, m4, m5, m6, m7) with relative frequencies (f1 , f2, f3, f4, f5, f6, f7) = (1,1, 2, 3, 5, 8, 13). Draw the decode tree for this set of codes.
What is the best way to multiply a chain of matrices having dimensions
13 × 5 , 5 × 89, 89 × 3 and 3 × 34 using dynamic programming.
Show that Breadth First Traversal ( BFT) can be used to obtain the reflexive
transitive closure matrix of an undirected graph.
[4339] - 104 2
Q3) Attempt any four of the following : [4 × 4 = 16]
a) Find out all possible solutions for the following graph coloring problem
with m=3. Also show that only 12 solutions exist with exactly 3 colors.
1 2
4 3
Draw the portion of state space tree generated by Least Cost Branch Bound
( LCBB) method for the following 0/1 knapsack problem instance
where
w = ( 2, 4, 6, 9)
p = ( 10, 10, 12, 18)
m = 15
Write non-deterministic algorithm for max - clique decision problem.
Determine the polynomial of smallest degree that interpolates the points
(0,1) (1,2) and (2,3).
Order the following functions in ascending order of their growth rate :
en, nn, n!, loge (nn) , n2.
Q4) Attempt any two from the following : [2 × 8 =16]
a) Differentiate between Prim’s and Kruskal’s algorithm for finding minimum
spanning tree. Find the minimum spanning tree using Prim’s algorithm for the following graph.
b) Write control abstraction for divide and conquer strategy. Let x,y be two
n-bit numbers. The straight way of multiplying x and y takes O(n2) bit
operations. Show that multiplying x and y n- bit numbers required O(nlog3 )
bit operations using divide and conquer method.
[4339] - 104 3
c) Discuss the features of dynamic programming. Find all pair shortest path
for the following graph using dynamic programming.
Q5) Attempt any two of the following : [2 × 8 = 16]
What is backtracking ? Give the bounding function for backtracking
solution of sum of subsets problem. For the given set of weights w= {5,7,10,12,15,17} and m= 22. Draw the state space tree using variable tuple size and find all possible subsets that give sum of elements as 22.
Why Least Cost Branch Bound (LCBB) is preferred over FIFO & LIFO
branch and bound methods. Consider the following travelling salesman problem instance defined by cost matrix.
ª f 7 3 12 8 º
« 3 f 6 14 9 »
«
»
« 5 8 f 6 18»
« 9 3 5 f 11»
«»
«18 14 9 8 f »
¬ ¼
c)Obtain the reduced cost matrix. Which node will be selected next in LCBB formulation of problem.
Give an algorithm to test whether given diagraph is DirectedAcyclic Graph
(DAG) . Test whether the following diagraph is DAG. If yes, apply
topological sort to produce ordering of vertices. Start from vertex 1.
| Earning: Approval pending. |
