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 always faster 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 sometimes faster than an O(N2) algorithm.
Time Time
Time
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)?
(a)
Size
Size
Size
(b)
(c)
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
2
fastest of f1 and f2 for all size inputs. (d) What exact integer value N (±1) solves 𝟐𝟐𝟐𝟐√𝑵𝑵 = 10 (Log2 N )+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.
2
(d2) Based on your calculation, which complexity class 𝑶𝑶(√𝑵𝑵) or O( (Log2 N ) ) 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):
pairs = []
for f in alist:
for s in alist:
if f+s == asum:
pairs.append((f,s))
return pairs
def how_sum_2 (alist,asum):
____ pairs = [] ____ ____ aset = set(alist) ____ ____ for v in alist: ____ ____ if asum-v in asset: ____ ____ pairs.append((v,asum-v)) ____ ____ 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