# Homework 9¶

Directions: Add work to this notebook to solve the problems below.

Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.

This assignment will not be collected.

Some problems are derived from problems in these books:

• LL: Programming for Computations - Python by Svein Linge and Hans Petter Langtangen, 2nd edition.
• L: A Primer on Scientific Programming with Python by Hans Petter Langtangen, 2nd edition.
• TAK: Applied Scientific Computing With Python by Peter R. Turner, Thomas Arildsen, and Kathleen Kavanagh.

### Standard imports¶

In [ ]:
import math as m
import numpy as np


## 1. Determine the winner¶

The organizers of a races use a dictionary mapping names to times (positive real numbers). Write a function race_winner(times) which takes as input a dictionary times which maps names to times and returns the name of the winner. The winner is the person with the lowest time.

In [ ]:



In [ ]:
# Test
data = { 'Donovan': 12.488626865581734,
'Dennis': 12.339121151126296,
'Akeyla': 16.989828336822182,
'Miguel': 10.058766707549275,
'Seonin': 15.489321944011124 }
winner = race_winner(data)
print("{} won the race!".format(winner))
assert winner == 'Miguel', "You have the wrong winner."


## 2. Printing a polynomial¶

Example 6.2.3 on page 280 of L discusses the example of using a dictionary to store the non-zero coefficients of a polynomial. The dictionary representing a polynomial maps the degree $d$ of a term $c_d x^d$ to the coefficient of the term $c_d$. Read this example for more information.

Write a function polynomial_string(data) which takes as input a dictionary data representing a polynomial and returns a string representing that polynomial. The string should be such that if the string is evaluated by python it would return the polynomial evaluated at x.

You have a lot of flexibility with how you print your answer. In the test below I define p by:

p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3
s = polynomial_string(p)


Any of the following strings are acceptable returns by polynomial_string(data):

• '1*x**3-2*x**2-3'
• '-3*x**0 - 2*x**2 + x**3'
• '-3 + x**2 * (x-2)'

The test below makes use of the eval function.

In [ ]:



The dictionary mapping $0$ to $-6$ represents the constant polynomial $-6$.

In [ ]:
p = {0: -6}
s = polynomial_string(p)
print(f"The polynomial is '{s}'.")
assert -6 == eval(s), 'There is an error in your code.'


Below we test the polynomial $x^3 - 2x^2 - 3$.

In [ ]:
p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3
s = polynomial_string(p)
print(f"The polynomial is '{s}'.")
x = 0
assert eval(s) == -3, "The polynomial should evaluate to -3 when x=0."
x = 1
assert eval(s) == -4, "The polynomial should evaluate to -4 when x=1."
x = -5
assert eval(s) == -178, "The polynomial should evaluate to -178 when x=-5."


## 3. Derivatives of polynomials¶

Write a function polynomial_derivative(data) which takes as input a dictionary data representing a polynomial and returns a dictionary representing the derivative of the polynomial.

In [ ]:



The following test also makes use of the polynomial_string function.

In [ ]:
p = {0:3, 2:1} # x^2 + 3
der = polynomial_derivative(p)
assert polynomial_derivative(p)=={1:2}, "The derivative should be 2*x."
print("The derivative of {} is {}.".format(polynomial_string(p),
polynomial_string(der)))


## 4. Polynomial products¶

Write a function polynomial_product(f,g) which takes as input two dictionaries f and g representing polynomials and returns a dictionary representing the product of the two polynomials.

Be sure that there are no degrees in the returned dictionary which map to a coefficient of zero. (The reason to worry about this has to do with uniqueness of a polynomial representation. For example, the dictionaries {2:1} and {0:0, 2:1} both represent $x^2$ but {2:1}=={0:0, 2:1} will return False.)

You can assume that f and g have nonzero coefficients.

In [ ]:



In [ ]:
# Test
f = {1:1,0:1} # f(x)=x+1
g = {1:1,0:-1} # g(x)=x-1
h = polynomial_product(f, g)
print("The product of {} and {} is {}.".format(polynomial_string(f),
polynomial_string(g),
polynomial_string(h)))
assert h == {2:1, 0:-1}, "The product is wrong or has a zero coefficient."


Recall that a quadrature formula has the form $$Q(f) = \sum_{k=0}^N c_k f(x_k).$$ Here $f$ should be a function whose domain includes the points $x_k$ and each $c_k$ is a number.

The quadrature rule $Q$ is determined by the mapping $x_k \mapsto c_k$ which we can interpret as a dictionary.

Write a funtion quadrature_evaluation(q, f) which takes as input a dictionary q mapping points $x_k$ to the corresponding coefficient $c_k$ and a function f and returns the quantity $$\sum_{k=0}^N c_k f(x_k).$$

In [ ]:



In [ ]:
# Test
# Simpson's rule for [0, 1]
q = {0: 1/6, 0.5: 4/6, 1: 1/6}
# The function x -> x^2
f = lambda x: x**2
# this quadrature rule should be exact:
assert abs(quadrature_evaluation(q, f)-1/3) < 10**-15, \
"incorrect result returned. The answer should be 1/3."


Near the bottom of the Numerical Integration notebook (under the heading Change of coordinates formula for quadrature rules) a formula is given for transforming a quadrature rule $A$ approximating integrals over the interval $[-1, 1]$ into a quadrature rule $B$ approximating integrals over the interval $[c,d]$.

Write a function transformed(A, c, d) which takes as input a dictionary A representing a quadrature rule and floats c and d with $c<d$ and returns a dictionary representing the transformed quadrature rule $B$.

In [ ]:



In [ ]:
# Testing on the example in the Numerican Integration notebook
A = {-m.sqrt(3)/m.sqrt(5) : 5/9,
0 : 8/9,
m.sqrt(3)/m.sqrt(5) : 5/9 }
B = transformed(A, 0, m.pi)
key0, key1, key2 = sorted(B.keys())
assert abs(key0 - 0.35406272400281313) < 10**-8, \
'The point x_0 is wrong.'
assert abs(B[key0] - 0.8726646259971648) < 10**-8, \
'The coefficient c_0 is wrong.'
assert abs(key1 - 1.5707963267948966) < 10**-8, \
'The point x_1 is wrong.'
assert abs(B[key1] - 1.3962634015954636) < 10**-8, \
'The coefficient c_1 is wrong.'
assert abs(key2 - 2.78752992958698) < 10**-8, \
'The point x_2 is wrong.'
assert abs(B[key2] - 0.8726646259971648) < 10**-8, \
'The coefficient c_2 is wrong.'