Abstract

These lecture notes introduce the last kind of algorithms of the course, i.e. the greedy algorithms. The historic hero introduced in these notes is Adriano Olivetti, who was one of the most important innovators in the field of typewriting and electronic computers.

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: Adriano Olivetti

Adriano Olivetti (shown in Figure 1) was an engineer and entrepreneur, who was a son of Camillo Olivetti, the founder of the company named after him. He was known all over the world for being the manufacturer of Olivetti typewriters, calculators, and computers.

His idea of company profits was (and still is) very distinctive since he believed that all such profits had to be reinvested for the benefits of the society at large. This utopic idea of management was personally tested by him in his company, where he decreased the working hours, increased the salaries, and transformed the company space in a lively and comfortable environment for all the employees and the related families. In fact, the main Olivetti campus included a nursery school, a library for the employees, and other additional services for making the life of the people working in the company sustainable and enjoyable.

After his death, his heritage and vision have been continued by his son, Roberto Olivetti. Among the most important items produced during Roberto Olivetti's leadership, there were several typewriters, such as the Olivetti Lettera 32 shown in Figure 2, and in particular the in the first desktop computer in the whole history, i.e. the Programma 101 (shown in Figure 3). For that period, the Programma 101 was a very cheap programmable electronic computer, that could be placed and used easily on a common desk, while the other computers of that age were quite expansive and very huge in terms of physical infrastructure. Programma 101 could be programmed by a programming language very similar to the Assembly. Its simplicity of use was one of the main reason for being so much appreciated (and sold) in the United States for personal and scientific uses as well (e.g. see [1]) – it is worth mentioning that even the NASA had used it to plan the Apollo 11 landing on the Moon.

Greedy algorithms

A greedy algorithm is an approach that, at every stage of execution of a particular algorithm where we are seeking for possible candidates for constructing the solution to a computational problem, makes always the choice that is optimal (i.e. the best one) at that particular moment. For certain kinds of problems, this behaviour allows us to reach the best possible solution to the computational problem in consideration. For instance, if you have to determine the minimum number of euro coins needed for making a change, then a greedy algorithm will return even an optimal solution overall:

1. consider the coins to choose for the change as ordered in a decrescent way, from the highest value (i.e. 2 euros) to the lowest one (i.e. 1 cent);

2. for each kind of value, add in the candidate set of the solution as much coins of that value as possible until their sum is lesser than the remaining of the change to give;

3. if the change value is reached, return it.

However, sometimes it is possible that the solution found, while it provides a correct solution to the problem, is just a sub-optimal solution. For instance, driving from Florence to Bologna, we can encounter a crossroad with two signs indicating two different routes to get to Bologna. The left route allows us to get to Bologna by travelling for 42 kilometres. On the other hand, the right route allows us to get to Bologna by travelling for 56 kilometres. A pure greedy approach would select the left route since at the moment seems the most convenient scenario. However, the approach does not predict the existence of possible traffic in the left road and, consequently, it would be possible to arrive in Bologna even after a car that takes the right route.

There are two main characteristics that a computational problem should show so as to be sure that the application of a greedy approach will bring to an optimal solution to the problem. The first one is that the greedy choice property should be guaranteed. This property means that, at a certain step, we can choose the best candidate for improving the set of candidates bringing to a solution.

The other characteristic is that the problem as an optimal substructure. This means that the optimal solution to a computational problem can be built by considering the optimal solutions to its subproblems. For instance, the previous example of the travel from Florence to Bologna does not have an optimal substructure because there can be accidents that are encountered because an optimal subsolution has been taken at certain point.

Line wrap

Understanding where to break a line in a page, i.e. line wrap, is one of the most simple and relevant problems one has to tackle when dealing with documents, either in print or digital forms. For instance, when a person is using a typewriter for writing a document, at a certain point, after she has written a bunch of characters, there is a mandatory action to take which is the carriage and return operation, that is performed mechanically on the typewriter itself. Basically speaking, when the writer notices that the page has no more space for imprinting a new word on that line, the configuration of the typewriter is initialised again in order to start from the very beginning of the left border but in the following line.

In modern tools, such as wordprocessors, the line wrap is totally handled by an algorithm that takes care of choosing when there is enough space to put that word in the current line. Generally speaking, we can describe the problem in the following manner:

Computational problem: break a text into lines such that it will fit in the available width of a page.

A greedy approach is very efficient and effective for addressing the aforementioned computational problem. It would proceed as follows:

1. For each word in the input text, see if there is enough space in the line for adding that word;

2. If there is space, add the word to the line; otherwise,

3. Declare finished the current line, and add the word as the first token of the following line.

In order to implement this algorithm, we need to introduce two ancillary methods for strings, in particular for tokenising and recomposing strings. The first of these methods is ​<string>.split(<string_separator>). This method allows us to separate the string executing it according to a specific set of characters the string may contain, specified by the parameter ​<string_separator>. For instance, if we have the variable my_string assigned to "a b c", the execution of the aforementioned method, i.e. my_string.split(" "), returns the following list: ["a", "b", "c"].

The other method we need, i.e. ​<string_separator>.join(<list_of_strings>), implements the opposite operation, i.e. it would be able to concatenate the string in a list again, according to a particular sequence of characters. For instance, if we have the list my_list = ["a", "b", "c"], the execution of the aforementioned method, i.e. ​" ".join(my_list), returns the following string: "a b c".

We now have all the ingredients for implementing our algorithm for the line-wrap. In particular, it is introduced in Listing 1. 

def line_wrap(text, line_width):
    result = []  # the list of all the lines of a document

    space_left = line_width  # the maximum available space per a specific line 
    line = []  # the current line that is built

    for word in text.split(" "):
        word_len = len(word)

        if word_len + 1 > space_left:  # we consider the length of the word plus one space character
            result.append(" ".join(line))
            line = [word]
            space_left = line_width - word_len
        else:
            line.append(word)
            space_left = space_left - word_len + 1

    result.append(" ".join(line))  # we add the remaning line to the document

    return "\n".join(result)​

Exercises

1. Implement the informal algorithm introduced in Section 2 for returning the minimum amount of coins for a change. 

References

• Hardt, J. (1972). A Computer Program for Calculating Blood Acid-Base Parameters on an Olivetti "Programma 101" Desk Computer. Clinical Chemistry, 18 (7): 658-661. http://clinchem.aaccjnls.org/content/18/7/658/tab-article-info (last visited 15 December 2017)