{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Homework 9"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"INSERT YOUR NAME HERE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Directions:__ Add work to this notebook to solve the problems below.\n",
"\n",
"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.\n",
"\n",
"This assignment will not be collected.\n",
"\n",
"Some problems are derived from problems in these books:\n",
"* __LL__: *Programming for Computations - Python* by Svein Linge and Hans Petter Langtangen, 2nd edition.\n",
"* __L__: *A Primer on Scientific Programming with Python* by Hans Petter Langtangen, 2nd edition.\n",
"* __TAK__: *Applied Scientific Computing With Python* by Peter R. Turner, Thomas Arildsen, and Kathleen Kavanagh."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Standard imports"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import math as m\n",
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Determine the winner"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"data = { 'Donovan': 12.488626865581734,\n",
" 'Dennis': 12.339121151126296,\n",
" 'Akeyla': 16.989828336822182,\n",
" 'Ahad': 14.851156675973165,\n",
" 'Miguel': 10.058766707549275,\n",
" 'Seonin': 15.489321944011124 }\n",
"winner = race_winner(data)\n",
"print(\"{} won the race!\".format(winner))\n",
"assert winner == 'Miguel', \"You have the wrong winner.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Printing a polynomial"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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.\n",
"\n",
"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`.\n",
"\n",
"You have a lot of flexibility with how you print your answer. In the test below I define `p` by:\n",
"```python\n",
"p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3\n",
"s = polynomial_string(p)\n",
"```\n",
"Any of the following strings are acceptable returns by `polynomial_string(data)`:\n",
"* `'1*x**3-2*x**2-3'`\n",
"* `'-3*x**0 - 2*x**2 + x**3'`\n",
"* `'-3 + x**2 * (x-2)'`\n",
"\n",
"The test below makes use of the [`eval` function](https://docs.python.org/3/library/functions.html#eval)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The dictionary mapping $0$ to $-6$ represents the constant polynomial $-6$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = {0: -6}\n",
"s = polynomial_string(p)\n",
"print(f\"The polynomial is '{s}'.\")\n",
"assert -6 == eval(s), 'There is an error in your code.'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Below we test the polynomial $x^3 - 2x^2 - 3$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3\n",
"s = polynomial_string(p)\n",
"print(f\"The polynomial is '{s}'.\")\n",
"x = 0\n",
"assert eval(s) == -3, \"The polynomial should evaluate to -3 when x=0.\"\n",
"x = 1\n",
"assert eval(s) == -4, \"The polynomial should evaluate to -4 when x=1.\"\n",
"x = -5\n",
"assert eval(s) == -178, \"The polynomial should evaluate to -178 when x=-5.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Derivatives of polynomials"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following test also makes use of the `polynomial_string` function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = {0:3, 2:1} # x^2 + 3\n",
"der = polynomial_derivative(p)\n",
"assert polynomial_derivative(p)=={1:2}, \"The derivative should be 2*x.\"\n",
"print(\"The derivative of {} is {}.\".format(polynomial_string(p),\n",
" polynomial_string(der)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Polynomial products"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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. \n",
"\n",
"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\n",
"`{2:1}=={0:0, 2:1}` will return `False`.)\n",
"\n",
"You can assume that `f` and `g` have nonzero coefficients."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"f = {1:1,0:1} # f(x)=x+1\n",
"g = {1:1,0:-1} # g(x)=x-1\n",
"h = polynomial_product(f, g)\n",
"print(\"The product of {} and {} is {}.\".format(polynomial_string(f),\n",
" polynomial_string(g),\n",
" polynomial_string(h)))\n",
"assert h == {2:1, 0:-1}, \"The product is wrong or has a zero coefficient.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Quadrature rules"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recall that a quadrature formula has the form\n",
"$$Q(f) = \\sum_{k=0}^N c_k f(x_k).$$\n",
"Here $f$ should be a function whose domain includes the points $x_k$ and each $c_k$ is a number. \n",
"\n",
"The quadrature rule $Q$ is determined by the mapping $x_k \\mapsto c_k$ which we can interpret as a dictionary.\n",
"\n",
"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 \n",
"$$\\sum_{k=0}^N c_k f(x_k).$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"# Simpson's rule for [0, 1]\n",
"q = {0: 1/6, 0.5: 4/6, 1: 1/6}\n",
"# The function x -> x^2\n",
"f = lambda x: x**2 \n",
"# this quadrature rule should be exact:\n",
"assert abs(quadrature_evaluation(q, f)-1/3) < 10**-15, \\\n",
" \"incorrect result returned. The answer should be 1/3.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. Transforming quadrature rules"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Near the bottom of the [Numerical Integration notebook](http://wphooper.com/teaching/2020-fall-computation/nb/Numerical%20Integration.html) (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]$. \n",
"\n",
"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