cs1010s

Question 1

Select ALL the code snippets that do not produce syntax error. Assume all variables are already declared.

A
while ​res ​> 0:
res +​= ​1

B
while​ (if x ​< 0 { T​rue } ​else { ​False }):
x ​= ​-​x

C
while​ “​”​:
res​ +​= ​1

D
while ​x ​!​= 1:
x = ​x /​/ 2
if x ​% 3 =​= 0:
break​

E
whil​e x !​= 1:
if ​x ​% 3 =​= 0:
conti​nue
x ​= x ​/​/ 2

F
whi​le ​x !​= 1​:
bre​ak

G
while​ x !​= 1:
if x ​% 3 =​= 0:
bre​ak
x ​= x /​/ 2​

Answer 1

A
C
E
F
G

Question 2

​x ​= ​3

​x ​* ​x ​< ​9
FIND OUTPUT

Answer 2

FALSE

Question 3

Select ALL the linear recursive function definition of the function f. Assume that any other function beside f are defined non-recursively.

A:
def f(x):
return f(x)

B:
def f(x):
return g(x + 1)

C:
def f(x, y):
if x == y:
return x + y
else:
return f(x + 1, y - 1)

D:
def f(x, y):
if x == 1:
return y
else:
z = f(x // 2, y)
return z + z

E:
def f(x, y):
if x == 1:
return y
else:
return f(x // 2, y) + f(x // 2, y)

F:
def f(x, y):
if x == 1:
return y
else:
return y * f(x - 1)

G:
def f(x, y):
if x == 1:
return y
elif x == 2:
return y + y
else:
return x * y

Answer 3

A,C,D,F

Question 4

def f(​x)​:
if x​ <​= 0​:
return​ 1
else​:
y ​= f​(x - 2​)
retur​n ​y +​ y

How many times does the function f get called in the following expression f(​3)
?
Include the call to f(3) in your answer.

Answer 4

3

Question 5

Select ALL the functions below that are NOT higher-order function. Assume that any other function besides f are definitely not higher-order function.

A:
def f(x, y, z):
if x > 0:
return y
else:
return z

B:
def f(x, y, z):
if x > 0:
return y(x)
else:
return z(x)

C:
def f(x, y, z):
if x(y, z) > 0:
return y
else:
return z

D:
def f(x, y, z):
if x > 0:
return y(x)
else:
return z(x)

E:
def f(x, y, z):
if x > 0:
return (y)(x)
else:
return (z)(x)

F:
def f(x, y, z):
if x > 0:
return g(y)
else:
return g(z)

Answer 5

A,D,F

(f)(X) IS A FUNCTION CALL!!!!!!

Question 6

def ​f(n​):
res ​= 0​
for​ i in​ rang​e(n):
res​ = res​ + g​(i)
return​ res

What is the order of growth in time complexity of the function f above with respect to the input n? Assume that the function g(n) has an order of growth in time complexity of
o(n) .

Answer 6

O(N^2)

Question 7

A
def foo(a, b):
return a + a

B
def foo():
return

C
def foo:
return b

D
define foo(a):
return a

E
def foo(a, b, c):
a + b + c

F
def foo(a)
return a

Answer 7

A,B, E

Question 8

x = 2
def square(x):
x = 3
return x * x

print(square(x), x, square(5))

FIND RETURN VALUE

Answer 8

9 2 9

Question 9

What is the simplified big-O notation for the expression below?

n2 log(n) + n (log(n))2

Answer 9

O(n**2 log n)

Question 10

What is the simplified big-O notation for the expression below?

3(n2 + 3n + 6)

Answer 10

O(3(n2 + 3n))

Question 11

What is the simplified big-O notation for the expression below?

log log(n**2.5)

Answer 11

O(log log n)

Question 12

def foo(n):
for i in range(n):
for j in range(n // 2):
print(i, j)

A: Time: O(n**2 / 2), Space: O(1)

B: Time: O(n), Space: O(1)

C: Time: O(n**2), Space: O(1)

D: Time: O(n), Space: O(n)

E: Time: O(1), Space: O(n**2)

Answer 12

C

Question 13

5(7logbase5(n)) + n5

WHAT IS O(N)

Answer 13

O(n**7)

Question 14

def baz(n):
i = 1
while i < n:
i = 2
print(“” * i)

A: Time: O(n), Space: O(n)

B: Time: O(n), Space: O(1)

C: Time: O(n**2), Space: O(1)

D: Time: O(log n), Space: O(n)

E: Time: O(log n), Space: O(1)

Answer 14

A

Question 15

def quux(n):
if n >= 1:
return
for i in range(n):
print(i)
quux(n // 2)
quux(n // 2)

Time: O(log n), Space: O(log n)

Time: O(n), Space: O(log n)

Time: O(n log n), Space: O(log n)

Time: O(n), Space: O(1)

Time: O(1), Space: O(1)

Answer 15

Time: O(1), Space: O(1)

Question 16

def quuz(n):
if n <= 1:
return
for i in range(n):
print(i)
quuz(n // 2)
quuz(n // 2)

Time: O(n log n), Space: O(log n)

Time: O(n), Space: O(1)

Time: O(1), Space: O(1)

Time: O(log n), Space: O(log n)

Time: O(n), Space: O(log n)

Answer 16

Time: O(n log n), Space: O(log n)

Question 17

def wubble(m, n):
if m > n:
return n
return wubble(m + 1, n) + wubble(m + 3, n)

Time: O(2n), Space: O(2n)

Time: O(2**n), Space: O(1)

Time: O(2**(n - m)), Space: O(n)

Time: O(2**(n - m)), Space: O(n - m)

Time: O(2**n), Space: O(n)

Answer 17

Time: O(2**(n - m)), Space: O(n - m)

Similar to the Count Change problem, the recursion call will always split into two calls and since the depth of the recursion tree is at most d = n - m, the most approximate time and space complexity is simply O(2**d) and O(d).

Question 18

def spudow(n):
def boom(x):
for _ in range(x):
print(“bow”)
bow(x - 1)

def bow(x):
    if x < 0:
        return
    boom(x - 1)
    while x > 0:
        print("boom")
        x //= 3

boom(n)

Time: O(n**2), Space: O(n)

Time: O(n), Space: O(n)

Time: O(n**2), Space: O(1)

Time: O(n), Space: O(1)

Time: O(1), Space: O(1)

Answer 18

Time: O(n**2), Space: O(n)

This time, each call of boom(x) will perform an O(x) pre-recursing operation and bow(x) will perform an O(log x) post-recursing operation.

Thus, the total time complexity is n + log(n - 1) + (n - 2) + log(n - 3) + … + 0 = O(n + (n - 2) + (n - 4) + … + 0) = O(n**2)

Question 19

def fum(n):
def fee(n):
if n < 0:
print(‘fum!’)
return
print(‘fee’)
fi(n - 1)

def fi(n):
    fo(n - 1)
    while n > 0:
        print('fi')
        n //= 2

def fo(n):
    fee(n - 1)
    for _ in range(8):
        print('fo')

for n in range(n):
    print('fum?')
    fee(n)

Time: O(3**n), Space: O(n)

Time: O(n**2), Space: O(n)

Time: O(n**2 log n), Space: O(n)

Time: O(n2), Space: O(n2)

Time: O(n log n), Space: O(n)

Answer 19

Time: O(n**2 log n), Space: O(n)

Using the similar thinking process from the previous question, each call of fee(n) will perform an O(1) pre-recursing operation and fi(n) will perform an O(log n) post-recursing operation, and fo(n) will perform an O(1) post-recursing operation.

For each call of fee(n), the recursion will just alternate between fee, fi, and fo. Thus, the total time complexity for only fee(n) is O(1) + O(log(n - 1)) + O(1) + O(1) + O(log(n - 4)) + O(1) + … + O(1) = O(n log n) (the linear terms are smaller than the sum of the logarithms and so is discarded)

Finally, since fum(n) is the combination of calling fee(0), fee(1), and up to fee(n - 1), the total time complexity of fum(n) is approximately O((n - 1)log(n - 1) + (n - 2)log(n - 2) + … + 0) = O(n**2 log n).

Do not confuse the n from the line for n in range(n). This means we are presetting n into a sequence from 0 to the previous value of n, respectively.

Question 20

How many times does the function f get called in the following expression f(​3)?

def f(​x)​:
if x​ <​= 0​:
return​ 1
else​:
y ​= f​(x - 2​)
retur​n ​y +​ y

Answer 20

3

Question 21

def ​f(n​):
res ​= 0​
for​ i in​ rang​e(n):
res​ = res​ + g​(i)
return​ res

If g(i) has time complexity of O(N), find time complexity of f(n)

Answer 21

O(N^2)