# 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
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 2x3 + 3x2 + 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*43 + 3*42 + 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 (2x2 + 3)(4x + 5), and:
(2x2 + 3)(4x + 5) = 8x3 + 10x2 + 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()