2  Data structures

Exercise 2.1 - Lists

A list is a structure allowing to store heterogeneous elements:

list0 = [0, 5.4, "string", True]

Lists are mutable, i.e., it is possible to modify an element, add one or delete one, without having to redefine the whole list.

list0[3] = False # replace True by False
list0.append("new") # add the string "new" to the list
list0.insert(2, 34) # insert 34 in place of 2
list0.remove(0) # remove 0
list0

[5.4, 34, 'string', False, 'new']

In particular, care must be taken when copying a list. If we execute the following code:

list1 = list0
list1[2] = "change"
list0

[5.4, 34, 'change', False, 'new']

then list0 is also modified and is equal to list1. To create a real copy, you have to use the following code:

list2 = list0.copy()
list2[2] = "rechange"
list0

[5.4, 34, 'change', False, 'new']

which does not modify list0. Note that it is possible to modify the elements of a list inside a function:

def f(l):
    l[0] = 0
f(list0)
list0

[0, 34, 'change', False, 'new']

Finally, it is possible to create lists with the help of list comprehension:

list1 = [2*i+1 for i in range(10)]
list1

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

a. Search the documentation for the syntax to concatenate two lists.

b. Look in the documentation for the syntax to extract a slice from a list, i.e., if a is, for example, a list of length 10, return the elements from 6 to 9.

c. Search the documentation for the syntax to return the length of a list.

d. Write a function fibonacci(N) that returns the list of \(N\) first terms of the Fibonacci sequence defined by \(u_{n+2} = u_{n+1}+u_n\) with \(u_0=0\) and \(u_1=1\).

e. Write a function pascal(N) that returns the \(N\)-th line of Pascal’s triangle:

f. Let \((u_n)_{n\in\mathbb{N}}\) and \((v_n)_{n\in\mathbb{N}}\) be the sequences defined by \(u_0=1\), \(v_0=1\), and

\[ \begin{align*} u_{n+1} &= u_n + v_n \,, & v_{n+1} &= 2u _n - v_n \,, \end{align*} \]

for \(n\geq0\). Calculate \(u_{100}\) and \(v_{100}\).

g. Write a function vk(n0,K), which for two integers \(n_0\) and \(K\geq1\) computes the sequence of values \(v_k\) defined by \(v_0 = n_0\) and

\[v_{k+1}=\begin{cases} 3v_{k}+1 & \text{if $v_{k}$ is odd},\\ \frac{v_{k}}{2} & \text{if $v_{k}$ is even}, \end{cases}\]

for \(0 \leq k < K\). For \(K = 1 000\) and various values of \(n_0 \in \{10, 100, 1 000, 10 000\}\), display the last five calculated values, i.e., \((v_{K-4},v_{K-3},v_{K-2},v_{K-1},v_K)\).

Exercise 2.2 - Tuples

Tuples allow, just like lists, to store heterogeneous elements:

tuple0 = (0, 5.4, "string", True)

But unlike lists, tuples are not mutable. It is not possible to modify an element, add one or delete one, without redefining the whole tuple. The advantage of a tuple over a list is that it is hashable, i.e., it can be used as a key in a dictionary.

Finally, it is possible to assign variables inside a tuple, for example:

(a,b) = (1,9)

This is especially useful for exchanging two variables without having to use an additional variable:

(a,b) = (b,a)

a. Check that a tuple is immutable.

b. Define a function mdlast(lst,val) having as argument a list of integer tuples lst and an integer val and return the list of tuples with the last element of each tuple replaced by val. For example, if lst = [(10, 20), (30, 40, 50, 60), (70, 80, 90)], then mdlast(lst,100) should return [(10, 100), (30, 40, 50, 100), (70, 80, 100)].

c. How to convert a tuple into a list and vice versa?

Exercise 2.3 - Sets

Sets are used to store heterogeneous elements in the mathematical sense of set theory:

set0 = {0, 5.4, "string", True}

It is possible to test if an element belongs to a set:

