Abstract

These lecture notes introduce the main concepts related to some of the most important data structures for creating and handling sets and dictionaries. The historic hero introduced in these notes is Jorge Luis Borges, considered one of the most important Argentinian writers of the past century. Among his huge work, he wrote several short stories focussed on the exploration of mathematical concepts and limits.

Copyright notice. This work is licensed under a Creative Commons Attribution 4.0 International License. You are free to share (i.e. copy and redistribute the material in any medium or format) and adapt (e.g. remix, transform, and build upon the material) for any purpose, even commercially, under the following terms: attribution, i.e. you must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. The licensor cannot revoke these freedoms as long as you follow the license terms.

Historic hero: Jorge Luis Borges

Jorge Luis Borges, shown in Figure 1, was an Argentine short-story writer, poet, and essayist, who produce several works laying between philosophical literature and fantasy genre. In his short novels, he explored several aspects and situations related to dreams, labyrinths, libraries, mirrors, the notion of infinity, and religions, among the others.

One of his most known stories is entitled The Library of Babel [1]. In this short piece, he describes an incredibly big library, made of hexagonal rooms, where, in four of the walls of each room, there were 20 bookshelves (5 bookshelves for each wall). Each bookshelf had contained 35 books. Finally, each book counted exactly 410 pages, each page was organised in 40 lines, and each line contained exactly 80 characters. From one of the two empty walls, one could access to a hallway with two small rooms (one where to sleep standing up, the other with a bathroom) and to the stairs to get to higher hexagonal rooms. The idea is that the whole library contained all the books that have been and will be written by using every possible combination of 25 basic characters: 22 letters, the period, the comma, and the space. Of course, the main parts of the books contain a non-sense sequence of characters, while others (or even limited parts of them) are, indeed, describing situations using an intelligible language. However, even between those, there were also books that negated explicitly the statements of the others. Thus, the narrator suggested that we are in the presence of all the possible written books that, even when they make sense, are totally unuseful because they describe any possible fact from all the possible perspectives, and thus there is no absolute truth available and all the possibilities are admissible.

The opening sentence is of particular interest: ​[the Library] is composed of an indefinite and perhaps infinite number of hexagonal galleries​. In this passage, the narrator suggests that, since its very well-explained composition, the library is also made of an infinite number of books, contained in an infinite number of rooms. However, is really this the case?

Understanding infinity is a matter of a personal perception of things. Often we use to refer to an infinite amount of something (time, space, etc.) when actually we are solely speaking about a quite extensive and huge mass of stuff, which still is delimited by some physical or social constraint. The Library of Babel falls in these kinds of situation. Even if the narrator says explicitly that the library is infinite, actually it can contain only ${\displaystyle 2\cdot {10}^{1834097}}$ of books [2]. The previous number has been obtained by considering all the possible combination of all the finite set of charaters in all the 40 pages in all the books that can be generated. And this number exists, even if it is so big that is not manageable by our mind and, thus, we tend to identify it to infinity, while it is not.

Of course, mathematical infinity exists, as an abstract concept – e.g. think about the set of all the prime numbers, which is an infinitive set. However, when one tries to make calculations by means of a computer, which is physically limited in space somehow and, thus, in its resources, we can only reach a plausible approximation of it. For instance, even if it is possible to implement an algorithm that runs forever in a specific programming language, technically speaking its implementation runned by a (electronic) computer can stop (and will stop, after all) due to some external reasons – a blackout, the breaking of some hardware necessary for the correct execution of its processes, etc.

When we consider pragmatic applications and implementations of existing computational systems, we must be aware that infinity (e.g. the indefinite tape of a Turing Machine, the endless execution of an algorithm, etc.) is an illusion. It is just a theoretical tool which allows us to sketch out possible borders for real-world problems.

Unordered structures

In this lectures, we will introduce three specific data structures, that are discussed in details in the following sections, i.e.: sets and dictionaries. Their main characteristics, in addition of being among the most basic and used data structures in algorithms (and, more concretely, in programs), is that they do not specify any order for their elements and that they do not allow repetitions – i.e. the same value cannot be specified twice.

my_first_set = set()  # this creates a new set

my_first_set.add(34)  # these two lines add two numbers
my_first_set.add(15)  # to the set without any particular order
# currently my_first_set contains two elements: 
# set({ 34, 15 })

my_first_set.set("Silvio")  # a set can contains element of any kind
# now my_first_set contains: 
# set({34, 15, "Silvio"})

my_first_set.remove(34)  # it removes the number 34
# my_first_set became: 
# set({15, "Silvio"})

my_first_set.update(my_first_set)  # it doesn't add the new elements since they are already included in the set
# current status of my_first_set: 
# set({15, "Silvio"})

my_first_set_len = len(my_first_set) # it stores 2 in my_first_set_len​

my_first_dictionary = dict()  # this creates a new dictionary

# these following two lines add two pairs
# to the dictionary without any particular order
my_first_dictionary["age"] = 34  
my_first_dictionary["day of birth"] = 15
# currently my_first_dictionary contains two elements: 
# dict({ "age": 34, "day of birth": 15 })

# the pairs of a dictionary can contains even key-value pairs of different types
my_first_dictionary["name"] = "Silvio"  
# now my_first_dictionary contains: 
# dict({"age": 34, "day of birth": 15, "name": "Silvio"})

del my_first_dictionary["age"]  # it removes the pair with key "age"
# my_first_dictionary became: 
# dict({"day of birth": 15, "name": "Silvio"})

my_first_dictionary.get("age")  # get the value associated to the key "age"
# the returned result will be None in this case, since "age" has been just deleted

# the following lines create a new dictionary with two pairs
my_second_dictionary = dict()
my_second_dictionary["month of birth"] = 12
my_second_dictionary["day of birth"] = 28

# the following line add a new pair to the current dictionary, and rewrite 
# the value associated to the key ""day of birth" with the one specified in
# the my_second_dictionary dictionary
my_first_dictionary.update(my_second_dictionary)  
# current status of my_first_dictionary: 
# dict({"day of birth": 28, "name": "Silvio", "day of month": 12})

my_first_dictionary_len = len(my_first_dictionary) # it stores 3 in my_first_dictionary_len​​

Exercise

1. Write a pseudocode in ThyMopani so as to create a set of the following elements: ​Bilbo​, ​Frodo​, ​Sam​, ​Pippin​, ​Merry​.

2. Consider the set created in the aforementioned exercise, stored in the variable my_set. Describe the status of ​my_set after the execution of each of the following operations: ​my_set.remove("Bilbo"), ​my_set.add("Galadriel"), ​my_set.update(set({"Saruman", "Frodo", "Gandalf"})).
3. Suppose that all the elements in the set returned by the previous exercise have been organised in two different sets, i.e. set_hobbit that refers to the set set({"Frodo", "Sam", "Pippin", "Merry"}), and set_magician defined as set({"Saruman", "Gandalf"}). Create a dictionary containing two pairs: one that associate the set of hobbits with the key "hobbit", and the other that associates the set of magicians with the key "magician".

Acknowledgements

I would like to thank Bruno Sartini, one of the students of the 2017/2018 course, for having suggested corrections to some typos in the text.

References

• Borges, J. L. (1941). La biblioteca de Babel. In El Jardín de senderos que se bifurcan. Editorial Sur. English translation available at http://www.arts.ucsb.edu/faculty/reese/classes/artistsbooks/The%20Library%20of%20Babel.pdf

• Foulds, J. (2017). Answer to the question "Is the Library of Babel infinite?". Quora. https://www.quora.com/Is-the-Library-of-Babel-infinite (last visited 16 November 2017)