{This question psper contains 8 printed pages.) wets 8 | NOOE OIL Nee ahs teor tng naomi hgiveaiease Unigue Paper Code; 32361801... Naie'oP the Paper”: Detgs ai Kiai 6 Aortme Poa at Name of the Course ae eee No. 7. 1. @ Arrange the tolling functions in the Of nr ak FO 100 Ghai a Ny. i clement in a given aray: di [L.Se Ch) —Gnb SeCLBES) TT Saved - 20/7| 2796 2 ight md) IF 1 Is smaller than the left recursive search in the leftmost prion: iit is ewer than the right mi, pertorm a ecupve seach in the | ‘rightmost partition; else perform a recursive search in i} the middle perttion. Thus, the algérithm performs 4 | comparisons in each iteration and recurses on one-third | of te any. Write the resrence relation for he ing 1 time ofthe algorithm and ove it. o ee zr ‘le it i's cai a Ae For each possible coloring of the three nodes, ion the property tat is Violated. ® a, pero 3 ‘shopkeeper has’ W marbles and m empty bottles, Let oj, Gjnny Oy respectively denote the number of (P marbles the bottles ean contain: The shopkeeper waats to store the marbles in the bottles. ©) Describe grecdy algorithm which minimizes the ‘number of bottles used. (@ How would you modify your algorihan i bottle | ‘also has an cesoviated cost price pj and the ‘onli to minimize the total coet of the bottles sed. Gr) istibuted. Then: (i) will the sort stil S_ sive.comect output? (i) what will be the impact of telaxing this condition on the runaing time ? Justify @ Discuss the run time complenity of the naive string “atohing algorithm, o {8) Compare the space requirements of adjacency list and djacncy matrix ropreseitatins of praph having m © edges and a vertices. ® (© Give a efficent algorithm to fad the minimym element Ju 4 maxcheap, Give the exact runing time of the cy seri, ® Pro.2796 4 He op a7 TS of te ces sch bre) ‘Rte a weldied gph wth etary ce srg? ty your aes, ® 12. (@) Give on efficient algorithm to check if given undirected ‘sah has a cycle, Discuss the time complexity of your algorithm. 3 () For each of the following operations does 2 Red Black ‘Tree work faster than Binary Search Tree? Elaborate © Search iy ontondee avers o 3. (@)A priority queue is implemented in two different ways toring = max heap a ing ‘order of ke} values (higher key value indicates higher priority). Compare the time complexity ofthe following an array sorted in de operations when performed on the two different implementations of the priority queue (@ Finding the maximom element (i) Deleting the maximum element (Gy Taorease the pririty of a certain elenieat (6) 5 (©) Suppose «graph has two edge-Sisjoit spanning trees (wo spanning trees that have #0 edges in common). ‘Argue that inthis graph G, every pair of nodes forms part of s cycle, o (@) Consider the following recursive algorithm to find an optimal schedule for weighted interval scheduling problem: ‘Compute_optt) Ij = 0 then “Retura 0 Blse : Rerum many + Comypse_ opt), Compue op) (© Explain why does his algorithm take exponential time to ran in the wort case () What changes should be made to the above ‘Algorithm fo make t run in polynomial time, o (©) Suppose that an nx n array A consist of 1’s and O's such that in any row of all the 1's come before any 0's in that row. Give an O(algn) algorithm for counting ouAhe umber of U's in A, o Pro.©. (@) Which red-back tree properties may be violated when a 2796 6 +s 2 5. (@) Give an example graph having four nodes that docs @D hhave a topological ordering ® Hicst. The instructor wishes to sort the m integer scores (0 Suppose a lve aay i msntained withthe following 1 policy: the sts inal sre, When ew elements te ded, they we loved tthe oni of he ny tn conse. Witt the ber of pow mens cher ee es 10, the array is resorted and the counter is cleared. ee CONT coutiet a ee, Whe taf ev Ginko es eng Sei cet 00) se th Hien ner tt en Tae ie irs te hihet order bt. Th ely operation on the comer is “nsreneat (©) We use Randomized-Select to select the minimum clement of the array A=<3,2,9,0, 75. Describe « sequence of partitions thet would result in the worst ‘cate performance of the algorithm, o ie sort algorithm is such that depts the worst cate beh the running time ofthe merge sor gorithm nstance, ® ge weights are allowed to be ‘your answer with an argument, o fers and on Integer T. It finds iether there exist two elements in the array that sm up to T and returss 1 on success and 0 onihe 20 SES, ae