CMU 15-112: Fundamentals of Programming and Computer Science
Week8 Practice (Due never)
- Big-O Analysis: Problems and Solutions
Find the Big-O runtime of the given function by computing the runtime of each line.
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) # initial computation of O(nlogn), then runs O(n) times for i in range(1, len(sorted(L)) + 1): # O(nlogn) + n iterations 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))
-
mostCommonName(L) in O(n) time
Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a set of the most common names. So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the set {"Aaron", "Jane"}. If the set is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names. You should write three different versions, one that runs in O(n**2), O(nlogn) and O(n).def mostCommonName(L): return 42 # place your answer here! def testMostCommonName(): print("Testing mostCommonName()...", end="") assert(mostCommonName(["Jane", "Aaron", "Cindy", "Aaron"]) == "Aaron") assert(mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) == {"Aaron", "Jane"}) assert(mostCommonName(["Cindy"]) == "Cindy") assert(mostCommonName(["Jane", "Aaron", "Cindy"]) == {"Aaron", "Cindy", "Jane"}) assert(mostCommonName([]) == None) print("Passed!") testMostCommonName() -
getPairSum(a, target) in O(n) time
Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list. If there is more than one valid pair, you can return any of them. You should write two different versions, one that runs in O(n**2) and the other in O(n). For example:getPairSum([1],1) == [] getPairSum([5,2],7) in [ [5,2], [2,5] ] getPairSum([10,-1,1,-8,3,1], 2) in [ [10,-8], [-8,10] ] (can also return [-1,3] or [1,1]) getPairSum([10,-1,1,-8,3,1],10) == []
def getPairSum(a, target): return 42 # place your answer here! def testGetPairSum(): print("Testing getPairSum...", end="") assert(getPairSum([1],1) == []) assert(getPairSum([5, 2], 7) in [ [5, 2], [2, 5] ]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-8, 10], [-1, 3], [3, -1], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum() - mergeSortWithOneAuxList(a)
Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.