Seite 119 [119]
118 11 MULTIDIMENSIONAL EXPANSION OF THE ALGORYTHMICS...
Linear search algorithms check, successively, every element of a list for the
one that eguals the value we are looking for (target key). Binary searches repeat¬
edly target the middle element of an ordered list reducing the search space by
half after each step. We have chosen to illustrate the linear and binary searching
strategies by flamenco dance choreographies (see figures 11.2-3). The list to be
searched could be represented by a flamenco dancer sequence (women) and the
target key by an extra dancer (man; the protagonist of the performance). Since
each dancer wears the corresponding value on his/her back, these are not visible
in the case of list elements but are visible on the back of the target key.
In the case of linear searching, the result of the comparison operation be¬
tween the target key and the current element of the searched list is yes (equal)
or no (not equal). These yes/no comparisons could be illustrated by pieces of
choreographies where the two dancers are dancing identically/differently (see
Figure 11.2). In the case of binary searching, comparison operations result in one
of the following three possibilities: less/greater/equal. To illustrate these variants,
the corresponding dance couple could follow the same piece of choreography
but in a slower/faster/in-synchrony rhythm (see Figure 11.3).
Backtracking can be seen as an advanced searching strategy. It is a pro¬
gramming strategy for finding all (or some) solutions to a given computational
problem that incrementally builds solutions and immediately abandons all those
partial solutions that evidently cannot be completed to a valid final solution.
The classic backtracking example is the so-called “eight queens puzzle”, which
asks for all valid arrangements of eight chess queens on a chessboard (no queen
attacks any other). We chose to illustrate the recursive version of the four-queen
variant of this classic backtracking algorithm by classic ballet choreography
(see Figure 11.4). The following pieces of choreographies are attached to each
ballerina:
— The queen comes to life on cell 0 of her row (new recursive call).
— The queen dies on cell 5 of her row (the current recursive call ends).
— The queen goes into “hibernation mode” (the current call is suspended;
a new one begins at the next row).
— The queen comes back from the “hibernation mode” (the suspended call
from the previous row continues).
— The current queen moves to the next cell of her row.
— The current queen successively considers those queens that hibernate on
previous rows.
e These ones temporally wake up for a “pair of mutually attacking”/“pair
of mutually non-attacking” dance.
Additionally, four-queen “victory dances” illustrate the two valid solutions.