CMU 15-112 Spring 2016 Homework 5 Practice
(Due never)

• Do not hardcode the test cases in your solutions.

1. Big-Oh Analysis
2. mostCommonName(L)
3. getPairSum(L, sum)

1. Big-Oh Analysis
   
   What is the big-Oh of each of the following functions?
   
   

   def bigOh1(s):
       charCount=""
       for c in s:
           count = s.count(c)
           if c in charCount: 
               continue
           else:
               charCount += "%s%d " % (c, count)
   
   def bigOh2(s): 
       myS = s * len(s)
       result = ""
       for c in myS:
           if c in result:
              break
           else:
               result += c
       return result
   
   def bigOh3(a):
       for i in xrange(len(a)):
           j=1
           while j < len(a):
               j *= 2 
       print(a) 
   
   def bigOh4(L):
       # assume L is a 1d list
       N = len(L)
       while (n > 0):
           print(max(L[0:N]))
           n //= 4
   
   def bigOh5(L):
       # assume L is a 1d list
       N = len(L)
       for i in range(N):
           for j in range(i, N):
               if (L[i] > L[j]):
                   (L[i], L[j]) = (L[j], L[i])
   



2. 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()


3. 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) == [5,2]
   getPairSum([10,-1,1,-8,3,1], 2) == [10,-8] (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) == [5, 2]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-1, 3], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum()