CMU 15-112 Fall 2015 Quiz 4 Practice
(Due never)

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

1. Code Tracing
2. areaOfPolygon(L)
3. evalPolynomial(coeffs, x)
4. multiplyPolynomials(p1, p2)
5. repeatingPattern(L)
6. isNearlySorted(L)

1. Code Tracing
   See here.


2. areaOfPolygon(L)
   Write the function areaOfPolygon(L) that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5).
   def areaOfPolygon(L): return 42 # place your answer here! def almostEqual(d1, d2): epsilon = 10**-8 return abs(d1 - d2) < epsilon def testAreaOfPolygon(): print("Testing areaOfPolygon()...", end="") assert(almostEqual(areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]), 45.5)) assert(almostEqual(areaOfPolygon([(9,7), (11,2), (2,2), (4, 10)]), 45.5)) assert(almostEqual(areaOfPolygon([(0, 0), (0.5,1), (1,0)]), 0.5)) assert(almostEqual(areaOfPolygon([(0, 10), (0.5,11), (1,10)]), 0.5)) assert(almostEqual(areaOfPolygon([(-0.5, 10), (0,-11), (0.5,10)]), 10.5)) print("Passed!") testAreaOfPolygon()


3. evalPolynomial(coeffs, x)
   Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x³ + 3x² + 4. With this in mind, write the function evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value. For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*4³ + 3*4² + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).
   def evalPolynomial(coeffs, x): return 42 # place your answer here! def testEvalPolynomial(): print("Testing evalPolynomial()...", end="") # f(x) = 2x^3 + 3x^2 + 4, f(4) = 180 assert(evalPolynomial([2,3,0,4], 4) == 180) # f(x) = 6, f(42) = 6 assert(evalPolynomial([6], 42) == 6) # f(x) = 6x^2 -2x - 20, f(-1) = -12 assert(evalPolynomial([6,-2,-20], -1) == -12) # f(x) = 6x^5-8x^3-8x, f(2) = 112, f(1) = -10, f(0) = 0 assert(evalPolynomial([6,0,-8,0,-8,0], 2) == 112) assert(evalPolynomial([6,0,-8,0,-8,0], 1) == -10) assert(evalPolynomial([6,0,-8,0,-8,0], 0) == 0) print("Passed!") testEvalPolynomial()


4. multiplyPolynomials(p1, p2)
   Write the function multiplyPolynomials(p1, p2) which takes two polynomials as defined in the previous problem and returns a third polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x² + 3)(4x + 5), and:
       (2x² + 3)(4x + 5) = 8x³ + 10x² + 12x + 15
   And so this returns [8, 10, 12, 15].
   def multiplyPolynomials(p1, p2): return 42 # place your answer here! def testMultiplyPolynomials(): print("Testing multiplyPolynomials()...", end="") # (2)*(3) == 6 assert(multiplyPolynomials([2], [3]) == [6]) # (2x-4)*(3x+5) == 6x^2 -2x - 20 assert(multiplyPolynomials([2,-4],[3,5]) == [6,-2,-20]) # (2x^2-4)*(3x^3+2x) == (6x^5-8x^3-8x) assert(multiplyPolynomials([2,0,-4],[3,0,2,0]) == [6,0,-8,0,-8,0]) print("Passed!") testMultiplyPolynomials()


5. repeatingPattern(L)
   Write the function repeatingPattern(L) that takes a list L and returns a tuple of (pattern, repeat), where pattern is a list and repeat is an integer >= 2, where the list L is composed of "repeat" consecutive instances of pattern. Return None if no such pattern exists. For example, repeatingPattern([1,2,3,1,2,3]) returns ([1,2,3], 2).
   def repeatingPattern(L): return 42 # place your answer here! def testRepeatingPattern(): print("Testing repeatingPattern()...", end="") assert(repeatingPattern([]) == None) assert(repeatingPattern([42]) == None) assert(repeatingPattern([1,2]) == None) assert(repeatingPattern([1,1]) == ([1], 2)) assert(repeatingPattern([1,2,1]) == None) assert(repeatingPattern([1,2,3,1,2,3]) == ([1,2,3], 2)) assert(repeatingPattern([1,2,3,1,2]) == None) assert(repeatingPattern([1,2,3,1,2,3,1]) == None) L = list(range(10)) assert(repeatingPattern(L*20) == (L, 20)) print("Passed!") testRepeatingPattern()


6. isNearlySorted(L)
   Write the function isNearlySorted(L) that takes a possibly-empty list L and returns True if the list is "nearly sorted", and False otherwise, where a "nearly sorted" list is one which is not sorted and requires exactly one swap of two elements to become sorted.
   def isNearlySorted(L): return False # place your answer here! def testIsNearlySorted(): print("Testing isNearlySorted()...", end="") assert(isNearlySorted([0,1,2,3]) == False) assert(isNearlySorted([]) == False) assert(isNearlySorted([42]) == False) assert(isNearlySorted([3,2]) == True) assert(isNearlySorted([2,2]) == False) assert(isNearlySorted([5,2,3,4,1,6]) == True) assert(isNearlySorted([1,2,3,5,4]) == True) print("Passed!") testIsNearlySorted()