CMU 15-112: Fundamentals of Programming and Computer Science
Week7 Practice (Due never)

• These problems will help you prepare for hw7 (which is due this Saturday) and for quiz7 (which is after the midterm).
• No starter files this week.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

1. Review Thursday lecture notes
   As a group, review and discuss the notes from Thursday's lecture. In particular, be sure you understand:
   1. What (approximately) 2¹⁰, 2²⁰, and 2³⁰ equal.
   2. What approximately log₂1k, log₂1m, log₂1b equal.
   3. The fact that logn is much, much smaller than n.
   4. Why we ignore lower-order terms and constants in Big-O.
   5. Why we ignore the base in logs in Big-O.
   6. How selectionSort, bubbleSort, and mergeSort work.
   7. The proof that selectionSort is O(n²).
   8. The proof that, for selectionSort (or any quadratic algorithm), when you multiply the input size by c, you multiply the runtime by c².
   9. The proof that mergeSort is O(nlogn).
   10. The fact that, for mergeSort (or any nlogn algorithm), when you multiply the input size by c, you multiply the runtime by a value slightly larger than c but quite a bit smaller than c².
   11. The fact that O(nlogn) is theoretically optimal for any comparison-based sort, and consequently that mergeSort is within a constant time as fast as any possible comparison-based sort.
   12. These class notes on sorting (in detail!) -- just the sorting section. Be sure to really read these notes, including for example watching the videos of the sorting animations.


2. Review xSortLab
   Still as a group, install xSortLab (see link in course notes mentioned above), and run it, and...
   1. Do a visual sort of bubbleSort, and predict each step before confirming it visually.
   2. Do a visual sort of selectionSort, and predict each step before confirming it visually.
   3. Do a visual sort of mergeSort, and predict each step before confirming it visually.
   4. Do a timed sort of selectionSort, and confirm that doubling the input size increases the runtime by about 4x, and that this prediction grows more accurate as the input size increases.
   5. Do a timed sort of mergeSort, and confirm that doubling the input size increases the runtime by more than 2x, but just barely, and well under 4x, and that this prediction grows more accurate as the input size increases.


3. Rewrite (from scratch, ultimately without notes) sorting.py
   Still as a group, rewrite the code from scratch from sorting.py as we covered in class and as written here. You are responsible for all the code in that file, including bubbleSort, selectionSort, mergeSort (and merge), and the timing and testing code. Be sure to study our implementations, and not others online (and be sure not to use recursion!). You need to know this code very well by Tuesday's lecture!


4. 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) 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])


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


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