CMU 15-112: Fundamentals of Programming and Computer Science
Homework 10 (Due Friday 6-Nov at 8pm ET)

• There is no spicy portion of this hw, so that everyone has plenty of time to enjoy Hack112 this weekend if they so choose.
• Note that the autograder will only test for general correctness, and not for the required big-oh O() runtime.
• You will receive only 10% of the points for general correctness. So if all your functions are generally correct, without regard to big-oh, then the autograder will award you 10 total points.
• The other 90% of the points will be determined when TA's manually grade for big-oh after the submission deadline. To receive any big-oh points, two things must be true:
  1. The function must be otherwise correct (so it must have scored >0 by the autograder).
  2. The function must be in the right O() family (or a faster one, but that's really not necessary).

1. hasAdjacentValues(L) in O(N) [30 pts]
   Write the function hasAdjacentValues(L) that runs in in O(N) time. This function takes a list L of N integers, and returns True if there exists some v in L such that either (v-1) or (v+1), or both, are also in L, and False otherwise. Note that you may not sort L, since that takes O(NlogN) time.
   
   Here are some test cases for you:
   assert(hasAdjacentValues([1,5,8,2]) == True) assert(hasAdjacentValues([1,5,8,0]) == True) assert(hasAdjacentValues([1,5,8,4]) == True) assert(hasAdjacentValues([1,5,8,6]) == True) assert(hasAdjacentValues([1,5,8,3]) == False) assert(hasAdjacentValues([1,5,8,-5]) == False) assert(hasAdjacentValues([ ]) == False) assert(hasAdjacentValues([2,0,-2]) == False) assert(hasAdjacentValues([1,-1,2,0]) == True) assert(hasAdjacentValues([-15,16,19,-21,0]) == False) assert(hasAdjacentValues([-15,16,-16,-21,0]) == True)
   Note that this function must run in O(N) time.


2. hasTriplicate(L) in O(N) [30 pts]
   Write the function hasTriplicate(L) that runs in O(N) time. This function takes a list L with N arbitrary immutable values in it, and returns True if there exists v in L such that (L.count(v) >= 3), and False otherwise. Hint: L.count(v) is O(N), so you can't use it here.
   
   Here are some test cases for you:
   assert(hasTriplicate([ 1, 1, 1 ]) == True) assert(hasTriplicate(list(range(10))*3 ) == True) assert(hasTriplicate([ ]) == False) assert(hasTriplicate(list(range(100))*2) == False) assert(hasTriplicate([ 1, 2, 3 ]) == False) assert(hasTriplicate([ 1, 2, 3, 1 ]) == False) assert(hasTriplicate([1, 5, 1, 1, 2]) == True) assert(hasTriplicate([-3, -2, 1, -2, -2, 3]) == True) assert(hasTriplicate([-3, -2, 1, -2, 2, -3]) == False) assert(hasTriplicate(list(range(-1000, 1000))) == False) assert(hasTriplicate(list(set([1, 5, 1, 1, 2]))) == False) assert(hasTriplicate(list("Axolotls")) == False) assert(hasTriplicate(list("mushroom soup")) == True) assert(hasTriplicate(list("Bumfuzzle Cattywampus Gardyloo")) == True)
   Note that this function must run in O(N) time.


3. boxesAnInteger(L) in O(NlogN) [40 pts]
   Write the function boxesAnInteger(L) that runs in O(NlogN).
   
   Background: Assume L contains N non-negative floats. We will say that L "boxes" an integer (a coined term) if L contains two distinct values u and v, so (u != v), neither of which is equal to an integer, such that there is exactly one integer between u and v.
   
   For example, if L is [ 2.3, 9.4, 1.7 ], the function would return True because between 1.7 and 2.3 there is only one integer (2).
   
   However, if L is [ 2.3, 9.4, 0.7 ], the function would return False because there are two integers between 0.7 and 2.3 (1 and 2) and even more integers between the other pairs of numbers in L.
   
   Also, if L is [ 2.0, 9.4, 0.7 ], the function would return False because (2.0 == 2), so 2.0 cannot be used to box an integer.
   
   With this, write the function boxesAnInteger(L) that takes a list of N non-negative floats and returns True if the list boxes an integer, as just described, and False otherwise.
   
   Hint: You may find math.ceil() or math.floor() useful here.
   
   Here are some test cases for you:
   assert(boxesAnInteger([ 2.3, 9.4, 1.7 ]) == True) assert(boxesAnInteger([ 2.3, 9.4, 0.7 ]) == False) assert(boxesAnInteger([ 2.0, 9.4, 1.7 ]) == False) assert(boxesAnInteger([ ]) == False) assert(boxesAnInteger([ 15.0, 15.0 ]) == False) assert(boxesAnInteger([ 0.0, 2.1, 3.5, 14.8 ]) == True) assert(boxesAnInteger([ 2.1, 0.0, 0.9, 15.2, 13.66 ]) == False)
   Note that this function must run in O(NlogN) time.