if "string" in set0:
    print("inside")

inside

Sets are mutable, so it is possible to add or remove an element from a set:

set0.add(18) # add 18 to the set
set0.add(0) # add 0 to the set (this does nothing as 0 already belongs to the set)
set0.remove("string") # remove "string to the set

On the other hand, sets can only contain hashable elements, i.e., immutable. In particular a set cannot contain another set:

set1 = { {1,2}, {3}, {4} }

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[23], line 1
----> 1 set1 = { {1,2}, {3}, {4} }

TypeError: cannot use 'set' as a set element (unhashable type: 'set')

Note that in Python there are also immutable sets, called frozenset:

frozenset0 = frozenset([0, 5.4, "string", True])

A string can be transformed into a set:

set1 = set('abracadabra')

As with lists, it is possible to make set comprehensions:

set2 = {x for x in 'abracadabra' if x not in 'abc'}

In this example, strings are automatically transformed into sets. Note that the empty set is defined by set().

a. Define a function divisible(n) that returns the set of integers divisible by n less than or equal to 100.

b. Search the literature to find the intersection, union, and difference of two sets. Determine the numbers less than or equal to 100 that are not divisible by 2 but divisible by 3 and 5.

Exercise 2.4 - Dictionaries

Dictionaries are a structure allowing to store heterogeneous elements indexed by keys (also heterogeneous):

dict0 = {"apples": 0, "pears": 4, 12: 2}

The elements of a dictionary are accessible through the keys:

dict0["apples"]
dict0[12]

2

A dictionary can be seen as an associative array associating to each key a value. The list of keys and the list of values are accessible, respectively, with dict0.keys() and dict0.values(). Dictionaries are mutable, so it is possible to modify a key-value association and to add or remove one:

dict0["apples"] = 3 # modify the value associated to apples
dict0["oranges"] = "many" # add oranges as key with value "many"
del dict0["pears"] # remove the key pears, hence the value
dict0.pop("apples") # remove the key apples, hence the value

3

Although a dictionary is mutable, the keys that compose it must be hashable objects, i.e., immutable. Thus, a list or a set cannot be used as keys in a dictionary:

dict0[list0] = "test"
dict0[set0] = "retest"

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[33], line 1
----> 1 dict0[list0] = "test"
      2 dict0[set0] = "retest"

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

On the other hand, it is possible to have a tuple or a frozenset as a key:

dict0[tuple0] = "test"
dict0[frozenset0] = "rest"

hence the interest of frozensets. As for lists and sets, it is possible to make dictionary comprehensions:

dict1 = {x: x**2 for x in range(5)}

Finally, an interesting thing about dictionaries is the unpacking illustrated by the following example:

def add(a=0, b=0):
    return a + b
d = {'a': 2, 'b': 3}
add(**d)

5

a. How to define an empty dictionary?

b. How to concatenate several dictionaries together?

c. We consider a list of words:

words = ['Apricot', 'Cranberry', 'Pineapple', 'Banana', 'Blackcurrant', 'Cherry', 'Lemon', 'Clementine', 'Quince', 'Date', 'Strawberry', 'Raspberry', 'Pomegranate', 'Gooseberry', 'Persimmon', 'Kiwi', 'Litchi', 'Mandarin', 'Mango', 'Melon', 'Mirabelle', 'Nectarine', 'Orange', 'Grapefruit', 'Papaya', 'Peach', 'Pear', 'Apple', 'Plum', 'Grape']

Write a function position(words, x, n) that returns the list of words with the character x as their n-th letter (starting from zero, as in Python).

d. Assuming that the list of words is very long, then each time the position function is evaluated, the whole set of words is searched, which takes quite a long time. To improve this, build a dictionary mots_dict having as keys the tuples (x,n) and as values the list of words having the character x as n-th letter, i.e., such that mots_dict[x,n] returns the same thing as position(words, x , n) except for the order. Thus, the words list is traversed only once during dictionary construction and then dictionary evaluation is extremely fast for any query.