{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Course 3 (and assignment)\n",
"=========================\n",
"\n",
"Name: XXX FILL YOUR NAME HERE XXX\n",
"\n",
"Some comments about the assignment\n",
"- This work is made for you: it is a revision of all previous worksheets. Moreover, the content of the following courses will be adapted depending on the results. For these reasons, the assignment must be personal.\n",
"- Each exercise should be solved using the cells below it. If needed you can add more cells with the menu \"Insert -> Insert Cell Above\" and \"Insert -> Insert Cell Below\".\n",
"- Your code should be clear and execute cleanly from top to bottom (you can check with the menu \"Kernel -> Restart & Run All\")\n",
"- It is better to split your code into several cells rather than having a big cell with a lot of code\n",
"- Do not modify the statements of the exercises. If you want to add comments to your answers, either use Python comment (with `#`) or create new cell of Markdown type.\n",
"- Each function you program should come with examples."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Functions\n",
"=========\n",
"In the previous worksheets you have already used a lot of Python functions like `print`, `len`, `math.cos`, `numpy.arange` or `matplotlib.pyplot.plot` (do you have others in mind?). Functions are useful because they allow you to write code that you can reuse at several places in a computation. In this worksheet we will learn how to write them.\n",
"\n",
"We present the syntax by writing a function which takes in argument two numbers `x` and `y` and returns the value of `cos(x) + sin(y)`.\n",
"```python\n",
"def f(x, y):\n",
" from math import cos, sin\n",
" s = cos(x)\n",
" t = sin(y)\n",
" return s + t\n",
"```\n",
"The keyword `return` specifies the value to be returned by the function. It can be any Python object.\n",
"\n",
"**Exercise:**\n",
"- Copy the function `f` above in a code cell and test it with various input values.\n",
"- Program the function $g: z \\mapsto exp(z^2 + z + 1)$.\n",
"- What is the value of `f(g(1.0), 2.3)`?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Make a function `sign(x)` that returns the sign of a number `x` (i.e. `-1` if `x` is negative, `0` if `x` is zero and `1` if `x` is positive)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- Write a function `fib_range(n)` that returns the list of the first $n$ Fibonacci numbers.\n",
"- Write a function `fib(n)` that returns the $n$-th Fibonacci number (this function must not use a list).\n",
"- Check the following formulas up to $n=100$:\n",
" $$F_{2n-1} = F_n^2 + F_{n-1}^2, \\quad F_{2n} = F_n (F_{n-1} + F_{n+1}) = F_{n+1}^2 - F_{n-1}^2$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"**Exercise:**\n",
"- Write a function `mean(l)` that returns the mean value of a list `l` made of floating point numbers.\n",
"- Write a function `var(l)` that returns the variance of `l`.\n",
"- Compute the mean and variance of the following list of numbers\n",
"```python\n",
"[1.34, 12.25, 5.5, 3.26, 7.22, 1.7, 11.12, 3.33, 10.23]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"**exercise:** The Collatz function is the function defined on the positive integers as $collatz(n) = n/2$ if $n$ is even and $collatz(n) = 3n+1$ otherwise. It is a conjecture that starting from any positive integer and repeatedly applying the collatz function we end up with the cycle $1 \\mapsto 4 \\mapsto 2 \\mapsto 1$. For example $$3 \\mapsto 10 \\mapsto 5 \\mapsto 16 \\mapsto 8 \\mapsto 4 \\mapsto 2 \\mapsto 1.$$\n",
"\n",
"- Program the function `collatz(n)`.\n",
"- Write a function `collatz_length(n)` that returns the number of steps needed to reach $1$ by applying the Collatz function starting from $n$.\n",
"- Compute the lengths needed to attain 1 with the Collatz function for the first 50th integers.\n",
"- Find the largest of these lengths."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"\n",
"- What does the following function do?\n",
"\n",
"```python\n",
"def function(n):\n",
" d = []\n",
" for i in range(1, n+1):\n",
" if n % i == 0:\n",
" d.append(i)\n",
" return d\n",
"```\n",
"(*hint: you might want to test this function with small positive integers `n` as input*)\n",
"- Can you find a more efficient way to program it?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Given a smooth function $f: \\mathbb{R} \\to \\mathbb{R}$, the Newton method consists in starting from an initial value $x_0 \\in \\mathbb{R}$ and forming the sequence $$x_{n+1} = x_n - \\frac{f(x_n)}{f'(x_n)}.$$\n",
"Under certain general conditions, one can show that $x_n$ converges to a root of $f$ (if you are curious you can have a look at the corresponding [wikipedia article](https://en.wikipedia.org/wiki/Newton%27s_method)).\n",
"- Write a function `nth_root(s, n, x0, k)` that returns the term $x_k$ of the Newton sequence obtained for the function $f(z) = z^n - s$ and where `x0` is the initial condition.\n",
"- Try this function with $s=2$, $n=2$, $x_0=1$, $k=5$. Which equation does satisfy the output?\n",
"- Try more examples and check whether the returned value satisfy the equation $f(z) = 0$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When calling a function you can also name the arguments. For example defining\n",
"```python\n",
"def f(x, y):\n",
" return x + 2*y\n",
"```\n",
"You can use any of the following equivalent form\n",
"```python\n",
"f(1, 2)\n",
"f(x=1, y=2)\n",
"f(y=2, x=1)\n",
"```\n",
"**Exercise:** Copy, paste and execute the above code."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is also possible to set some of the arguments of a function to some default. For example\n",
"```python\n",
"def newton_sqrt2(num_steps=5):\n",
" x = 1.0\n",
" for i in range(num_steps):\n",
" x = (x + 2.0 / x) / 2.0\n",
" return x\n",
"```\n",
"Defining the function as above, the argument `num_steps` is optional. You can hence use this function in any of the following form\n",
"```python\n",
"newton_sqrt2()\n",
"newton_sqrt(12)\n",
"newton_sqrt(num_steps=12)\n",
"```\n",
"**Exercise:**\n",
"- Find out what the above code is doing.\n",
"- We have already seen some functions with optional arguments. Do you remember some?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- Copy the function `nth_root`, change its name to `nth_root_bis` where:\n",
" - the argument `x0` is optional with default `1.0`\n",
" - the argument `k` is optional with default `10`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is valid to write a Python function that does not contain `return`. For example\n",
"```python\n",
"def welcome_message(name):\n",
" s = \"Hello \" + name + \"!\"\n",
" print(s)\n",
"```\n",
"or with no argument\n",
"```python\n",
"def am_i_beautiful():\n",
" return 'yes'\n",
"```\n",
"**Exercise:**\n",
"- What do the above functions do?\n",
"- Copy, paste and execute the function `welcome_message` in a code cell and call it with your name as argument.\n",
"- What is the output value of `welcome_message`? (*hint*: use the `type` function that we used in the worksheet 1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"Recursion\n",
"---------\n",
"We call a function recursive when it calls itself. The following is a recursive implementation of the factorial function\n",
"```python\n",
"def factorial(n):\n",
" if n == 0:\n",
" return 1\n",
" else:\n",
" return n * factorial(n-1)\n",
"```\n",
"It can be viewed as the following mathematical definition of factorial\n",
"$$\n",
"0! = 1 \\qquad n! = n \\times (n-1)!\n",
"$$\n",
"Let us insist that in a recursive function you always need a special case for the initial step. Otherwise your code contains an infinite loop.\n",
"\n",
"**Exercise:**\n",
"- Copy paste the `factorial` function above.\n",
"- Make a for loop in order to print the valuf of `factorial(n)` for `n` from `0` to `10` included.\n",
"- Implement a recursive function `binomial_rec(n, k)` to compute the binomial number $\\binom{n}{k}$.\n",
"- Implement a recursive function `fibonacci_rec(n)` to compute the $n$-th Fibonacci number.\n",
"- In each case could you compute how many function calls are done?\n",
"- Write a recursive function with no initial condition. What kind of errors do you get when it is called?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Use a recursive function to draw the following pictures\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Extra exercises (optional, if you do all I buy you a beer)\n",
"----------------------------------------------------------"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"\n",
"**Exercise (++):** We have at our disposition three lists `l1`, `l2` and `l3`. At each step we are allowed to take the last element from a list and put it on the top of another list. But all lists should always be in increasing order.\n",
"\n",
"The following example is a valid sequence of moves\n",
"\n",
" l1 l2 l3\n",
" \n",
" [0, 1, 2] [] []\n",
" [0, 1] [] [2]\n",
" [0] [1] [2]\n",
" [0] [1, 2] []\n",
" [] [1, 2] [0]\n",
" [2] [1] [0]\n",
" [2] [] [0, 1]\n",
" [] [] [0, 1, 2]\n",
" \n",
"Write a (recursive) function that print all steps to go from\n",
"\n",
" l1 = [0, 1, 2, 3, 4]\n",
" l2 = []\n",
" l3 = []\n",
"\n",
"to\n",
"\n",
" l1 = []\n",
" l2 = []\n",
" l3 = [0, 1, 2, 3, 4]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"**Exercise (++):** Write a recursive function that solves the following problem:\n",
"given a positive integer $n$ and a positive rational number $p/q$ find all solutions in positive integers $1 \\leq a_1 \\leq a_2 \\leq \\ldots \\leq a_n$ that satisfies $$\\frac{1}{a_1} + \\frac{1}{a_2} + \\ldots + \\frac{1}{a_n} = \\frac{p}{q}.$$\n",
"(you could first prove that there are finitely many solutions)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (++):** Write a function `plot_conic(a, b, c, d, e, f)` that plots the conic of equation $$a x^2 + bxy + cy^2 + dx + ey + f = 0$$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (++):** A square in a list is a sublist that is repeated twice. For example, the list `[0, 1, 2, 1, 2]` contains a repetition of the sublist `[1, 2]`. And `[0, 2, 1, 1, 2]` contains a repetition of `[1]`. A list that does not contain a square is called squarefree. For example, `[0, 1, 2, 0, 1]` is squarefree.\n",
"- Write a function to check if a given list is squarefree.\n",
"- How many lists containing only the numbers `0` and `1` are squarefree?\n",
"- Find the smallest lexicographic squarefree list containing only the letters `0`, `1` and `2` and has length 100."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (++):** For each recursive function you wrote make a non-recursive version."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Copyright (C) 2016 Vincent Delecroix <vincent.delecroix@u-bordeaux.fr>\n",
"\n",
"This work is licensed under a Creative Commons Attribution-NonCommercial 4.0\n",
"International License (CC BY-NC-SA 4.0). You can either read the\n",
"[Creative Commons Deed](https://creativecommons.org/licenses/by-nc-sa/4.0/)\n",
"(Summary) or the [Legal Code](https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode)\n",
"(Full licence)."
]
}
],
"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.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}