
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

Pune University - Sem - I : Design & Analysis of Algorithms, April 2010

4 pages, 24 questions, 0 questions with responses, 0 total responses,

	pune_sci	+Fave Message
	Profile Timeline Uploads Q & A

Home > pune_sci >

Instantly get Model Answers to questions on this ResPaper. Try now!
NEW ResPaper Exclusive!

Formatting page ...

Total No. of Questions : 4] P1060 [Total No. of Pages : 4 [3733]-104 M.Sc. COMPUTER SCIENCE CS11-104 : Design & Analysis of Algorithms (Old & New Course) (Semester - I) Time : 3 Hours] [Max. Marks : 80 Instructions to the candidates: 1) 2) 3) 4) 5) All questions are compulsory. Neat diagrams must be drawn wherever necessary. Figures to the right indicate full marks. All questions carry equal marks. Assume suitable data, if necessary. Q1) Attempt all of the following : [8 2 = 16] a) Define O notation. Is 2n+1 = O(2n)? b) What are prefix codes? What is the use of prefix code. c) Explain relaxing of edge with an example. d) What is the difference between Dynamic programming and Divide and conquer strategy. e) Define articulation point and bridge. f) What is optimal substructure property. List any two problems which satisfy this property. g) Define P and NP class. h) Define explicit and implicit constraints. Q2) Attempt any Four of the following : [4 5 = 20] a) Find an optimal solution to the Knapsack problem instance, n = 7, m = 35, w = (15, 13, 12, 7, 9, 5, 8) and p = (30, 28, 36, 7, 15, 10, 20) b) Define sum of subset problem. What are the rules for generating state space tree? c) Explain Dijkstra s Algorithm. What is its time complexity? P.T.O. d) What is Tower of Hanol problem? Give a recursive algorithm for the problem and find its running time in terms of number of disks n. e) What do you mean by Stable Sorting Algorithm. Prove that counting sort is stable. Q3) Attempt any Four of the following : [4 5 = 20] a) Write a nondeterministic algorithm for max Clique decision problem. b) What is matrix chain multiplication problem. What is the best way to multiply a chain of matrices with dimensions, A = 10 20, B = 20 50. C = 50 1, D = 1 100, using dynamic programming. c) What is the longest common subsequence problem? Find the LCS of following string. X = AGCGA Y = CAGATAGAG d) Explain Breadth First traversal of a graph. Give a breadth first traversal for following graph starting at A, if neighboring nodes are picked in reverse alphabetical order. e) Using Bellman Ford algorithm find lengths of shortest paths from source Z to all other vertices. [3733]-104 2 Q4) Attempt any Four of the following : [4 6 = 24] a) What is minimum spanning tree? Use Prim s and Kruskal s algorithm to find minimum spanning tree of following graph. b) Draw the portion of state space tree generated by LCBB for the Knapsack problem instance given by w = (4, 6, 3, 4, 2), p = (10, 15, 6, 8, 4) and m = 12. c) Derive the time complexity required by Strassen s matrix multiplication. How Strassen s approach different from the ordinary matrix multiplication algorithm. d) What are strongly connected component? Give the algorithm to compute strongly connected component using DFS. Find the strongly connected component of the following graph using above algorithm. e) What is Flow Network? Explain Ford Fulkerson algorithm to find maximum flow and illustrate it on the following network where s is the source and t is the sink. [3733]-104 3 f) Explain Travelling salesperson problem using dynamic programming. Find the shortest path for following instance of TSP defined by cost matrix. 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 [3733]-104 4

Formatting page ...

Additional Info : M.Sc. COMPUTER SCIENCE, CS11-104 : Design and Analysis of Algorithms ( New & Old Course) (Semister - I), Pune University
Tags : msc computer science pune university, msc computer science pune exam papers, Design and Analysis of Algorithms, pune university exam papers, university of pune question papers, pune university science, pune university courses, bsc pune university, msc pune university, pune university solved question papers, pune university model question paper, pune university paper pattern, pune university syllabus, old question papers pune university

pune_sci chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: