In this notebook we introduce control flow tools that will allow us to write real world code used in simulations. As their name imply, these structures determine the paths that can be taken in a particular code. Let us start with the `if/elif/else`

statement.
The example below illustrates their general structure.

```
import random
x = random.random()
print("Random number picked in [0,1): ", x)
if x < 1/3:
subinterval = "[0,1/3)"
elif x < 2/3:
subinterval = "[1/3,2/3)"
else:
subinterval = "[2/3,1)"
print("x belongs to " + subinterval)
```

The piece of code above uses the random module. This library contains
implementations of pseudo-random number generators for several probability distributions. If you type `random.random()`

in the interactive console, you will see that a number in the interval $[0,1)$ is printed to the screen. Thus, `random.random()`

samples from the uniform probability distribution in $[0,1)$. In our code above, the number sampled is assigned to the variable `x`

and a string is printed to the screen telling us what value `x`

points to. What is done next depends on the value assigned to `x`

. If the value sampled is less than $1/3$, the boolean expression `x < 1/3`

returns `True`

and the command `subinterval = "[0,1/3)"`

is executed. If the sampled number is greater than $1/3$, the interpreter ignores the assignment in the scope of the `if`

statement and tests the condition on the `elif`

statement. Therefore, if the variable `x`

satisfies $\frac{1}{3}\leq$ `x`

$< \frac{2}{3}$, the condition evaluated in the `elif`

statement will return `True`

and the line `subinterval = "[1/3,2/3)"`

will be executed. On the other hand, if $\frac{2}{3}\leq$ `x`

, both the `if`

and `elif`

conditions will be false and the line inside the scope of the `else`

statement, `subinterval = "[2/3,1)"`

, will be executed. After this `if/elif/else`

structure, a line telling us the interval `x`

belongs to is printed. You should note that you can use as many `elif`

statements as you want. Of course, you are not obliged to use neither `elif`

nor `else`

after an `if`

statement: they are optional. The general formula for Python conditional statements is summarized below.

```
if boolean expression:
block of code
elif another boolean expression: #This is optional!
another block of code
else: #This is optional too!
yet another block of code
```

You can put these concepts in practice in the next exercises.

```
In [1]:
```import random

```
In [ ]:
```

```
In [ ]:
```

The full solution to the quadratic equation $ax^2 + bx + c$ requires the use of complex numbers, so this is a great opportunity to introduce them.
In Python the imaginary unit $i$ that squares to $-1$ is written as `1j`

. We can indeed see that this is so by typing the following code.

```
i = 1j
print("Type of i: ", type(i))
print("i squared: ", i**2)
```

Multiples of $i$ are obtained substituting the number 1 by the appropriate value. Thus, $3i$ becomes `3j`

. We can now move on to our problem. If you want more details about the complex type, you can always read the documentation.

In this problem, your task is to implement the solution to the quadratic equation considering separately the three cases: $\Delta > 0$, $\Delta < 0$ and $\Delta = 0$, where $\Delta = b^2 - 4ac$.

```
In [ ]:
```

Now we get to the point where we will be able to write real world programs. The data structure that will allow us to do this is the `for`

loop. With loops, we will be able to solve problems of arbitrary complexity. Up to this point, we have been writing programs that run in constant time. This means that the amount of time it will take to run them is bounded by their number of lines of code. Evidently this a problem, since as complexity grows we will have to write ever more lines of code. Clearly this task will quickly become impracticable. As an example, suppose we naively decide to compute the sum of the first $n$ natural numbers by adding them one by one. We would quickly be overwhelmed! A `for`

loop does this trivially:

```
def sum_natural_numbers(n):
"""
Sums the n first natural numbers
n: last number in the sum
"""
total_sum = 0
for number in range(n+1):
total_sum = total_sum + number
return total_sum
```

The `for`

loop above has been implemented with a range-type object. These objects are used in the following way.

```
range(start, stop, step)
```

We provide three arguments to `range`

: a start point that defaults to $0$ if ommited; a stop point that has to be provided, since it has no default value; and a step size, which is how we will reach the stop point from the start point. The step size defaults to 1. Note that in the example we provided above, we have used exactly the default values for start and step, so we only cared to give the stop argument.

How does the `sum_natural_numbers(n)`

function work? We initialize the `total_sum`

variable, which points to the partial sums, to zero. After this, the `for`

loop does the work for us. The variable `number`

takes every single value from `0`

to `n`

in steps of `1`

and adds it to `total_sum`

. It is important to note that the command inside the `for`

loop is only executed while `number < n+1`

. That is, the value `n+1`

is itself excluded. That is why in our code above we computed the sum of the `n`

first numbers with a `range`

whose `stop`

point is `n+1`

. We can see all the elements generated by `range`

by generating a list from it:

```
list(range_object)
```

