” 辅导ICS-33python程序、data留学生程序 写作Quiz #7: Analysis of Algorithms/Complexity Classes ICS-33 Spring 2020When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed.Submit your completed written quiz on Gradescope by Friday May 29th at 11:30pm (in the Irvine time zone). Iwill post my solutions to Piazza reachable via the Solutions link on Saturday morning.1. (3 pts) Sketch approximate Size vs. Time curves for the two algorithmic complexity classes required in each of the picturesbelow: for one, write Impossible instead: (a) An O(N) algorithm tHat is alwaysfaster than an O(N2) algorithm.. (b) an O(N)algorithm that is never faster than an O(N2) algorithm. (c) an O(N) algorithm that is sometimesfaster than an O(N2) algorithm.2. (2 pts) Assume that a function sis in The complexity class O(). (a) What is its doubling-signature:how much more time (by what factor) does it take to solve a problem twice as large? Show yourcalculation and simplification To a numerical answer. (b) Briefly explain why it makes little sense for analgorithm to be in the complexity class O(1/n)?3. (6 pts) Assume that functions f1 and f2 compute the same result by processing the same argument. Empirically wefind that Tf1(N) = 10 N log2 N and Tf2(N) = 90N where the times are in seconds. (a) Solve algebraically for what size Nthese two functions would take the same amount of time, showing how you calculated your answer. (b) for what sizearguments is it better to use f1? f2? (c) Briefly describe how we can write a simple function f that runs as fast as thefastest of f1 and f2 for all size inputs. (d) What exact integer value N (1) solves = 10 (Log2 N2)+1000?Use a calculator, spreadsheet, or A program to guess and refine your answer (try plotting values to see wherethe curves meet). Your answer should be correct for all digits up to the ones-place: e.g., a number like 23,728.(d2) Based on your calculation, which complexity class () or O( (Log2 N2)) grows more slowly; why?4. (6 pts) The Following functions each determine all pairs Of two values in alist that sum to asum. As Is shownin the notes, (a) write the complexity class of each statement on its right, where N is len(alist). 辅导Algorithms作业、data留学生作业 写作、 辅导Java、Python，c++程序语言作业def how_sum_1 (alist,asum): def how_sum_2 (alist,asum):pairs = [] ____ pairs = [] ____for f in alist: ____ aset = set(alist) ____for s in alist: ____ for v in alist: ____if f+s == asum: ____ If asum-v in asset: ____pairs.append((f,s)) ____ pairs.append((v,asum-v)) ____return pairs ____ Return pairs ____(b) Write the full calculation that computes the complexity class for the entire function. (c) Simplify what youwrote in (b).5. (5 pts) Assume that function f is in the complexity class O(N (log2 N2)), and that for N = 1,000 the programruns in 10 seconds.(a) Write a formula, T(N) that computes the approximate time that it takes to run f for any input of size N.Show your work/calculations by hand, approximating logarithms, then finish/simplify all the arithmetic.(b) Compute how long it will Take to run when N = 1,000,000 (which is also written 106). Show yourwork/calculations by hand, approximating logarithms, finish/simplify all the arithmetic.6. (3 pts) Assume that We have recorded the following data when timing three methods (measured inmilliseconds). Based on These times (which are measured and therefore approximate, so dont expect perfectresults), fill in an estimate for the complexity class (one of the standard ones) for each method and fill in anestimate For the running time when N = 1,600.N Time: Method 1 Time: Method 2 Time: Method 3100 300 20 20200 604 76 22400 1,196 325 20800 2,395 1,178 191,600如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
