联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2020-05-25 11:04

Quiz #7: Analysis of Algorithms/Complexity Classes ICS-33 Spring 2020

When 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). I

will 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 pictures

below: 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 s is 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 your

calculation and simplification to a numerical answer. (b) Briefly explain why it makes little sense for an

algorithm 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 we

find that Tf1(N) = 10 N log2 N and Tf2(N) = 90N where the times are in seconds. (a) Solve algebraically for what size N

these two functions would take the same amount of time, showing how you calculated your answer. (b) for what size

arguments is it better to use f1? f2? (c) Briefly describe how we can write a simple function f that runs as fast as the

fastest 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 where

the 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 shown

in the notes, (a) write the complexity class of each statement on its right, where N is len(alist).

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 you

wrote 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 program

runs 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 your

work/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 in

milliseconds). Based on these times (which are measured and therefore approximate, so don’t expect perfect

results), fill in an estimate for the complexity class (one of the standard ones) for each method and fill in an

estimate for the running time when N = 1,600.

N Time: Method 1 Time: Method 2 Time: Method 3

100 300 20 20

200 604 76 22

400 1,196 325 20

800 2,395 1,178 19

1,600

Complexity

Class Estimate


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp