CMU 15-112: Fundamentals of Programming and Computer Science
Week 4: Efficiency

To start:
1. In the folder named 'Week4'
2. Download 10. efficiencyPractice.py
3. Edit the downloaded file using your preferred editor
Do not use recursion in the solutions.

Big O Analysis

Code #1:
def bigO1(L): # L is a list of length N count = 0 # O(_) for i in range(len(L)): # loops _ times count += L[i] # O(_) return count # O(_) # Overall - O(_)

Code #2:
def bigO2(L): # L is a list of length N i = 1 # O(_) listLength = len(L) # O(_) result = [] # O(_) while i < listLength: # loops _ times result += L[i] # O(_) i *= 3 # O(_) return result # O(_) # Overall - O(_)

Code #3:
def bigO3(L): # L is a list of length N result = 0 # O(_) for elem in L: # loops _ times result += L.count(elem) # O(_) return result # O(_) # Overall - O(_)

Code #4:
def bigO4(a): # a is a list of length N for i in range(len(a)): # loops _ times j = 1 # O(_) while j < len(a): # loops _ times j *= 2 # O(_) return a # O(_) # Overall - O(_)

Code #5:
def bigO5(n):#n is an int, N= n #Big-O ret = [] #______ for i in range(n): #______ for j in range(i+1,n): #______ ret.append(i+j) #______ return ret #______

Code #6:
def bigO6(L): #L contains N items # Big-O allowedWords =["surround", "friend", "stop"] #______ newList = [] #______ for w in L: #______ if w in allowedWords: #______ newList.append(w) #______ for w in allowedWords: #______ if w in L: #______ L.remove(w) #______ L.sort() #______ L.extend(newList) #______ return L #______

Code #7:
def bigO7(L, z): n = len(L) a = max(L) for x in range(n): a += x return a Big-O: ______________ Explanation: _____________

Code #7:
def bigO7(L, z): n = len(L) a = max(L) for x in range(n): a += x return a Big-O: ______________ Explanation: _____________

Code #8:
def bigO8(L, z): a = max(len(L)-1, z) L[0] += L[a] return max(L[a],z) Big-O: ______________ Explanation: _____________

Code #9:
def bigO9(L, z): n = len(L) x = 0 y = 0 while (x < n): while (y < n): y += 1 z += y x += 1 z += x return z Big-O: ______________ Explanation: _____________

Code #10:
def bigO10(L,z): for i in range(len(L)): if L[i] == sorted(L)[z]: return i return False Big-O: ______________ Explanation: _____________

Free Response

Short Answer
Consider the following code:
```
     def f(a):
      t = 0
      for e in a:
        for t in a:
          t = t + 1
      return t
    
```
Big-O time efficiency of the function if:
1. a is a list. _________________________________
2. a is a set. _________________________________
3. a is a dict. _________________________________
4. a is a 5-letter English word (string). _____________________

cheapestProducts(priceList) (Efficient)
Write the function cheapestProducts(priceList) which, given a list of tuples each containing the product name, store name, and price of a product, returns a dictionary mapping product names to a tuple containing the store and price for the lowest price found for the item. In the event of a tie, either store may be used. Consider the following example. If
```
          productList = [ ("X-Box", "LuLu", 1200), ("iPhone XR", "Carrefour", 3000), ("Washer", "SafariMart" , 799), ("iPhone XR", "Al Anees" , 2870), ("Washer", "LuLu", 899) ]
          cheapestProducts(priceList)
      
```
returns a dictionary containing... {'X-Box': (1200, 'LuLu'), 'iPhone XR': (2870, 'Al Anees'), 'Washer': (799, 'SafariMart')} Your solution must run in O(N) time, where N = len(productList).

findFlukeNumbers(L)(Efficient)
A fluke number (coined term) is an integer that has a frequency in the list equal to its value. Write the function findFlukeNumbers(L)) that is given a list L of objects (not necessarily integers). The function should return a set containing all the fluke numbers in the list. Your solution should run in O(N) time. For example,
```
      assert(findFlukeNumbers([1,'a','a',[4], 3, False, 3, 3]) == {1, 3})
      assert(findFlukeNumbers([1, 2, 2, 3, 3, 3, 4]) == {1, 2, 3})
      assert(findFlukeNumbers([0, False, 'hello']) == set())
  
```

Improve the Efficiency! : I
The following function returns the number of elements in L that also have their square in L.
```
      def countSquares(L):
        count = 0
        for item in L:
          square = item**2
          if item !=square and square in L:
            count += 1
        return count
    
```
1. What is the Big-O efficiency of this function?
2. The function is less efficient than it could be. Briefly describe how to change the function to make it more efficient without completely changing the algorithm. Your answer must change the function family of the program’s runtime. Also state the Big-O efficiency the function with your changes.

Improve the Efficiency : II
Given the function f(L) below which takes a list L containing N integers, write the function g(L) such that:

g(L) works identically to f(L) for any list L with N integers.
g(L) runs in O(N) time.

      def f(L):
        if L == [ ]:
          return None
        M = [ ]
        for v in L:
          if v not in M:
            M.append(v)
        N = sorted([L.count(v) for v in M])
        return N[-1]

getPairSum(a, target)
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). (Or just do the O(n) one)

mostCommonName (L)
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). (Or just do the O(n) one)

sameXandY(L)
Write the function sameXandY(L) that takes a list L that contains n (x, y) tuples, and returns True if every x value occurs as some y value and every y value also occurs as some x value, and False otherwise. If the list is empty, return False. Note: To receive full credit, your function must run in O(n) where n is the length of L. For example: assert(sameXandY([(1,2),(2,3),(3,2),(1,1)]) == True) Here, the x values are 1, 2, 3, 1, and the y values are 2, 3, 2, 1. This meets the requirement, so the function returns True. As another example: assert(sameXandY([(1,2),(2,3),(3,2),(4,1)]) == False) Here, the x values are 1, 2, 3, 4, and the y values are 2, 3, 2, 1. Since the x value 4 does not occur as a y value, the function returns False.
```
      def testSameXandY():
        assert(sameXandY([ ]) == False)
        assert(sameXandY([(1,2)]) == False)
        assert(sameXandY([(2,2)]) == True)
        assert(sameXandY([(1,2),(2,1)]) == True)
        assert(sameXandY([(1,2),(2,3)]) == False)
        assert(sameXandY([(1,2),(2,3),(3,2),(1,1)]) == True)
        assert(sameXandY([(1,2),(2,3),(3,2),(4,1)]) == False)
    
```

getZeroPair(L)
Write the function getZeroPair(L) which takes a list L of integers, and returns a set of two different integers in L that sum to zero. If no such pair exists, the function returns None. If there is more than one valid pair, you can return any of them. For example, getZeroPair([1, 2, 3, 10, -3]) should return the set {-3, 3} since these sum to 0. getZeroPair([1, 2, 3, 10]) should return None since there is no pair of numbers in [1, 2, 3, 10] that sums to 0. Your solution must run in no worse than O(N) time, where N is the length of L.
```
        def testGetZeroPair():
          assert(getZeroPair([1, 2, 3, 10, -3]) == {-3, 3})
          assert(getZeroPair([1, 2, 3, 10]) == None)
          assert(getZeroPair([-1, 2, 3, 0, 1]) == {-1, 1})
          assert(getZeroPair([-1, 2, -3, 0, -2]) == {-2, 2})
          assert(getZeroPair([0, 1, 2, 3, 0]) == None) #Integers must be different
          assert(getZeroPair([]) == None)
      
```

CMU 15-112: Fundamentals of Programming and Computer Science Week 4: Efficiency

CMU 15-112: Fundamentals of Programming and Computer Science
Week 4: Efficiency