{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Midterm 1 Review\n", "\n", "Complete the following questions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Standard imports" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import math as m\n", "from mpmath import mp, iv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1. Working with lists.\n", "\n", "Write a function odd_sublist(lst) which takes as input a list lst of integers and returns a list containing only the odd integers, in the same order." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests: Should not produce errors\n", "assert odd_sublist([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) == [1, 3, 5, 7, 9]\n", "assert odd_sublist([1, 1, 2, 3, 5, 8, 13, 21]) == [1, 1, 3, 5, 13, 21]\n", "assert odd_sublist([101, 1001, 10001]) == [101, 1001, 10001]\n", "assert odd_sublist([2, 4, 8, 16, 32, 64]) == []" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2. Volume of a cylinder\n", "\n", "Write a function cylinder_volume(r, h) which returns the volume of a cylinder of radius $r>0$ and height $h>0$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests that should be passed\n", "assert abs(cylinder_volume(1, 1) - 3.141592653589793) < 10**-8\n", "assert abs(cylinder_volume(0.5641895835477563, 5) - 5) < 10**-8\n", "assert abs(cylinder_volume(10, 2) - 628.3185307179587) < 10**-8\n", "assert abs(cylinder_volume(10, 10) - 3141.5926535897934) < 10**-8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3. Function plotting\n", "\n", "Use matplotlib to plot the function $sin(\\frac{1}{x})$ using $10001$ values of $x$ equally spaced in the interval $[0.00001, 1.00001]$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Check your work:** Your plot should look something like this:\n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4. Counting the elements in a list.\n", "\n", "Write a function count_small_elements(lst, epsilon) which takes as input a list lst of real numbers and an $\\epsilon>0$, and returns the number of real numbers $x$ in lst such that $|x|<\\epsilon$. \n", "\n", "For example count_small_elements([0.1, 0.5, 1.1, 2], 1) should return $2$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests:\n", "assert count_small_elements([0.1, 0.5, 1.1, 2], 1) == 2\n", "assert count_small_elements(list(range(100)), 50) == 50\n", "assert count_small_elements([x/4 for x in range(-100,101)], 3.7) == 29" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5. Evaluating a series\n", "\n", "Consider the series $$\\sum_{k=0}^\\infty \\frac{1}{1+\\sqrt{k}}.$$\n", "Let $S_N$ be the partial sum consisting of the sum of the first $N$ terms. \n", "Compute the smallest $N$ such that \n", "$$|S_N - S_{N-1}| < \\frac{1}{30 \\pi}.$$\n", "Store the value of $N$ in the variable N_stop and store the value of $S_N$ in the variable partial_sum_stop." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "assert N_stop == 8696, \"N_stop is wrong.\"\n", "assert (partial_sum_stop - 178.06448) < 10**-3, \"partial_sum_stop is wrong.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 6. Working with different bases\n", "\n", "Write a function base7(n) which takes as input an integer $n > 0$ and converts it to a string storing its representation in base $7$. The returned string will consist only of the characters in the set $\\{0,1,2,3,4,5,6\\}$.\n", "\n", "For example, the number $67$ in base $7$ is is given by 124 since\n", "$$67 = 1 \\cdot 7^2 + 2 \\cdot 7 + 4.$$\n", "Thus base7(67) should return the string '124'." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests\n", "assert base7(6) == '6', 'Failed for n = 6.'\n", "assert base7(49) == '100', 'Failed for n = 49.'\n", "assert base7(67) == '124', 'Failed for n = 67.'\n", "assert base7(151235) == '1166630', 'Failed for n = 151235.'\n", "assert base7(6723477342423466) == '4062124131215314042', 'Failed for n = 6723477342423466.'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 7. Rigorous comparisons\n", "\n", "Write a function root_difference_less_than(n, p, q) which takes as input integers $n$, $p$, and $q$ and returns True if \n", "$$\\sqrt{n} - \\sqrt{n} < \\frac{p}{q}.$$\n", "The function should return False if the inequality is not true. You can assume that $q \\neq 0$ and that the quantity $\\sqrt{n} - \\sqrt{n}$ is irrational (i.e., that it can not be true that $\\sqrt{n} - \\sqrt{n}=\\frac{p}{q}$.)\n", "\n", "Use interval arithmetic at increasing precision to be sure that your answer is always correct, even if the integers involved are very large.\n", "\n", "For example root_difference_less_than(27, 2, 1) should return False since $\\sqrt{27} \\in (5,6)$ while $\\sqrt{27}=3$. Thus $\\sqrt{n} - \\sqrt{n}$ lies in the interval $(2,3)$, and we are comparing to the fraction $2/1$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests\n", "assert not root_difference_less_than(27, 2, 1)\n", "assert root_difference_less_than(27, 9, 4)\n", "assert not root_difference_less_than(2, 39167, 253849)\n", "assert not root_difference_less_than(3, 266312747, 918949655)\n", "assert not root_difference_less_than(5, 3503460365364981558547916427985849, \n", " 6659405883574539501104899156429155)\n", "assert not root_difference_less_than(6, \n", " 12937268231607778583821492269711419883137751358, \n", " 20458411408288108829612787097012200189720135111)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 8. Significant digits\n", "\n", "Find the value of $\\frac{22}{7} - \\pi$ to $20$ significant digits. Store the answer as a string in the variable pi_approx_difference. Do not use exponential notation.\n", "\n", "Your answer should differ be within one least significant digit from the true value. Note the true value has the form $0.00126\\ldots$, so differing by one least significant digit means that abs(\\frac{22}{7} - pi - pi_approx_difference) should be less than $10^{-22}$.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests:\n", "# The correct answer is '0.0012644892673496186802' but nearby answers are acceptable:\n", "assert '0.0012644892673496186802' == pi_approx_difference or \\\n", " '0.0012644892673496186801' == pi_approx_difference or \\\n", " '0.0012644892673496186803' == pi_approx_difference" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 9. ArcTan\n", "\n", "Inverse tangent is an analytic function. It's Taylor series centered at the origin is given by $$\\tan^{-1}(x) = x - \\frac{x^3}{3} + \\frac{x^5}{5} - \\frac{x^7}{7} +\\ldots.$$\n", "This series converges for values of $x \\in [-1,1]$.\n", "\n", "Write a function arctan_partial_sum(x, d) which takes as input a float $x \\in [-1,1]$ and an integer $d$ and returns the Taylor polynomial of degree $d$ evaluated at $x$. Use Python's built in floats to carry out the calculation." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "assert abs(arctan_partial_sum(0.5, 0)) < 10**-8, \"Error with input (0.5, 0).\"\n", "assert abs(arctan_partial_sum(0.3,1)-0.3) < 10**-8, \"Error with input (0.3,1).\"\n", "assert abs(arctan_partial_sum(0.7,2)-0.7) < 10**-8, \"Error with input (0.7,2).\"\n", "assert abs(arctan_partial_sum(0.5,10)-0.46368427579365) < 10**-8, \\\n", " \"Error with input (0.5,10).\"\n", "assert abs(arctan_partial_sum(1,100) - 0.7803986631477527) < 10**-8, \\\n", " \"Error with input (1,100).\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 10. ArcTan, continued\n", "\n", "The usual form for the remainder in the Taylor series is not immediately useful, since it requires us to control high order derivatives of $\\tan^{-1}$. \n", "\n", "However, observe that the degree $d$ term of the Taylor series for $\\tan^{-1}$ has absolute value less than $|x|^d$. Thus the remainder $R_d(x)-\\tan^{-1}(x)$ satisfies\n", "$$-\\sum_{k=d+1}^\\infty |x|^k < R_d(x) < \\sum_{k=d+1}^\\infty |x|^k.$$\n", "Observe that $\\sum_{k=d+1}^\\infty |x|^k$ is a geometric series and can be evaluated by a standard formula.\n", "\n", "Write a function arc_tan_degree(x, epsilon) which takes as input an $x \\in (-1,1)$ and an $\\epsilon>0$ and returns an integer $d$ such that $|R_d(x)|<\\epsilon$.\n", "\n", "Use your function to compute $\\tan^{-1}(\\frac{1}{2})$ correct to $8$-significant digits. Store the result as a float in the variable arc_tan_half.\n", "\n", "You can use floats and ignore the effects of round off error.\n", "\n", "**Remark:** This problem would be too hard and time consuming for a test, but it is still good practice." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Tests\n", "assert abs(arc_tan_half - m.atan(0.5)) < 10**-8\n", "assert arc_tan_degree(0.25, 100) == 0\n", "assert abs(arctan_partial_sum(0.25, arc_tan_degree(0.25, 0.5*10**-4)) - m.atan(0.25)) < 10**-4\n", "assert abs(arctan_partial_sum(0.75, arc_tan_degree(0.75, 0.5*10**-6)) - m.atan(0.75)) < 10**-6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 11. Fibonacci numbers\n", "\n", "The Fibonacci numbers are defined inductively by \n", "$F_0=1$, $F_1=1$ and \n", "$$F_{n+1}=F_n + F_{n-1} \\quad \\text{for all n \\geq 1.}$$\n", "\n", "Write a function fibonacci(n) which computes the number $F_n$ for integers $n \\geq 0$.\n", "\n", "The first few values are printed below:\n", "$$F_0 = 1,~F_1 = 1,~F_2 = 2,~F_3 = 3,~F_4 = 5,~F_5 = 8,~F_6 = 13,~F_7 = 21,~F_8 = 34,~F_9 = 55.$$ " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests\n", "assert fibonacci(0) == 1\n", "assert fibonacci(1) == 1\n", "assert fibonacci(2) == 2\n", "assert fibonacci(3) == 3\n", "assert fibonacci(4) == 5\n", "assert fibonacci(5) == 8\n", "assert fibonacci(6) == 13\n", "assert fibonacci(7) == 21\n", "assert fibonacci(8) == 34\n", "assert fibonacci(9) == 55\n", "assert fibonacci(10) == 89\n", "assert fibonacci(11) == 144\n", "assert fibonacci(12) == 233\n", "assert fibonacci(13) == 377\n", "assert fibonacci(14) == 610\n", "assert fibonacci(15) == 987\n", "assert fibonacci(16) == 1597\n", "assert fibonacci(17) == 2584\n", "assert fibonacci(18) == 4181\n", "assert fibonacci(19) == 6765\n", "assert fibonacci(20) == 10946\n", "assert fibonacci(21) == 17711\n", "assert fibonacci(22) == 28657\n", "assert fibonacci(23) == 46368\n", "assert fibonacci(24) == 75025\n", "assert fibonacci(25) == 121393\n", "assert fibonacci(26) == 196418\n", "assert fibonacci(27) == 317811\n", "assert fibonacci(28) == 514229\n", "assert fibonacci(29) == 832040" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 12. Inductive Proof\n", "\n", "Inductively prove that if $n \\geq 7$, then $F_n > 1.5^n$.\n", "\n", "*Hint:* Show by computation that $F_7 > 1.5^7$ and $F_8 > 1.5^8$. Argue that if $F_n > 1.5^n$ and $F_{n-1} > 1.5^{n-1}$, then $F_{n+1} > 1.5^{n+1}$ using the fact that $F_{n+1}=F_n+F_{n-1}$. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 13. Series involving Fibonacci numbers\n", "\n", "Consider the series \n", "$$X = \\sum_{n=0}^\\infty \\frac{1}{F_n}$$\n", "where $F_n$ is the $n$th Fibonacci number. Let $S_N$ be the partial sum consisting of the first $N$ terms. Write a function fibonacci_partial_sum(N) which returns $S_N$. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests\n", "assert abs(fibonacci_partial_sum(1) - 1.0) < 10**-8\n", "assert abs(fibonacci_partial_sum(2) - 2.0) < 10**-8\n", "assert abs(fibonacci_partial_sum(3) - 2.5) < 10**-8\n", "assert abs(fibonacci_partial_sum(4) - 2.8333333333333335) < 10**-8\n", "assert abs(fibonacci_partial_sum(5) - 3.0333333333333337) < 10**-8\n", "assert abs(fibonacci_partial_sum(6) - 3.1583333333333337) < 10**-8\n", "assert abs(fibonacci_partial_sum(7) - 3.2352564102564108) < 10**-8\n", "assert abs(fibonacci_partial_sum(8) - 3.282875457875458) < 10**-8\n", "assert abs(fibonacci_partial_sum(9) - 3.3122872225813405) < 10**-8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 14. Approximation of series.\n", "\n", "Use the fact that $F_n > 1.5^n$ for $n \\geq 7$ to compute an upper bound on the remainder $R_N = X - S_N$ for value of $N \\geq 7$.\n", "\n", "Note that all terms are positive, so $R_N>0$. \n", "\n", "Use what you learned to write a function series_approx(epsilon) which takes as input an $\\epsilon>0$ and returns a real number $Y$ such that $|X-Y|<\\epsilon$ where $X=\\sum_{n=0}^\\infty \\frac{1}{F_n}$.\n", "\n", "*Hint:* If you know $R_N < 2 \\epsilon$, then $S_N+\\epsilon$ is within $\\epsilon$ of the limit $X$ (i.e., $|X - (S_N+\\epsilon)|<\\epsilon$.)\n", "\n", "You can use floating point arithmetic and ignore the effects of round of error.\n", "\n", "Use your function to compute the value of $X$ to $8$ significant digits. Store the result as a float in the variable X_approx. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## TESTS:\n", "assert abs(X_approx - 3.3598857) < 1.1*10**-7\n", "assert abs(series_bound(0.5*10**-12) - 3.359885666243673) < 1.1*10**-12" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.9" } }, "nbformat": 4, "nbformat_minor": 2 }