```
In [ ]:
```

```
In [ ]:
```

```
In [ ]:
```

Loops are intimately related to iterables. Indeed we could tautologically say that iterables are data structures that can be looped or iterated over. We have been using them for a while now: whenever we plotted anything, we always had to create lists of x coordinates and y coordinates and pass them as arguments to `plt.plot()`

. It is worth spending a little time in these data structures, since they are among Python's basic data types. They are the following.

- Strings;
- Lists;
- Tuples;
- Dictionaries.

Let us briefly review each of these types.

In Python, strings are of type `str`

. They are created from characters enclosed between quotes (single or double). The most trivial use you can give them is simply to print text to the screen. For example,

```
print("hello world!")
```

prints this silly (albeit very canonical in computer science) message. There is a lot more to strings in Python though. Indeed, they are a nice oportunity to introduce some basic concepts related to object orientation. We can think of particular strings such as `"hello world"`

as instances of a larger class of objects, in this case the class `str`

. The advantage of thinking in these terms is that a class is a big bundle that includes not only the instances, but also functions that act on them. Such functions are called methods. For example, given any lower case string, we might want to get its upper case version. This is is easily accomplished with the `str.upper()`

method.

```
myLowerCaseString = "hello world"
myUpperCaseString = myLowerCaseString.upper()
print(myUpperCaseString)
```

The pattern you see above, which is called dot notation, will repeat itself when using this object-oriented approach. The general recipe to apply the method `myMethod`

to an instance `myObject`

of a class is

```
myObject.myMethod(arguments)
```

Python provides several built-in string methods. As another example of introspection in Python, the methods available in a class can be seen with `dir`

, such as in the example below.

```
dir(str)
```

In the next exercise you are invited to try a string method.

```
In [ ]:
```

We are going to view Python's `list`

type as just that: a list of obects (although the concept of list can be made more precise in computer science). Python's lists have two important features: they are mutable and they can store objects of different types. By mutable we mean that we can "edit" the contents of a given list at any time. Let us try a small example.

```
myList = [1,2,"Hello World"]
print("This is my list: ", myList)
myList[0] = 0
print("This is my edited list: ", myList)
print("Length of myList: ", len(myList))
```

The above example illustrates the important points well. First, a list in Python is written with brackets. After initializing the list, we changed its zeroth entry. This is an important point to note: indexing in Python starts at zero. In the end we use the `len()`

function to print the list's length, which is equal to the number of elements in the list. Also note that the list above contains objects of different types: `int`

and `str`

.

Just as with strings, Python has several built-in list methods that perform usual operations on lists. You will surely use them a lot.

Besides using lists to store data, we shall loop over them very often. Given any of the iterable types, we can do this with the following command.

```
for element in iterable:
block of code
```

Another way to iterate over lists (and any other ordered iterable) is by indexing. Indeed given the iterable `orderedIterable`

, we could write the following code to iterate over it.

```
for index in range(len(orderedIterable)):
block of code
```

Let us try some exercises on lists now.

Write two functions, `print_iterable(anIterable)`

and `print_by_index(orderedIterable)`

. The first takes an iterable object and prints all its elements by the first method. The last one does the same, but using the second method. Test your functions with the string `"hello world!"`

and the list `[0,1,2,3,4,5,6,7,8,9]`

.

```
In [ ]:
```

The purpose of this exercise is to get you familiar with the indexing possibilities offered by lists. A point to note is that although we use lists here, what you shall do in this exercise will also work with strings and tuples. Try to guess what should be the result of the following commands.

```
myList = list(range(20))
a = myList[-1]
b = myList[1:6] #This is a slice!
c = myList[-1]
d = myList[-14:-10]
e = myList[:10]
f = myList[-6:]
g = myList[-15:12]
h = myList[15:]
print("This is a: ", a)
print("This is b: ", b)
print("This is c: ", c)
print("This is d: ", d)
print("This is e: ", e)
print("This is f: ", f)
print("This is g: ", g)
print("This is h: ", h)
```

```
In [ ]:
```

In this exercise we analyze embedded iterables. For the sake of clarity, we consider lists whose elements are themselves lists (or some other kind of iterable like strings). Try to guess the output of the commands below.

```
myList = [[1,2,3], "hello world!", ['a','b',[4,5,6,7]]]
a = myList[0]
b = myList[0][1]
c = myList [-2]
d = myList[-2][-4]
e = myList[len(myList) - 1]
f = myList[len(myList) - 1][-1]
g = myList[len(myList) - 1][-1][2]
h = myList[len(myList) - 1][-1][:]
print("This is a: ", a)
print("This is b: ", b)
print("This is c: ", c)
print("This is d: ", d)
print("This is e: ", e)
print("This is f: ", f)
print("This is g: ", g)
print("This is h: ", h)
```

```
In [ ]:
```

