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

2003 Course Design & Analysis of Algorithms

3 pages, 32 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] [Total No. of Pages : 3 [3764]-411 P1541 B.E. (Computer) DESIGN AND ANALYSIS OF ALGORITHMS (2003 Course) Time : 3 Hours] [Max. Marks : 100 Instructions to 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) b) Prove by generalized mathematical induction that every positive integer can be expressed as a product of prime numbers . [8] Consider the recurrence: T(n) = O(n) T(l) = (l) Show that above recurrence is asymptotically bound by (n). c) [8] State whether the following function is e CORRECT or INCORRECT and justify your answer. [2] 3n+ 2 = O(n) OR Q2) a) Prove by contradiction : There exist two irrational numbers X and Y such that Xy is rational. [8] b) Prove by mathematical induction that the sum of the cubes of the first n positive integers is equal to the square of the sum of these integers. [8] c) State whether the following function is e CORRECT or INCORRECT and justify your answer. [2] 10n2+ 4n + 2 = O(n2) Q3) a) Write an algorithm for sorting n numbers using Quick sort method. Determine its time complexity. [8] P.T.O. b) Write Kruskal s algorithm. Comment on its time complexity. [8] OR Q4) a) With respect to greedy method define the following terms and explain briefly their significance. i) Feasible solution. ii) Optimal solution. iii) Subset Paradigm. [8] b) Write an algorithm for recursive binary search. What is the time complexity for successful search and unsuccessful search? [8] Q5) a) Write a function to compute length of shortest paths of a given graph.[6] b) Write a short note on worst case optimal algorithm. [6] c) Enlist and briefly explain elements of dynamic programming. [4] OR Q6) a) Prove if l1 l2 ........... ln then the ordering ij = j, l j n minimizes. n k k =1 j =1 lij over all possible permutations of the ij. b) [8] Two jobs have to be scheduled on three processors. The task times are given by matrix: 20 J= 3 3. 52 Show all possible schedules for the jobs. Prove that there exists an optimal schedule. [8] SECTION - II Q7) a) Write a Recursive Backtracking algorithm for sum of subsets of a problem. [8] b) Explain how branch and bound can be used to solve Knapsack problem? [8] [3764]-411 2 OR Q8) a) b) Q9) a) Explain in detail control abstraction of L.C. search. [8] Write recursive back tracking schema for m coloring of the graph. [8] Consider the following expression: ((7 (21/3))* 3) + ((9* (10 8)) + 6). Explain how it can be evaluated parallely. [8] b) Explain in detail parallel sorting. [8] OR Q10)a) b) Q11)a) Prove that Hamilton cycle is in NP. [8] State halting problem and prove that it is undividable. To which category (P or NP) does it belong to? [8] What is Satisfiability problem? Explain in detail. [8] b) Write Non deterministic Knapsack algorithm. [8] c) State True or False: Satisfiability problem is NP complete. [2] OR Q12)Write short notes on any three: a) Cook s Theorem. b) AND/OR graph problem. c) 8 Queen s Problem. d) [18] Hamilton Cycles. Y [3764]-411 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: