################################################################################
#Q1
def most_productive_elf(toys_produced):
most_toys = max(toys_produced.values())
for elf, toys_produced in toys_produced.items():
if toys_produced == most_toys:
return elf
################################################################################
#Q2
def two_smallest(L):
m1, m2 = max(L[0], L[1]), min(L[0], L[1])
for i in range(2, len(L)):
if L[i] < m1:
m1, m2 = max(m2, L[i]), min(m2, L[i])
return [m1, m2]
#Complexity: O(n), since the loop repeats n-2 times and each iteration
#takes the same amount of time
################################################################################
#Q3
def col_sum(M, col):
s = 0
for row in range(len(M)):
s += M[row][col]
return s
def largest_col_sum(M):
sums = []
for col in range(len(M[0])):
sums.apped(col_sum(M, col))
return max(sums)
################################################################################
#Q4
#Run it in Python
################################################################################
Q5a:
# L is a list with n = len(L)
total = 0.0
for item in L:
if item > 0.0: #line 4
total += item #line 5
# In the worst case, line 4 and line 5 are repeated n times, since we go through
# the entire list, which is of length n. If addition and assignment are a
# constant-time operations (which we can assume here), the block consisting of
# lines 4 and 5 takes the same amount of time every time it runs. So the runtime
# is proportion to n, i.e., it is O(n).
#
#
Q5b:
# L is a list with n = len(L)
a = 5
for i in range(n):
for j in range(5):
a = i*j #line 5
# The block inside the innermost loop (line 5) is repeated 5n times, since the
# outer loop repeats n times, and the inner loop repeats 5 times every time.
# Assuming (as we should) that multiplication and assignment are constant time
# operations, that means that the runtime is proportional to 5n, i.e., it is
# proportion to n as well. That means that the runtime is O(n).
#
# Q5c is just print_all() from the Dec. 7 lecture:
# http://www.cs.toronto.edu/~guerzhoy/180/lectures/W13/lec1/print_all.py
################################################################################
def filter_out_odds(L):
if len(L) == 0:
return []
if L[0] % 2 == 0:
return [L[0]] + filter_out_odds(L[1:])
else:
return filter_out_odds(L[1:])
################################################################################
#Q7
def elem_in_elems(L, e):
for sub in L:
if e in sub:
return True
return False
def f(s, L):
#s is a string, L is a list of strings
res = [s]
for e in L:
if not elem_in_elems(res, e):
continue
prev_res = res[:]
res = []
for sub_res in prev_res:
split_list = sub_res.split(e)
for i in range(len(split_list)-1):
res.extend([split_list[i], e])
res.append(split_list[-1])
return res
#The function splits the string s over the elements of L, and returns
#a list with all the elements and the splitters in it, in the order
#that they appear in s. For example,
#f("23+3-10", ["+", "-"]) returns ["23", "+", "3", "-", "10"]
################################################################################
#Q8
def consume_all(decomp, op):
def mult(a, b):
return a * b
def add(a, b):
return a + b
ops = {"+": add, "*": mult}
while op in decomp:
i = decomp.index(op)
decomp[i-1:i+2] = [str(ops[op](int(decomp[i-1]), int(decomp[i+1])))]
return decomp
def ev(expr):
decomp = f(expr, ["*", "+"])
decomp = consume_all(decomp, "*")
decomp = consume_all(decomp, "+")
return int(decomp[0])
ev("1*4+2*3*2+2")
################################################################################
#Q9a
#mystery(L, e) returns True iff e in L
#Q9b
#Note that initally, mystery is called with j-i = len(L), and then each time
#there are two (or three, but the third call is smaller, similarly to the
#analysis of mergeSort) calls that mystery makes to itself, with j-i = len(L)//2
#The call tree is (with the numbers equal to j-i)
# 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#
# ....................................
# n/4 n/4 .. ..
# \/ \/
# n/2 n/2
# \ /
# n
#Each call takes the same amount of time, so we just need to add up the numbers
#of calls on each level. This is the same as the number of calls in
#MergeSort, which is O(n)
#https://www.youtube.com/watch?v=Owbm_iYDWxs&feature=youtu.be
#
#In this case, the number of calls is proportional to the runtime, so the
#complexity is O(n) as well.