```
In [ ]:
```

In this exercise we will write code that decomposes decimal integers to their decimal power representation. Given an integer $z$ that has a $n$-length decimal power representation, say $z \simeq z_{n-1}...z_0$, with $z_i \in \{0,1,...,9\}$, its decimal power representation will be

\begin{equation*} z = z_010^0 + z_110^1 + ... + z_{n-1}10^{n-1} \end{equation*}Your program should take in an integer and return a string containing its decimal power representation.

```
In [2]:
```def decimal_representation(anInt):
"""
Returns a string with decimal power representation of anInt.
anInt: integer.
"""
#your code goes here
pass

```
In [ ]:
```

Common sense tells us that as we take larger and larger natural numbers, the occurrence of primes becomes ever rarer. Let us investigate this proposition. Write a function that searches the first $n$ natural numbers for primes. Your function `find_primes(n)`

should return a list with all the prime numbers $ \leq n$. Use your function to plot the proportion of natural numbers $\leq n$ that are primes. You should compare your plot to a plot of the function $f(n) = \frac{1}{\ln n}$ (see the prime number theorem).

```
In [ ]:
```

In this exercise we use binary search to find if an element is in a list. The algorithm works as follows: at each iteration, we divide the unsearched list in two halves and choose one of them to inspect. If the element we are searching for is found, the search stops and we return its index. If not, the search moves on to the unsearched half. Fill in the remaining steps below.

```
In [30]:
```def binary_search(aList, element):
'''
Finds and element in a list via binary search. Returns the index where
element was found, or a message saying the element was not found in the
list.
aList: list to be searched
element: the element we are looking for in aList.
'''
pass

The next iterable type in Python is the `tuple`

type that consists, well, of tuples. They seem very similar to lists, so it is important to emphasize their differences. Just like strings, tuples are immutable. This means that once you have created a `tuple`

object, you cannot change it anymore. This adds safety to your code when immutability is desired. Python's designers also had in their minds different uses for lists and tuples. Although not mandatory, lists should be homogeneous, whilst tuples should be heterogeneous. This means that each entry in a tuple ideally should have a different meaning. Think for example of polar coordinates $(r,\theta)$. The first entry of this tuple has a meaning (radial distance) that is different from the second one (angular position). Let us see some sample code that assigns a tuple to the variable `myTuple`

.

```
myTuple = (1,2,3,4,5,6,7,8,9)
print(myTuple)
```

```
In [ ]:
```

Dictionaries (type `dict`

) are an example of unordered iterable. In practice what this means is that dictionaries don't use the same number-based indexing system that we have seen in the other iterables. Instead, dictionaries can be viewed as maps that link keys to values. In order to access a particular value stored in a dictionary, we have to provide its corresponding key as an index. Hopefully, running the example below will make this explanation redundant.

```
myDict = {'a': 1, 'b': 2, 'c': 3}
print("myDict keys: ", myDict.keys())
print("myDict values: ", myDict.values())
print("Value associated to key 'b': ", myDict['b'])
```

Note in the code above the use of dictionary methods, `myDict.keys()`

and `myDict.values()`

.

```
In [ ]:
```

Some quick, important facts about dictionaries. First, the keys can only be immutable types. Thus, lists cannot be used as keys, for example. Strings, ints/floats and tuples, on the other hand, are perfectly acceptable keys. Second, as should be clear by now, dictionaries are constructed with a pair of braces; an empty pair of braces creates an empty dictionary. Third, we can always add key:value pairs by simply assigning the desired value to the new key. Again, an example should make these matters clear.

```
myEmptyDict = {}
print("This is an empty dictionary: ", myEmptyDict)
myEmptyDict['a'] = "First value added"
print("Key 'a' added: ", myEmptyDict)
```

```
In [ ]:
```

For quite a long time, the ASCII character encoding was the standard encoding system in many platforms. In this exercise we shall create a dictionary that encodes ASCII as follows. The dictionary's keys are the 128 characters encoded by ASCII. Its values are the binary encodings corresponding to each character. Fill the missing steps below.

```
In [21]:
```#list of ascii characters
asciiCharactersList = [chr(i) for i in range(128)]
#list of binary values
#now make a dict from the two lists and print it to the screen
#Convert the string "Hello World!" to ascii binary and print it

The simplest type of encryption scheme is perhaps the Caesar cipher. The idea is to translate every character in the alphabet by a fixed value. If we translate every character by 2, for example, the resulting Caesar cipher maps $a \rightarrow c$, $b \rightarrow d$, ..., $x \rightarrow z$, $y \rightarrow a$, $z \rightarrow b$ and we perform all these substitutions in a given text to encode it. Write the function `ceasar_cipher()`

that encodes a string. Do it by filling the code below, then test it in a string of your choice.

```
In [24]:
```def caesar(translation, aString):
"""
Returns the encoded version of aString, where all characters are translated by the value of translation
translation: int in range(26)
aString: string to be encoded.
"""
pass

At this point we are familiar with most of Python's basic structures, so this is a good moment to discuss scopes and namespaces again. The scope of variables has been briefly mentioned in the previous notebook. It is certainly a good idea to read about it a little more carefully now. Here, we want to introduce global variables. If you want a quick example that shows the difference between a local and a global variable, run the code below.

```
x = 42
def local_assignment():
x = 3.14
print("This is x inside of local_assignment(): ")
print(x)
def global_assignment():
global x
x = 2.78
print("This is x inside of global_assignment(): ")
print(x)
print("This is x before calling any function:")
print(x)
print("Now I will call local_assignment():")
local_assignment()
print("Note that x in the global scope did not change:")
print(x)
print("Now I will call global_assignment():")
global_assignment()
print("Note that global_assignment() changed x! This is x in the global scope:")
print(x)
```

Hopefully, the example above made clear the point that variables defined inside of a function are local to the function's scope. If you wish to have different behaviour, you have to declare a global variable explicitly inside a function definition. A word of caution: although global variables can be pretty useful sometimes, their use is often disencouraged due to the extra difficulties they might introduce in the debugging process. Therefore, be parsimonious with their use.

Suppose you have two scalar variables,`a`

and `b`

. One would commonly swap their values using a third auxiliary variable `c`

like in the example below.

```
a = 1
b = 2
print("This is a before the swap: ", a)
print("This is b before the swap: ", b)
#Swapping
c = a
a = b
b = c
print("This is a after the swap: ", a)
print("This is b after the swap: ", b)
```

How would you write a function that swaps the values of any two variables?

```
In [ ]:
```

Copying lists in Python can be a tricky feat. This exercise aims to alert you to that. Suppose we want to copy a list from a variable `a`

to a variable `b`

. We might want to keep the list in `a`

intact while performing some operations in `b`

. As an example, suppose we want the list in `b`

to contain the elements of `a`

, but with the zeroth element changed. A naive first try would be the following.

```
a = [1,2,3]
b = a
print("This is a: ", a)
print("This is b: ", b)
b[0] = 10
print("This is a after the change in b: ", a)
print("This is b after the change in b: ", b)
```

Our code shows that we indeed changed `b`

, but we also changed a! This is due to the fact that Python does not have variables strictly speaking, but names. When we execute the command `b = a`

what we are actually doing is giving the list `[1,2,3]`

another name, `b`

. Thus, actions performed in `b`

will be performed on the same list that the name `a`

refers to. How would you solve this issue? Specifically, write a function that returns a copy of a list. Then test if you have a true copy by changing the zeroth element of the list returned by your function.

```
In [ ]:
```

We end this notebook with a brief discussion on recursion. We can view recursion as another kind of loop, one in which further values in the computation refer to previous values, so that the whole computation cascades to a defined set of primary cases. Thus recursion works by solving many smaller versions of the same problem. A classical example is the recursive computation of the factorial of a natural number. We write this example below.

```
def recursive_factorial(n):
if n == 0:
return 1
else:
return n*recursive_factorial(n-1)
```

This solution to the computation of factorials uses the trivial fact that $n! = n(n-1)!$. Note that to compute the factorial of $n$ we end up generating $n+1$ calls to `recursive_factorial()`

. In this case it is not really a big deal, but in some cases, such as the computation of Fibonacci numbers, the number of recursive calls can grow quite overwhelmingly. We will investigate this in the next exercise.

The Fibonacci sequence is an integer number sequence that relates to surprisingly disparate phenomena, ranging from pattern formation in nature to poetry optimization. The full Fibonacci sequence can be recursively generated as follows.

\begin{equation} F(n) = \begin{cases} 0, \text{ if } n = 0;\\ 1, \text{ if } n = 1;\\ F(n-1) + F(n-2), \text{ if } n \geq 2. \end{cases} \end{equation}We want to investigate how fast the number of function calls grow when we recursively generate Fibonacci numbers. To achieve this, we shall use what is usually considered bad practice: a global variable. The global variable `counter`

will count how many times the function `fibonacci(n)`

is called. Fill the missing steps below.

```
In [29]:
```import matplotlib.pyplot as plt
from math import log
counter = 0
def fibonacci(n):
"""
Recursively computes the n-th Fibonacci number.
n: integer, >=0
"""
global counter
counter += 1
pass
#compute the fibonacci(n) for all n in the list below. It might take a while!
nList = [n for n in range(1,30)]
#store in the list below the values of fibonacci(n) for all n in nList
fibList = []
#store in the list below the logs of counter values associated to fibonacci(n), for all n in nList
counterLogList = []
#Generate fibList and counterLogList
#plot counterLogList x nList