-
Code Tracing
See here.
-
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()
-
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()
-
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()
-
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()
-
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()