CMU 15-112 Fall 2015 Quiz6 Practice
(Due never)

• Edit how you wish (add imports, helper functions, etc), except:
  • Do not use recursion, lambdas, or non-local variables this week.
  • Do not edit the test code.
  • Do not hardcode the test cases in your solutions.
• Quiz6 will include a subset of the problems here.

1. Code Tracing
2. The Worked Examples Using 2d Lists
1. Word Search
2. Word Search Redux
3. Connect4
4. Othello
3. mostCommonName(L) in O(n) time
4. getPairSum(a, target) in O(n) time

1. Code Tracing
   See here.


2. The Worked Examples Using 2d Lists
   This week's quiz may include any of the worked examples from last week's worked examples. Specifically:
   1. Word Search
   2. Word Search Redux
   3. Connect4
   4. Othello


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


4. 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. This can be done in O(n) time. 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()