Odo Hanoi, 65,3); end {hint time complexity em) 1 ifm 1) 2. (1) Show that itis possible to multiply two men matices i atime O(a). (15%) ao @ What do you do about matrices whose size isnot «power of 2? (10%)aa) 8 Te wie # fate a cam am us HREM ARAE SRE | Om RERSMRAK kone sean: ob aig et ! TEA, Ane 1. The procedure MinMax below finds the minimam and maximum in an array X(1.2) cfm numbers with at most n-2 comparisons of real numbers minsx(}; mace for i= 2 t0nd0 XG] max then max = XTi] end () Weite your ow version of Miniax that uses significantly fewer comparisons of «eal numbers. For simplicity, assume that >=2, (15%) (©) Exactly how many compatisons of real numbers does your new algorithm make inthe wore eae? (10%) 2. Consider two sorting algorithms: Mergesot and Heapsort fee (@) Deseribe them, (10%) (@) Show that the runing time for each of them is O(ntogn. (10%) (©) Show that the Mergesor is faster that Heapsort by a constant factor. (5%) iyWane at Fen ele a ws] com am Dike eka we SRERE — BM TH GER IM aH 8 3R3a pel: eRe 44 343m we eee ag OOH as%) 1G) Show that for alt the nonempty bieary trees whose nonterminal nodes have tracy two nonempty childen, the number of leaves ais greater than the umber of nonterminal nodes kd mrt (6) Let Tio be te ime complexity oF the felling fneton F. Express Tin) in terms of Fy). int Fata) itfec=t) return ts return lol HE(O2}, ) (2%) 2. (@)Athiof robbing a safe finds it filled wih W types of tems of varying size and valu, buts only a small Krapsac of eapacity Mo use to carry the goods. The knapsack problem i to find the combination of ems which the thet shoal -choese for his knapsack in order to maximize the total value ofall the items he lakes, Suppose thatthe sizes of items and AY are integec. Can you derive an algorithm forthe knapssck problem with time complexity O(HD07 Ifyou ean, ‘write down your algort. (6) Suppose that the sizes of items and M are real numbers. Can you derive an algorithm forthe knapsack problem with polyromisl time complexity? Explain your aner * weFee nie a tM] came) er an HASM AR AS So BRE, = BAAN | me | sane: ALAD of eo an a fi: reg a 1. Find the time complexity ofthe fllowing functions. (10%) fori=010nd0 begin ink, while j#0 do =5/25 oe end was, furetion Euclid (m,n) while m>0 do begin t= mod my; mat end eee retumn 2. Consider the following internal sorting slgoithms: (selection sort (insertion sort eee (Obubbte sort (@aquick sort Answer the following questions with brief explanation: (25%) frESEEEEEaG (@) Which method run fastest for file which ie already sorted? (b) Which method run fastest fra file in reverse order? (©) Which method run fastest fora file whose keys are all equal? é (© Which method implies the fewest exchanges? (©) Whiet method uses “Divide & Conquer" technique? 23. Please answer the following question briefly with “yes” or “no” {IF any one NP-Complete problem can be solved in polynomial tne, then ll the [NP problems car be solved in polynomial time? (10%)a are 2 cee FFh at | mM kamal Se at WRI RE FH Bes ae / -16,30,8,28.4.10,20,6,18) at the end of each [-— phase of the following algorithms: (0) QuickSore C105) 8) MergeSort (10 9) 2 Derive jhe time complexity ef the Play ¢_aXbarithm for Lincling the minimum enning. tree of a groph Gis I EF, |, |__car_ he graph is_ represent by aay) by) the. gsaph is _topresent by adjacency list” C/T #) {Assume that G has at least one vertex) T:=Q; TV:= {1}; {start with vertex f and no edges) }— dione := false; while T contains fewer than n—1 edges and not done do begin Let (u, v) be a least cost edge such that we TV and v ¢ TV; if there is no such edge then done := true — else add v to TV and (u, v) 10 T; end; if contains fewer than 1 edges then writeln (‘no spanning tree’); Prim’s minimum spanning tree algorithmHLfRHRAF Fa, Fe eee] = Fee ele ot + m| cen en eo YEAR > SHR ASME saan UtRetle pe Biba Om 3. Write a context free grammar that generates all words of an equal number ofa's and b’s. 2576 4 Design a data structure that may access sparse matrices efficiently. Use an example to demonstrate your design. 25% % pRR I Hhel ee * S| Cam) ee at Ri eBARKE ap eeae | BR GHARSRAK 8 sua: pee A Gee Aa: 1a D (CLOSE BOOKS & NOTES) 20% int reeursivetint n) t inti, sum-0; if(n- Steet RoMMe 2 ne OR ata: Hea ot | sata: ERT} Biaduay © .Peonve._the following. Chaotew.s _ ae eee Any. decision tree. that_sorts 1 distinct. NL has_a height Of ok Beast. dogg 80th CBI algoritten that sorts only by comparisons must have a f= Case. computing. hime _of OCs). C15 2) 2. The following. is 0 Sametion ‘that ul idan Caleran. walk tr a connected, undirected groph that Ras wo vertices with odd edges. Path Graph::euler (vertex v) eee oe 2 Path path = { }5 3 for (all vertices w adjacent to v) && (edge (v,w) not yet used)) { 4 mark edge (v,w) as used; 5S path = {(»,w)) VU euler (w) U path; 6 eet 7 return path; 8) shoo that_if_o graph rie represented aby tts. adjacency mubtilists Ard." path” hy. a finlerd Uiat, the. Suine-tion euler’ wortes ta €_.vepresents she of vestices |____dnd. edge « 4 G, respectively. Clo)eal A ake aa Fee mle em] (am) a jae on BLERIRAMER CL PERB > MBA FREMAK % AR ARAL Oars + Baty Bs a : Lees Besduas 9 (CLOSE BOOKS & NOTES) 1 (25%) (@) Describe P and NP. (b) Describe NP-hard and NP-complete. (©) Describe Cook’s theorem, (@)_ What is the first NP-complete problem? (©) Give a method for proving that a problem is NP-complete (ic. list the steps) Explain your answer, 2. (5%) Tong int caleu(int n) l Tong int sum = 0; int is ifn <= 1) return 15 for (i= 1; i<= 10; 144) sum +2 calcu(n-1); return sum; (Find the value of calou(n). (write down the recurrence equation and solve it) (©) Find the time complexity of “calcu” function. (write down the recurrence equation and solve it)bk ar a em Fee Ble tm] (am) oem jae Rieereewgem Seeee | #a HRA Fy We aaans Ut Ere a BEY cay ABA: Groene: 1. 5%) Functions d ands map set of postive integers into set of postive integers. You are given dQ) =5(2) = 13 dQ) = 53) = 2 ny = dna) +2 tne; sto) = sti) +n—1 if nis odd and n> s(n) = s(n2) +n —2. if mis even andn> 4. For integer n 2 2, prove ln) + s(n) =2n-2 and (a) = 2Llogy nl 1 ifgicn<3x24 and i2 ls (ni) =2 Logg nl if3x2H! Sn< 2H and i2 1. 2. (25%) (@) You are given an input file of characters S, A, O,R,T, I,N, G, A,N, D. Use a heap of size three to show how the replacement selection can be used to produce initial runs in the first par of the sort-merge process. (b) What are the meri of the replacement selection when compared with internal sorting algorithms (such as quicksort)?& a) A ake fe Fee mle tt of ay (em) ae ae asewctawem wegee | ewHeReMRM og, ge ae nem . saa 1A IEe. Besdeas 98 + The following procedure Dijkstra is used to solve Single Source Shortest Paths problems. C{ij] stores the length of the a from vertex i to vertex j. If tore is no are from vertex ito vertex j Cf] = 0. S isa set }- _of vertices to which the shortest paths from the source are known. Di] is an array and stores the length of the known shortest path from source to vertex i, We have a digraph G with 10 vertices and vertex 1 is the source. I the original data C[5,4] is damaged, then which part of the answer setD is unaffected? |___ procedure Dijeiro; { Dijkstra computes the cost of the shortest paths from veriex | to every vertex of a ditected graph } Desi wo eee ata Q iniitize Dy |__ «a for 1:= 1 t9 n—1 do begin o choose a vertex ib in V—S such that _ lw] is minimums o add w 0S; oO for each vertex» in VS do @ Div = min(Dlr}, Diw] + Cw. wD od anne end; (Dijkstra }