`Numpy`

, `Scipy`

, and `Matplotlib`

, which are automatically included in Anaconda."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1 - Basics - Lists and Loops\n",
"\n",
"Here are a few basic exercises to begin. Some of them may be made easier by inbuilt functions in Python, Numpy, etc.\n",
"\n",
"Below you are given a list\n",
"1. Iterate though this list (use some sort of loop!) and, in the following order:\n",
" - Remove any odd number greater than 5.\n",
" - Halve any even number"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12\n",
"8\n",
"9\n",
"2\n"
]
}
],
"source": [
"A = [12, 8, 9, 2, 18, 3, 15, 19, 6, 12, 15, 3, 20, 3, 13, 6, 1, 20, 13, 14]\n",
"\n",
"# YOUR CODE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now are going to explore a common mistake people make when creating certain objects in python. We first play around with an integer:\n",
"- Assign an integer to the variable `a`\n",
"- Set `b = a`\n",
"- Change `b`\n",
"\n",
"What does `a` look like? What about `b`?\n",
"\n",
"Lets do the same for a list\n",
"- Assign a list to the variable `A`\n",
"- Set `B=A`\n",
"- Change `B`\n",
"\n",
"What does the list `A` look like? What about `B`?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# EDIT THIS\n",
"a = 1\n",
"b = a\n",
"b += 1\n",
"\n",
"A = [1, 2, 3, 4]\n",
"B = A\n",
"B[-1] = 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the first situation, if you print out `a` and `b`, you will see `a = 1`, and `b = 2`.\n",
"\n",
"For the second, if you print out `A` and `B`, you will see `A = [1, 2, 3, 3] = B`.\n",
"\n",
"So, what is going on? You would expect one of these things to happen in both cases, surely?\n",
"\n",
"First, when you something to a variable, for instance an integer to `a`, or a list to `A`, you actually place that information in memory. That variable then just points to that position in memory. When you then assign `b = a`, or `B = A`, you actually telling `a` and `B` to point to the same positions in memory respectively. The function `id` prints out the actual memory id.\n",
"\n",
" - Print out the id's of `a` and `b` in the code below, after altering `b`. Do the same for `A` and `B`.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# PRINT OUT THE ID's. The first is done for you!\n",
"a = 1\n",
"b = a\n",
"print(\"id's for a and b\")\n",
"print(id(a))\n",
"print(id(b))\n",
"b += 1\n",
"print(\"id's after b is changed\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# The same again!\n",
"A = [1, 2, 3, 4]\n",
"B = A\n",
"print(\"id's for A and B\")\n",
"B[-1] = 3\n",
"print(\"id's after B is changed\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"See how they have the same memory id before altering `b` and `B`? However, after we alter `b`, the id changes, while `B` remains the same! \n",
"\n",
"Now, we have to talk about **mutability**. An object is mutable if it can be altered after creation. The opposite to this is **immutability**. As expetcted, an object is immutable if it can't be altered after creation.\n",
"\n",
"### Integers are immutable. \n",
"\n",
"They cannot be altered after you create them. If you then do anything to an integer, the variable actually stores this new information in a different position in memory. The same is true for floats, strings, and a variety of other types.\n",
"\n",
"### Lists are mutable. \n",
"You can edit a list, hence it doesn't have to store this information in a new position in memory when `B` is edited. If you assigned a new list to `B`, it will use up another position in memory however."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A = [1, 2, 3, 4]\n",
"B = A\n",
"print(id(A))\n",
"print(id(B))\n",
"B = [0, 0 ,0]\n",
"print(A)\n",
"print(id(A))\n",
"print(B)\n",
"print(id(B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So it's important to understand if you variable is mutable or not. If you are ever unsure, google it!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2 - Matrices\n",
"\n",
"Using numpy, create the following two matrices, and solve the following questions\n",
" $$ \n",
" A = \\begin{bmatrix}\n",
" 6 & 4 & 2 & 0 & 4\\\\\n",
" 6 & 1 & 3 & 9 & 0\\\\\n",
" 2 & 1 & 8 & 6 & 7\\\\\n",
" 5 & 6 & 1 & 8 & 0\\\\\n",
" 1 & 7 & 7 & 9 & 0\\\\\n",
" \\end{bmatrix}\n",
" \\quad\n",
" b = \\begin{bmatrix}\n",
" 9 \\\\ 6 \\\\ 4 \\\\ 6 \\\\ 5\n",
" \\end{bmatrix}\n",
" $$\n",
" \n",
"1. What is the determinant of $A$?\n",
"2. Find the product $Ab$.\n",
"3. Find $x$ satisfying $Ax=b$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# YOUR CODE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Big Matrices and Matrix Operations\n",
"\n",
"During this course, you may be expected to manipulate and create very large matrices. You want to, as much as you can, avoid loops when working with matrices. The best way to create and alter matrices is by learning the operations in built in numpy. Here are the most important operations.\n",
"\n",
"| Operation | Description | \n",
"| :-: | :- |\n",
"| `np.add(A, b)`, `np.subtract(A, B)`, `np.divide(A, B)`, `np.multiply(A,B)`| Elementwise operations |\n",
"| `A + B`, `A-B` `A/B`, `A*B` | Same as above |\n",
"| `np.dot(A,B)` / `np.matmult(A,B)` / `A@B` | Matrix Multiplication, the last two are the same. `np.dot` and `np.matmult` work slightly differently (see docs for details) |\n",
"| `np.transpose(A)` / `A.T` | Tranposition |\n",
"\n",
"Some useful functions are in the numpy.linalg library, and in the scipy.lingalg library. See [here](https://numpy.org/doc/stable/reference/routines.linalg.html) for the numpy functions, and [here](https://docs.scipy.org/doc/scipy/reference/linalg.html) for the scipy functions. \n",
"\n",
"Some classic functions are implemented and work elementwise in numpy. For instance `np.exp(A)` takes the exponential of each element in the array. See [here](https://numpy.org/doc/stable/reference/routines.math.html) for a list of functions. \n",
"\n",
"Finally, [this page](https://numpy.org/doc/stable/reference/routines.array-creation.html) contains some functions to create a variety of classic matrices, for instance the idenetity or diagonal matrices. See also the special matrices section of [here](https://docs.scipy.org/doc/scipy/reference/linalg.html)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solving a random big matrix\n",
"The following exercise hasn't been designed with a practical purpose, but demonstrates some of the useful matrix operations.\n",
"\n",
"We are trying to solve the following problem: We wish to find $x$ satisfying\n",
"$$\n",
"Ax = b\n",
"$$\n",
"where $A$ is a random symmetric matrix.\n",
"\n",
"We can create a random matrix using `np.random.randint`, and a random vector similarly. We then create a random symmetric matrix by taking the random matrices upper triangular part, using `np.triu`, adding that to its transpose. We can then either use `np.linalg.solve` or `linalg.solve` after importing `linalg` from `scipy`. \n",
"\n",
"- Finish the code off below, using these instructions. Remember to test your solution."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"from scipy import linalg\n",
"import time\n",
"\n",
"np.random.seed(1230)\n",
"A = np.random.randint(100, size=(10000, 10000))\n",
"b = np.random.randint(100, size=10000)\n",
"\n",
"# From here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3 - Plotting\n",
"\n",
"Plot the following functions using [matplotlib](https://matplotlib.org/):\n",
"- $f(x) = \\exp(x\\% 4), \\quad\\ x\\in(1,10).$ (The `%` opperator gives the remainder from division)\n",
"- $g(x) = \\sin(x)$ and $h(x) = \\cos(x^2)$ on the same plot, for $x\\in(-\\pi, \\pi)$. Use a legend and labels to distinguish the two curves."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"# YOUR CODE - f"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# YOUR CODE - g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4 - Root Finding\n",
"Below you will find a broken implementation of the [Secant method](https://en.wikipedia.org/wiki/Secant_method), whose purpose is to find the roots of a given function. You may have already encountered [Newton's method](https://en.wikipedia.org/wiki/Newton%27s_method) for finding roots, an iterative method given by\n",
" $$ x_{n+1} = x_n + \\frac{f(x_n)}{f'(x_n)}. $$\n",
"This method can be found by replacing the derivative $f'(x_n)$, by it s finite difference. You will encounter finite differences later in the course. See also exercise 4 for the approximation of $f’(x)$ with a finite difference approximation.\n",
"\n",
"Here, we note a few things.\n",
"\n",
"- This is a great example of why functions are useful. When you want to find the roots of a polynomial using this method, if you didn't use a function you would have to rewrite this code, taking time and making the code less readable.\n",
"- The function below starts with a doc string. Always include a comment at the start of the function explaining what it does. You don't need to go in this much detail (I often don't) unless you intend to release the code publicly.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def secantMethod(f, x0, x1, maxIter=100, E=0.001):\n",
" \"\"\"\n",
" Implemention of the Secant root finding method.\n",
"\n",
" --Parameters--\n",
" f: Function\n",
" Floats as input and output\n",
" x0, x1: Floats\n",
" Initial guesses\n",
" maxIterations: Int\n",
" Positive integer, max number of iterations for algorithm\n",
" E: Float\n",
" Convergence factor\n",
"\n",
" --Returns--\n",
" float, approximation to root should the method converge\n",
" \"\"\"\n",
" while maxIter>=0 and np.abs(x0 - x1) > E\n",
" x0, x1 = x1, x1 - f(x1 * (x1 - x0)/(f(x1) - f(x0))\n",
" maxIter -= 1\n",
" \n",
" return x1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercises\n",
"Consider the following functions\n",
" $$f(t) = -6 + 11 t - 6 t^2 + t^3$$\n",
" $$g(t)= t^2 + \\exp(t) + \\sin(t^3) -3$$\n",
" \n",
"1. Debug the above code. There are 2 errors.\n",
"2. Using [matplotlib](https://matplotlib.org/), which has been imported for you below, plot the graphs of these two functions.\n",
"3. Use the secant method to find some roots of these two functions.\n",
"4. Alter the function above so it also returns the number of iterations in a tuple (root, iterations). How many iterations did it take to converge to a solution given your inputs?\n",
"5. Implement the secant method recursively, i.e. by calling itself within itself. Compare your results to the given implementation to ensure your implementation is working."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"\n",
"# YOUR CODE - f\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# YOUR CODE - g\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# YOUR CODE - Recursive Implementation\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5 - Circular Primes\n",
"\n",
"We all know what a prime number is. A circular prime is a numer whose digits can be rotated to always produce a prime number. For instance, the number $113$ is a circular prime. That is, $113$, $311$, and $131$ are all prime numbers.\n",
"\n",
"Our goal is to find all the circular primes below a given number $N$.\n",
"\n",
"1. First, create a function that outputs whether or not a number is prime. Use the list of testNumbers to test your function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def isPrime(n):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"testNumbers = [1, 2, 3, 4, 7, 8, 13, 26, 113, 131, 311]\n",
"for n in testNumbers:\n",
" print(f\"{n}: {isPrime(n)}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now need a way to rotate the digits of a number. We will use a generator for this. You probably won't need to use a generator during the course, but they are a useful thing to know about. Rather than returning in a function, you yield the current output, and this can be used in a for loop for our purposes.\n",
"\n",
"2. There is a bug in the below code, however. Can you fix it?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def digitRotator(n):\n",
" yield n\n",
" # Converts the integer n to a list of its digits in string form.\n",
" lst = [i for i in str(n)]\n",
" \n",
" for i in range(len(lst) - 1):\n",
" # Rotates the list, converts it back into a strings, then back into an integer, and yields it.\n",
" lst = [lst[1]] + lst\n",
" del lst[1]\n",
" yield int(\"\".join(lst))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now create an algorithm to find the circular primes. It is included below, however you should try programming it syourself first.\n",
"\n",
"3. Code an algorithm to find the circular primes."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Try it yourself first."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"jupyter": {
"source_hidden": true
}
},
"outputs": [],
"source": [
"def findCircPrimes(N):\n",
" # Finds all the circular primes up to the integer N\n",
" circPrimes = []\n",
" for num in range(N):\n",
" isCircPrime = True\n",
" for n in digitRotator(num):\n",
" # If any of the rotations are not prime, this is not a circular prime\n",
" if not isPrime(n):\n",
" isCircPrime = False\n",
" break\n",
" if isCircPrime:\n",
" circPrimes.append(num)\n",
" \n",
" return circPrimes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"4. Finally, use our algorithm to find all the circular primes below 1000."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}