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

2003 Course Design & Analysis Of Algorithms

3 pages, 27 questions, 0 questions with responses, 0 total responses,

	pune_eng	+Fave Message
	Profile Timeline Uploads Q & A

Home > pune_eng >

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

Formatting page ...

Total No. of Questions : 12] P1350 [Total No. of Pages : 3 [3864]-401 B.E. (Computer) DESIGN AND ANALYSIS OF ALGORITHMS (2003 Course) Time : 3 Hours] [Max. Marks : 100 Instructions to the candidates : 1) Answer THREE questions from each section. 2) Answers to the TWO sections should be written in SEPARATE answer books. 3) Figures to the right indicate full marks. 4) Assume suitable data, if necessary. SECTION - I Q1) a) Explain what are different ways of measuring the running time of an algorithm? [8] b) With the help of an example, explain the general strategy/method that can be applied for analyzing the efficiency of Recursive and nonrecursive algorithms. [10] OR Q2) a) Prove by contradiction : There are infinitely many prime numbers.[8] b) Prove by mathematical induction on the integer n such that m = 2n.[8] c) State and justify whether the function : 100n + 6 = O(n) is CORRECT or INCORRECT. [2] Q3) a) Write an algorithm for Merge Sort algorithm. Draw the tree structure of the recursive calls made. [8] b) Explain the concept of Divide and Conquer technique and explain its three major variations. [8] OR Q4) a) Write a greedy algorithm to solve the knapsack problem and prove : if p1/w1 p2/w2 ........ pn/wn, then Greedy knapsack generates an optimal solution to the given instance of the knapsack problem. [8] b) Find an optimal solution for the following knapsack instance n = 7, m = 15, (p1, p2, .... p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, ..... w7) = (2, 3, 5, 7, 1, 4, 1) [8] P.T.O. Q5) a) Explain how dynamic programming method can be used for formulating k-stage graph. [8] b) Define the Traveling Salesperson Problem. Solve the TSP problem using Dynamic programming where the edge lengths are given as : 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 [8] OR Q6) a) Consider a complete graph of 4 nodes, where the vertices are vi for i between 1 and 4 and the weight of an edge (vi, vj) is i + j. Obtain a minimum spanning tree for the graph. What is the time complexity of your algorithm? Discuss. [8] b) Write Greedy Algorithm for sequencing unit time jobs with dead lines and profits. [8] SECTION - II Q7) a) What are the constraints that must be satisfied while solving any problem using backtracking? Explain briefly. [6] b) Explain how branch and bound method can be used to solve knapsack problem? [6] c) Write an algorithm to solve the knapsack problem. [6] OR Q8) a) Explain in detail Control Abstraction of LC-Search. [6] b) Write an upper bound function for 0/1 knapsack problem. [6] c) What is n-Queen s problem? Generate the state space tree for n = 4.[6] Q9) a) Prove that : any depth-d, size-n combinational circuit with bounded fan-in can be simulated by a p-processor CREW algorithm in O(n/p + d) time. [8] b) Explain with a neat diagram Randomized-list-Prefix Parallel algorithm for performing prefix computations on a linked list of n = 9 objects.[8] OR [3864]-401 -2- Q10) a) What is satisfiability problem? Prove that CNF - Satisfiability reduces to Directed Hamiltonian Cycle. [8] b) Write an algorithm to find the sum of n-elements of a complete binary tree. What is the time complexity of this algorithm? [8] Q11) a) Prove, if L1, L2 {0, 1}* are languages L1 p L2, then L2 L1 p. b) Prove that vertex cover problem is NP complete. p implies [8] [8] OR Q12) a) The Hamiltonian circuit problem for directed graphs is polynomially transformable to the Hamiltonian circuit problem for undirected graph. Prove that the problem of determining whether there is a Hamiltonian circuit in an undirected graph is NP complete. [8] b) Consider the following search algorithm : j = any value between 1 to n If (a[j] = x) then print Success ; else print Fails Is this algorithm non-deterministic? Justify your answer. rrrr [3864]-401 -3- [8]

Formatting page ...

Tags : Pune, Engineering, University of Pune, Engineering question papers, Pune University, previous year question papers, question papers, india, model question paper, pune university paper pattern, pune university syllabus, old question papers

pune_eng chat

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