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

2003 Course Design & Analysis of Algorithms

3 pages, 31 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] P1327 [Total No. of Pages : 3 [3664]-334 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) Prove there exist two irrational numbers X and Y such that Xy is rational. [8] b) c) Prove by mathematical induction All horses are the same color . [8] State whether the function is CORRECT or INCORRECT and justify [2] your answer : 10n2 + 4n + 2 = O(n2). OR Q2) a) Easter Sunday is in principle the first Sunday after the full moon after the spring equinox. Is this rule sufficiently precise to be called an algorithm? Justify your answer. [6] b) Explain building a heap and maintaining the heap property. c) [6] Recursive permutation generator A(x0) = (.......(anx0 + an-1)x0+........a1)x0 + a0 Write an algorithm to evaluate a polynomial using Horner s rule. [6] Q3) a) Write an algorithm for recursively finding the maximum and minimum of the set of elements {a(i), a(i + 1)i......a(j)}. [8] b) Prove GREEDY-ACTIVITY-SELECTOR always produces solutions of maximum size for the activity-selection problem. [8] P.T.O. OR Q4) a) b) Q5) a) Let n = 5, (p1........p5) = (20, 15, 10, 5, 1) and (d1, d2.......d5) = (2, 2, 2, 3, 3). Find the optional solution with prove it. [8] Find a minimum cost path from s to t in the multistage graph of fig(i). [8] Define the following : [8] i) Principle of optimality. ii) Explicit and implicit constraints. iii) Asymptotic notations. iv) Amortized analysis. b) Consider the following instance of the Knapsack Problem : n = 3, m = 20, (P1, P2, P3) = (25, 24, 15) and (W1, W2, W3) = (18, 15, 10). [8] OR Q6) a) b) Write an algorithm for finding a minimum cost binary search tree. [8] And show its computing time is O(n2). Prove if l1 <= l2 <= ........ln, then the ordering ij = j, l <= j <= n, Minimizes Nk lij k=1 j=1 Over all possible permutations of ij. [3664]-334 2 [8] SECTION - II Q7) a) b) Write an recursive Backtracking algorithm for sum of subsets problem. [8] Explain Backtracking solution to the 0/1 knapsack problem. [8] OR Q8) a) b) Explain in detail model for parallel computation. [8] Prove a sorting network with n inputs correctly sorts any set of values on its input if and only if correctly sorts all the 2n input vector consisting only of zeros and ones. [8] Q9) a) Prove the problem of determining whether a Boolean expression is satisfiable is NP complete. [8] CNF satisfiability is polynomially transformable to the clique problem. Therefore, prove the clique problem is NP-complete. [8] b) OR Q10)a) b) Prove partition the minimum finish time preemption flow shop schedule (m > 2). [8] Prove FNS the optional code generation for level one dags on a one [8] register machine. Q11)Write short notes on : a) The 8-Queen problem. b) Cook s Theory. c) Hamiltonian cycles. [18] OR Q12)a) b) c) 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. [6] Prove, if L1, L2 {0, 1}* are languages L1 p L2, then L2 p implies L1 P. [8] Explain in brief NP complete problem. [4] vvvv [3664]-334 3

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: