Embercode: AI-powered software engineer course

1. What does this program print? ``

python
calls = 0


def ways3(n):
    global calls
    calls += 1
    if n < 0:
        return 0
    if n == 0:
        return 1
    return ways3(n - 1) + ways3(n - 2) + ways3(n - 3)


value = ways3(4)
print(f"ways3(4) = {value}, calls = {calls}")

``

ways3(4) = 7, calls = 13ways3(4) = 7, calls = 25ways3(4) = 4, calls = 25ways3(4) = 7, calls = 4

2. What does this program print? ``

python
memo = {}
calls = 0


def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    answer = fib(n - 1) + fib(n - 2)
    memo[n] = answer
    return answer


value = fib(20)
print(f"fib(20) = {value}, calls = {calls}, memo size = {len(memo)}")

``

fib(20) = 6765, calls = 39, memo size = 20fib(20) = 6765, calls = 77, memo size = 19fib(20) = 6765, calls = 20, memo size = 19fib(20) = 6765, calls = 39, memo size = 19

3. What does this program print? ``

python
memo = {}
calls = 0


def paths(row, col):
    global calls
    calls += 1
    if row == 0 or col == 0:
        return 1
    key = (row, col)
    if key in memo:
        return memo[key]
    answer = paths(row - 1, col) + paths(row, col - 1)
    memo[key] = answer
    return answer


ways = paths(4, 4)
print(f"paths(4, 4) = {ways}, calls = {calls}, memo size = {len(memo)}")

``

paths(4, 4) = 70, calls = 33, memo size = 16paths(4, 4) = 35, calls = 33, memo size = 16paths(4, 4) = 70, calls = 17, memo size = 16paths(4, 4) = 70, calls = 33, memo size = 9

4. Using the memo, how many calls does fib(n) make, for n of 2 or more?

n * nn + 12 to the power of n2 * n - 1

5. For paths(size, size), the memoised method makes how many calls?

size + sizesize * size1 + 2 * size * size2 to the power of size

Trees and memo