CamScanner 10-11-2023 23.32

Fall 2023, CS3130, Dr. W. He Homework Assignment 1 (25 Questions: Answers) (Due 10/7/2023 Saturday) Noqw V Name: ¢l l. Given a polynomial as follows, 2 4 6 8 1 \ e P(z) = ap 4+ a12® + apx® + azz®, <9, & Qd\. vugh + X to evaluate it for arbitrary coefficients {ag, a1, as, a3} and some given value z, the P ) X{ minimum number of multiplications that one needs is: = 44 4 Qq' + (qfl b Ak )q\ ‘ q 4 ) 5 (c¢) 6 (d) 7ormore Ko 2. Nobody can find a solution to find the minimum in an n-element array with fewer than n — 1 comparisons, even after 100 years. (a) true false 3. Which of the following growth functions has the highest order of growth? (a) »n (b) logn (c¢) nlogn n2 4. When we use the linear search on many different input arrays, sometimes we have unordered arrays and sometimes we have ordered arrays. Which of the following statements about the efficiency is correct? (a) We will get better efficiency whenever we process the ordered arrays. (b) We will get better efficiency whenever we process the unordered arrays. ¢ We will get the same efficiency no matter we process the ordered or unordered arays aoes not contain any adjacent inversion, then it does not contain LON. i€ b} false ble that one can find the solution for the problem: Finding the minimum ray with n elements with an algorithm that is in ©(n)? yes (b) no 7. To evaluate a monomial z*® for a given value 2z, what is the minimum number of multiplications that you need? , : ) ( ] 7R 4 = ‘ ¢ * 4 q’(\(%;x\"x - N ,X-X; : ) TS Ans: K- A =% w2 KT X R X o *

A8y A good iden o APy the P wee fwotoresateon Mothod G Do Ve groadeat Sor ob o 1000t posttive intepera’ \;\‘ AR \\l\“ no O Let moand n be two posttive integers, and m e Phen we npply Lhee Diiaion Hgoniiim and get the following equation for some tntegers ¢ nnd r, me=gn e with 0 e Which of the following equalitios is correct? (&) god(mn) = ged(g.n) () ged(ryn) = ged(g,n) () god(m n) = ged(q, 1) w ped(mn) pod(n,r) 10. Given a polynomial as follows, 3 7 P(x) = ag + a,2° + aga” + aga! + a2 ) to evaluate it for arbitrary coeflicients {ay, ay,ay, a3, a4} and some given value z, the minimum number of multiplications that one needs is: (a) 5 @/ 6 (¢) 7 (d) 8ormore 11. Which of the following growth functions has the lowest order of growth? (a) vn*+4n+7 (b) 27 @ = (d) log n 12. § n + logn Vhich of the following growth functions has the lowest order of growth? e n® + 5n + 8 logn (b)) ——— B (c) n0000001 (d) /mlogn of the following functions increases faster in the long run? N (a) )1.0000001" (b) n34578% J 14. Given a 5-element array, say {z;, &2, 3, 24, T5}, it is known that 1 vy < @4 and Z; < o9. Based on the given information, which element cannot be the (a)) z;y (b) =z (c) / b median? zz (d) x4 15. Given a chessboard, we want to find those squares of different sizes with 2 black squares and 2 white squares at its 4 corners. Ho w many such squares can you find? AR = I8 = L/ 7/ \ / { «~ | : /,‘ + R) % L - 7

23. Given a 4-clement array, say {2, %, 23,24}, with 2; < 23 and z3 < 24, how many more comparisons do you need to find the 2nd largest element? Ans: a 24. Given a 6-element array with distinct elements, say {rl,zg,rs,m,Is,Is} it is known that z, is not the minimum. Is it possible that one can use 2 compar- isons to find an element that is neither the mazimum nor the minimum? (If ye ] please describe the main steps of your solution.) S Solutlon\J © / ”\":,‘ QH‘\( @ ComPard Yq qnd ‘/\3 ‘\h\/ . I F X&7 )(g = E(Se, X; ?X? A~ @) PRI x5 and X, Q) comPiry Xo aad K Be voox, W 1F Ra K - LK, !VCT"*‘{i“ or (1 ¢ \W’é RO " ke : q % L[;‘}‘E[r‘t i /‘ /Y‘ \w\";__ i f’: FlSe \1—‘ ) E | .,-AA ‘4 R et Y. ’ ";‘\;\’& N O UT MIN (,F rf\(,\)( 7 { S M X & Given two ordered arrays {aj,as,az} and {by,bs,b3,bs} with ay < a Qs and / +1 < by < by < by, we want to find the median of these seven elements '~.nallest element of all, and assume that all the elements are distinet) After we ¢ the first comparison on a, and b, and get a; < by, what are those elem be eliminated from the consideration as the median? nts 1 Solution: Wt Wdn+ 4—('\D (— ZAAD ;...v\ |¢‘ r(g()g A _______ NLqad4s b,Chq th O ‘{q<g -Swee. 4y s RSS ‘HW $ovf (\Qmm‘»a' 0 aw OA [,V‘f\ - M 0 (}\.(”\, K S WR E4OM 49 6 gMmAaten +laon de —> So kA0 AT O LAy | ) : o 7 | 1’,'/ c)fi/ ’] 'l) i "):(I 7}?1' + L UN o\ nd A" AN , A d by % gmuwl »#‘*if'f :M_ of kf 2 \)si-.»\ggf.{/“ 0".»?';‘-':\{», HC 0 A | S J\ _,\l/‘/ q e [ (;14) C UAND+ (jQ i "., O\, na ‘ i ) . e Sertel 4 'y Sea \ (43 i< g/o’fl*?{ Fhgn at 1045+ L{. ‘ ¢y \ixfl%m;/\/‘(«“ / (= J (7 ljbg p wh) CUn Cuy #hot (1- (S K\*\ i(\ (\ r+ {“‘\( zfi\ 16\[ 99\(“,4‘ Q\.Q(\‘r\‘\; iy L»-J l/\ ’ \ ‘ o f ‘)'*1- ')J- +"{ 'f\ed(q,