R- 18 - 115BX. G. Naray namma Institute of Technology & Science (Autonomous) (for Women) Shaikpet, Hyderabad- 500 104 HILB.Tech I-Semester Supplementary Examinations, September-2021 DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science & Engineering) Time: 03 Hours Max. Marks: 70 (Answer any 05 full questions. Each question carries 14 marks) Q.No. Question Marks Bloom's Level Q.1(a) Show that the solution to T(n) = 2T({n/2] + 17) +n is O(n log n). fo7) (Lay (6) Give a recursive algorithm to compute the product of two positive [07] (Lj integers m and n, using only addition and subtraction. 9.2(a) Explain briefly about merge sort? Write an algorithm to arrange the [07] (L2J | elements in sorted order using merge sort? (6) If Sisa set ofn elements, the powerset of S isthe set of all possible [07] [IL] Subsets of $!, For example, if $= (a, b,c) then, Powersei(S') = {(), (a). (b). (©), (a, b), (a, ), (b, ©), (a,b.c)}. Write a recursive algorithm to compute powerset(S). Q.3(a) Consider n= 7, m= 15, (pl, p2, ...., P7) = (10, 5, 15, 7, 6, 18, 3) and [07] {L3) (wl, w 7) = (2, 3, 5,7. 1, 4, 1) obtain the optimal solution for knapsack instance. (®) Consider an example graph and write an algorithm to perform single [07] {L2] source shortest path for each vertex (source) in the graph. Q.4(a) Suppose we start with n sets, each containing a distinct element. Show [07] {La that if u unions are performed, then no set contains more than u + 1 elements. (®) Construct optimal schedule for n= 7. (pl, p2, p3, p4, pS. p6, p7) (100, 10, 15, 27, 120, 55, 40) and deadlines (dl, d2, d3, d4) = (2, 1 1,4,3,1). Q.5(a) Describe the subproblem graph for matrix-chain multiplication with an [07] _—_[L4] input chain of length n. How many vertices does it have? How many. ‘edges does it have, and which edges are they? (07) {L3] 2 () Determine the cost and structure of an optimal binary search tree fora 07] [La] set of n= 7 keys with the following probabilities: eee ita a aes 1 ti ToT DOR TOF 01d 01s OT 4 [005 006 005 0.06 005 005 005 0.05 0.6(a) Explain one Scenario, where the Dynamic Programming can find out 07] [L2] the optimal solution and Greedy method can’t find out. () Find the optimal tour for the following matrix using dynamic [07] (L3) 570 8 63120GNITS-R- 18 - 115BX. Q.7(a) Give a backtracking algorithm for the knapsack problem using the {07} {L2] () 1nd find optimal tourby using travelling 07] [LA] ¢ branch and bound, 8 6 8 0 5 4 8 4 © 8 8 7 3 5 6 o 4 @ 0.8 Write a Non-deterministic algorithm for searching and sorting. (4) (12) END OF THE QUESTION PAPERG. Narayanamma Institute of Technology & Science (Autonomous) (for Women) Shaikpet, Hyderabad- 500 104 II-B.Tech I-Semester Regular Examinations, March -2021. DESIGN AND ANALYSIS OF ALGORITHMS (Computer Science and Engineering) Max. Mark Time: 03 Hours (Answer any 05 full questions. Each question carries 14 marks) QNo. Question Marks Bloom's Level Q.1(a) Explain asymptotic notations for analyzing time complexity with [07] [L2] suitable examples. () Sort the following numbers 3, 16, 12, 14, 11, 15 using Quick sort. [07] [2] | Show the step by step procedure. 4 Q.2(a) Write the algorithm for Merge sort using divide and conquer. o7) (Lay ‘ () Write an algorithm for sequential search and explain the worst, best’ [07] [L3] and average case efficiencies. £ Q.3(@) Explain kruskal's algorithm for finding minimum spanning tree forthe [07] {L3] ? given graph. a iG — ae i @ ie @ (®) Consider a Job Sequencing scheduling problem where the 6 jobs have [07] [La] a profit of (10, 34, 67, 45, 23, 99) and corresponding deadlines (2, 3, 1, 4, 5, 3). Obtain the Optimum schedule. What is the time complexity of your algorithm? Can you improve it. Q.4(a) Find an optimal solution using greedy approach to the following [07] _{L4] ‘knapsack instance n=7, m=15, (pl, p2,.....P7)=(10, 5, 15, 7, 6, 18, 3) and (wl, w2,....,w7)=(2, 3, 5, 7,1, 4, 1). (&) Write the algorithms for the following i) Weighted Union [07] [L2] ii) Collapsing Find. Give suitable example. 2.5(a) Discuss in detail about all pairs shortest path problem. fos] (12) (6) Discuss the construction of optimal binary search tree withanexample. [09] [L2] Page 1 of 2oa ‘matin chain multptication gramming. Also analyze the running tim 26%) Design algorithm by ro ne of your a @ Solve the knapsack instance for BERS Ot 0) = Cashes) Shanes eae 70) Wei atin Stn at Se nn ions eyeles ofa given graph yy yor Oe gee ot eel i ©) Design an algorithm for N-Queens Give a backtracking solution to ON ua ©. Pancens patie a ee os 240) Explain what teNP-ad anNP-Complete pene wry So . (©) tases rots cover ben siheneerne on un s 60 . 2% L > var” END OF THE QUESTION PAPER Page 2 0f2op kee te ey S| WW B Tech I - Semester Regular Examinations 2 M arch —2024 Desiqn AND Awatyers o¢ Atop etrms PRE PRREDBY ; ? Mes ReFauavikepy | Max Marks 110 host Prof. , CSE ¥) Rey meptt Notations : 4. — SS . uate Ne z — : Fe ly sic AS determining Dag 5 erotations eens buctenst thera Geggicients Im the Gmeles ie , foastions : Agwraplet antans,'SIn the bimit”. D Bigori Natabon' the ination Fler: O (fend) EE there ents positive Cnetaats Cx ong Such thot oy £Cn) < Caen) fox all en, n7,70 Ex, ange cunt for ath ny2 0.04 = Rs . 2) Coney Notation: The funtton £Cn)= agcadmazcenee tere exits positive Gnstante Cun Such that £Gn) 7, C# ACAD for atten, NY, Mo ys Eg, B42 YPN for mrt gy Ye « Bns2=9-(n) - | 5) Theta rslaton: The funetion Fenr=9 Gln) Fen) = OCatn)) i¢4 “there eriske positive: Gretawts Cs, Co, HM» Sue that CaP Sten SO Ta as Cn fa, Onde Sun for abt 72 Bee ; bo (7%, G4, N0*? - Steps + 2nd 2O(n)-Code No: 135AF JAWAHARLAL NEHRU. TECHNOLOGICA, 1. UNIVERSITY HYDERABAD B.Tech III Year I Semester Examinations, December - 2019 DESIGN AND ANALYSIS OF ‘ALGORITHMS (Common to CSE, rT) Time: 3 Hours Note: This question La) ») °) ¢ °) 2) b) i) i Max, Marks: 75 Paper contains two parts A and B, Pat A is compulsory which caries 25 make Toman, oF 5 Units. Answer any one fll quest TOmarks and may have a,b as sub questions Answer all questions in Part A. Part B ion from cach unit. Each question carries PART—A 25 Marks) Define 0-notation, 2] Explain “Divide and Conquer Technique”, B) State and explain graph coloring problem. 2) Differentiate between breadth fist Search and Depth first search, B) Define minimum spanning tree. 2) Write any two characteristics of Greedy Algorithm, B) What are the drawbacks of dynami¢ Programming? (2 Write the difference betw Sethe Greedy method and Dynamic programming. GB) Define NP-Complete, 2) ‘iy the Search path in a state-space tree ofa branch 4nd bound algorithm is ‘terminated? B) PART-B, (50 Marks) Apply and explain merge sort to sort the following list: 8, 3, 2, 9, 7, 1, 5, 4. How efficient is merge sort? (19) oR Consider the following recurrence Tea)=8T(w2)+ 0 Obtain asymptotic bound using substitution method, [19] © Graph www.manaresults.co.inOR 5. Given a set of non-negative integers (10, 7, 5, 18, 12, 20, 15}, and a value sum 35, determine if there is a subset of the given set with sum equal to given sum. [19] 6. Write down Prim’s Algorithm for finding the Minimum Spanning Tree of a connected raph, Execute your algorithm on the following graph 2. [19) jo) 2 7. Given the jobs(J1...J6), their deadlines (5,3,3,2.4,2 } and associated profits as {200,180,190,300,120,100}. a) Write the optimal schedule that gives maximum profit. b) Are all the jobs completed in the optimal schedule? ©) What is the maximum eamed profit? [44442] 8. Write down the Floyd Warshall algorithm to solve the all pairs shortest paths problem on a directed graph. Run your algorithm on the following weighted directed graph 3 and show the matrix Dg that results for each iteration of the outer loop. [10] AN, : Se Graph 3 OR 9. Determine the cost and structure of an optimal binary search tree for a set of n= 7 keys with the following probabilities. Where (pl...p7)={ .04 .06 .08 .02 .10 .12 .14) (q0....q7) ={.06 .06 .06 .06 .05 .05 .05 05} {uo} 10a) Prove, If any NP-complete problem belongs to class P, then is P= NP? b) Write a non deterministic algorithm of sorting the list of elements [545] OR 11. Solve the Travelling Salesman Problem for the following graph 4 by using the Branch, and Bound Algorithm. Uo} & Graph 4 www.manaregults.co.inCode No: 135AF JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech III Year I Semester Examinations, November/December - 2018 DESIGN AND ANALYSIS OF ALGORITHMS | (Common to CSE, IT) Time: 3 hours Max, Marks: 75 Note: This question paper contains two parts A and B. La) b) °) d 2 2a) b) 3.a) ») 7a) ») Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of § Units. Answer any one full question from each unit. Each question carries 10 marks and may have a,b, cas sub questions. \ PART-A 4 (25 Marks) Write an algorithm to find the number of digits in the binary representation of a positive decimal integer. 2) How can we measure an algorithm's running time? B) ‘What is a set? List the operations that can be performed on it. 2] Give brief note on graph coloring. B) State the Job ~ Sequencing Deadline Problem. 2] Find an optimal solution to the knapsack instance n=4 objects and the capacity of knapsack m=15, profits (10, 5, 7, 11) and weight are (3, 4 3,5). B) What is Travelling Sales Man Problem? 2) Give the statement of Reliability design problem. Bl State the methodology of Branch and Bound, C2) Define Bounding Function? Give the statement of 0/1 Knapsack FIFO BB. BI PART-B (50 Marks) Explain Recursive Binary search algorithm with suitable examples. Distinguish between Merge sort and quick sort. [545] OR What is stable sorting method? Is Merge sort a stable sorting method? Justify your answer. Explain partition exchange sort algorithm and trace this algorithm for n =8 elements: 24,12, 35, 23,45,34,20,48. 545) Write and explain the algorithm of Bi connected components with an example. [10] OR Give the solution to the 8-queens problem using backtracking, 10) What is Minimum cost spanning tree? Explain an algorithm for generating minimum cost Spanning tree and list some applications of it. (10) OR Explain the greedy technique for solving the Job Sequencing problem. Write with an example of Prim’s algorithm. [5+5] www.manaresults.co.inTime: 3 hours Note: 2a) ») RIG JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech III Year I Semester Examinations, May/June - 2019 DESIGN AND ANALYSIS OF ALGORITHMS (Common to CSE, IT) ‘Max. Marks: 75 This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of § Units. Answer any one full question from each unit, Each question carries 10 marks and may have a,b, a sub questions. PART-A (25 Marks) In what way a time complexity differs from space complexity. (2) Give the general plan of divide and conquer algorithms. . B) Write an algorithm for collapsing find 2 Define Backtracking? List the applications of Backtracking B) ‘What is the importance of knapsack algorithm in our daily life? ical Write Control Abstraction of Greedy method. 8) What you mean by dynamic programming. 2 Define optimal binary search tree with an example. 6) State the difference between FIFO and LC Branch and Bound algorithms. Q Write the Control Abstraction of Least ~ Cost Branch and Bound. 8) PART-B / (50 Marks) ‘What are the different mathematical notations used for algorithm analysis. Write Divide - And - Conquer recursive Quick sort algorithm and analyze the 10) algorithm for average time complexity. OR Write Randomized algorithm of Quicksor. Write an algorithm to determine the Hamiltonian cycle in a backtracking, or Explain the AND/OR graph problem with an example. Explain the Knapsack problem with an example. Write a greedy algorithm for sequencing unit time jobs with deadlines and profits. [10] OR State the Job ~ Sequencing with deadlines problem, Find an optimal sequence to the n= 5 Jobs where profits (PI, P2, P3, P4, PS) = (20, 15, 10, 5, 1) and deadlines (al, €2, 43, d4, d5) =(2, 2, 1,3, 3). {10] www.manaresults.co.in10. 1 Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = (do, if, read, while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1). [10] OR Explain how Matrix — chain Multiplication problem can be solved using dynamic programming with suitable example. (10) Solve the Travelling Salesman problem using branch and bound algorithms. 10) OR Explain the FIFO BB 0/1 Knapsack problem procedure with the knapsack instance for n=, m=15,(p1,p2,p3,p4)=(10,10,12, 18), (w1,w2,W3,w4) =(2, 4, 6, 9). Draw the portion of the state space tree and find optimal solution. {10} —00000— www.manaresults.co.inCode No: 1354R [R16 | JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech DI UI Year 1 Time: 3 hours Max. Marks: 75 Note: This question Part A is con consists of 5 10.marks and may h Paper contains two parts A and B, Unlte eeich caries 25 marks. Answer all questions in Part A. Part B )Units, Answer any one full question from each wait Each question carries havea, b, © as sub questions, PART-A : a (25 Marks) 1a) In. what way a time complexity differs trom space complexity, 2) 2) Give the general plan ofavide and cons algorithms. B) Write algorithm for collapsing find. 2] @) Défitte Backtrackinig? List the applications of Backtracking f BID §) Whats the importance of knapsack algeniion ut daily life? ee Dre } Write Control Abstraction of Greedy reat B) §) What you mean by dynamic programming, 2) 1) Define optimal binary search tree with me example, B] > State the difference between FIFO and LC Bree and Bound algorithms, 2] 2D Write the Control Abstract ion of Least ~ Cost Branch and Bound. algorithm for average time complexity OR Writ Randomized Alg6Fithm of Quieksort, 4 Write an algorithm to determine the Hamiltonian cycle ina given graph using backtracking. {lo} oR 5 Explain the ANDIOR graph problem with an example, 6.2) Expldinthe Knapsaek/problem with ‘anexample. —-/ b) Write.’ greedy afgorithn for sequencing unit OR 7 State the Job — Sequencing with deadlines problem. Find an optimal sequence to the "n= 5 Jobs where profits (PL, P2 PS, P4, P5) = (20, 15, 10, 5, 1) and deadtines (Al, d2, 43, d4, 45) =(2, 2, 1, 3,3) (10)8. Drawan Optimal Binary Search Tree for n=4 identifiers (al a2,a3,a4) = (do, iff read, while) P(L:4)"G.3,1,1) and Q0:4)-23.110. [10] OR 5 £29/ — Explaiit how Matrix chain Multiplication problem fan be solved (ising dynamie, (~~ : programining with’suitable example.) ae) cw (lo) 10/ Solve the Travelling Salesman problem using branch and bound algorithms. [10] OR 11, Explain the FIFO BB 0/1 Knapsack problem procedure with the knapsack instance for ine, m=15<(plsp2,p3,p4)=(10,10,12,18), (WI,W2,W3,W4) =(2, 4, 6, 9). Draw the portion of the state space tree and find optimal solution. W; Uo] ef fn son af .G >f 26 1 aG. Narayanamma Institute of Technology & Science ‘Autonomous under JNTUH (for Women) Shaikpet, Hyderabad- 500 008 IIL B.Tech, II Semester Regular Examinations, May-June 2014 DESIGN AND ANALYSIS OF ALGORITHMS (Common to CSE & IT) Time: 03 Hours Max. Marks: 75 Q1 1. Question paper comprises of Part A and Part B. 2. Part A (for 15 marks) is compulsory and must be answered at one place in the answer book. 3. Answer any 05 full que out of 08 from Part B (for 60 marks) in the answer book. PART-A (Question I comprises of I mark bits and Question 2 comprises of 2 mark bits) 1 2) The time complexity for strassen’s matrix multiplication is Q (4874 o@ Se b) Merge Sort uses jvide and conquer strategy _ii) Back tracking approach iii) Heuristic Search iv) Greedy approach ©) Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is__ : 4) Which of the following problem is not NP bard? i) Hamiltonian cireuit problem “The 0/1 Knapsack problem iif) Finding the biconnected components of a graph iv) The graph coloring problem. ¢) To implement Dijkstra’s shortest path algorithm on weighted graphs so that it can run in linear time, the data structure to be used is i) Queue ii) Stack iii) Heap iv)B-Tree [5x2= 10] a) What is PROFILING’ b) Solve the recurrence relation T(a)=T(n-1)H1 TU) ¢) Compare and contrast Dynamic programming with Greedy method. d) The recurrence relation T( T(a)=3T(n/4yen Has the solution T(n)= ? ©)Obtain an OBST with equal probabilities for the identifier set (al,a2,a3)= (if, stop, while) END OF PARTA Page 1 of 2GN-R-11-110523 PART-B (Answer any 05 full questions. Each question carries 12 marks) _Q.4~~ Draw the portion of state space tree generated by the following knapsack instance. [12] N=, (Phyeoy Ps) = (19,15,6,8,4); (Wiaeeeseey W5) = (4654.2) and m=12 by using following techniques. DOD 4) i) LCBB (ys stort OZ (i) FIFOBB Ve @,$fa) What are the different mathematical notations for computing time and space [06] complexities? z (6) What is the difference between Profiling and Debugging? a 106) Q.Sfa) Explain set representation using trees. x 104] (8) Develop algorithms for UNION and FIND using weighing and collapsing rule. 108] O.64a Analyse the time complexity of Quick sort 0 1,2,3,4,5,6,7- see 106) (®) Compute the average time complexity of Quick sort on a data set of size n. [06] Q.7(a) What is an Articulation Point? [04] (6) Devise an algorithm that identifies all the articulation points of a given Graph? 108) 0.8(a) Give an algorithm for finding all Hamiltonian cycles in a given Graph. [06] [06] —"™ Obtain matrix chain multiplication for the following matrices; Agua» Buowy, Cassi, Diss 0.9) Let W>(5,7,10,12,15,18,20) and M=35. Find all possible subsets of W which sum to [06] M using an algorithm. What is its complexity. (6) Draw the state space tree for MCOLORING where n=3 and m=3, [06] Q.464) Give a Deterministic and Non deterministic algorithms for sorting a set of [06) (B) Solve the Greedy Knapsack problem where m=25, n=3, P=(25,24,17), (06) W=(16, 14, 9). 5 a v END OF PART B END OF THE QUESTION PAPER ) 4 6 $ 2 loags Page 2 of 2