CMU 15-112: Fundamentals of Programming and Computer Science
Week8 Efficiency Practice (Due never)
| Problems | |
| Mild | |
| Problem 1 | def foo(L): #L is a list
i = 1
listLength = len(L)
result = []
while i < listLength:
result += L[i]
i *= 3
return i |
| Problem 2 | def foo(S): #S is a string
stringLength = len(S)
i = stringLength
result = {}
while i > 0:
result.add(S[i])
i //= 3
return result |
| Problem 3 | def foo(L): # L is a list
lenList = len(L)
count = 0
for i in range(lenList):
for j in range(lenList):
count += L[i]
return count |
| Medium | |
| Problem 4 | def foo(s): #s is a string of length N
result = 0
for char in string.ascii_lowercase:
if char in s:
s = s[1:]
result += 1
return result |
| Problem 5 | def foo(s):
return len(s) |
| Problem 6 | def foo(L): #L is a list
n = len(L)
for i in range(n**2, n**3, n):
L.append(i)
for j in range(n//5, n//2, n//10):
L.pop()
return L |
| Spicy | |
| Problem 7 | def foo(L):
result = []
for i in range(1, len(sorted(L)) + 1):
newList = len(L) * [i]
result.extend(newList)
return sorted(result) |
| Problem 8 | def foo(L): # L is a square, 2D list
n = len(L)
j = 1
count = 0
while j < n:
for i in range(n):
if max(L[j]) in L[i]:
count += 1
j *= 2
return count |
| Problem 9 | def bigOh(L):
new = list()
for i in range(len(L)):
new.extend(L[:i:2])
new.sort()
result = set(new)
return result
|
| Solutions | |
| Mild | |
| Problem 1 | def foo(L): #L is a list
i = 1 # O(1)
listLength = len(L) # O(1)
result = [] # O(1)
while i < listLength: # O(log(N))
result += L[i] # O(1)
i *= 3 # O(1)
return i # O(1)
# Overall -- O(log(N)) |
| Problem 2 | def foo(S): #S is a string
stringLength = len(S) # O(1)
i = stringLength # O(1)
result = {} # O(1)
while i > 0: # O(log(N))
result.add(S[i]) # O(1)
i //= 3 # O(1)
return result # O(1)
# Overall -- O(log(N)) |
| Problem 3 | def foo(L): # L is a list
lenList = len(L) # O(1)
count = 0 # O(1)
for i in range(lenList): # O(N)
for j in range(lenList): # O(N)
count += L[i] # O(1)
return count # O(1)
# Overall -- O(N ** 2) |
| Medium | |
| Problem 4 | def foo(s): #s is a string of length N
result = 0 #O(1)
for char in string.ascii_lowercase: #O(1)
if char in s: #O(N)
s = s[1:] #O(N)
result += 1 #O(1)
return result #O(1)
#Overall - #O(N) |
| Problem 5 | def foo(s):
return len(s) # O(1)
# Overall O(1) |
| Problem 6 | def foo(L): #L is a list
n = len(L) #O(1)
for i in range(n**2, n**3, n): #O(n**2)
L.append(i) #O(1)
for j in range(n//5, n//2, n//10): #O(1)
L.pop() #O(1)
return L #O(1)
#Overall: O(n**2) |
| Spicy | |
| Problem 7 | def foo(L):
result = [] # O(1)
for i in range(1, len(sorted(L)) + 1): # initial computation of O(nlogn),
# then runs O(n) times
newList = len(L) * [i] # O(n)
result.extend(newList) # O(n)
# result has length O(n**2)
return sorted(result) # n**2 log(n**2)
# Overall O(n**2 log(n)) |
| Problem 8 | def foo(L): # L is a square, 2D list
n = len(L) #O(1)
j = 1 #O(1)
count = 0 #O(1)
while j < n: #O(logn)
for i in range(n): #O(n)
if max(L[j]) in L[i]: #O(n)
count += 1 #O(1)
j *= 2 #O(1)
return count #O(1)
#Overall: O(n**2logn) |
| Problem 9 | def bigOh(L):
new = list() # O(1)
for i in range(len(L)): # n times
new.extend(L[:i:2]) # O(i) = O(n)
new.sort() # O(n^2 log(n))
result = set(new) # O(n^2)
return result # O(1)
# O(n^2 log(n)) |