cs1010s Flashcards
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 { True } else { False }):
x = -x
C
while “”:
res += 1
D
while x != 1:
x = x // 2
if x % 3 == 0:
break
E
while x != 1:
if x % 3 == 0:
continue
x = x // 2
F
while x != 1:
break
G
while x != 1:
if x % 3 == 0:
break
x = x // 2
A
C
E
F
G
x = 3
x * x < 9
FIND OUTPUT
FALSE
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
A,C,D,F
def f(x):
if x <= 0:
return 1
else:
y = f(x - 2)
return 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.
3
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)
A,D,F
(f)(X) IS A FUNCTION CALL!!!!!!
def f(n):
res = 0
for i in range(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) .
O(N^2)
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
A,B, E
x = 2
def square(x):
x = 3
return x * x
print(square(x), x, square(5))
FIND RETURN VALUE
9 2 9
What is the simplified big-O notation for the expression below?
n2 log(n) + n (log(n))2
O(n**2 log n)
What is the simplified big-O notation for the expression below?
3(n2 + 3n + 6)
O(3(n2 + 3n))
What is the simplified big-O notation for the expression below?
log log(n**2.5)
O(log log n)
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)
C
5(7logbase5(n)) + n5
WHAT IS O(N)
O(n**7)
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)
A
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)
Time: O(1), Space: O(1)
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)
Time: O(n log n), Space: O(log n)
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)
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).
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)
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)
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)
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.
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)
return y + y
3
def f(n):
res = 0
for i in range(n):
res = res + g(i)
return res
If g(i) has time complexity of O(N), find time complexity of f(n)
O(N^2)
