Keywords

1 Introduction

The classic book Computer Science Unplugged [4] includes activities, games, and puzzles suitable for people of all ages and backgrounds to communicate fundamental concepts of computer science without the help of a computer. A quintessential activity of CS Unplugged, conceived by Mike Fellows in the late 1980s [3], is to use a sorting network (often with 6 input nodes) drawn on the ground, where participants hold cards with numbers (or other linearly ordered objects) and perform the sorting represented by the sorting network by stepping from node to node. At the beginning, the participants stand on the input nodes of the sorting network, and after a signal to start, they work through the network until they arrive at the output nodes holding their cards in an ordered sequence. The elementary step performed throughout the activity occurs when a pair of participants arrive together at a comparator node, and according to the relative ordering of the two cards they hold, the one with the smaller number continues to the next node via the minor edge, and one with the higher number continues to the next node via the major edge. Which edge is minor or major can be indicated by the color and/or thickness of the edge.

Figure 1 shows a simple example of a sorting performed on a sorting network. We refer to this activity as a human sorting network, or HSN, and to the participants as players.

Fig. 1.
figure 1

Five snappshots of the sorting performed on a sorting network with 4 input nodes. Major edges are indicated by thick lines. All edges are assumed to be directed from top to bottom, also in other illustrations below.

Full size image

This activity has shown to be quite successful, educational meaningful, and fun. By choosing the right type of objects to be sorted, the activity can be adjusted to the age or proficiency of the players: one-digit or 3-digit numbers, words to be sorted lexicographically, or even very domain-specific objects (see Sect. 4).

In this paper, we report on two extensions of the basic HSN activity. Our objective is to encourage educators to organize simlar events, and by laying out our experience to provide useful information.

In Sect. 3, we report on a large HSN with 50 input nodes that we realized with school classes in Vienna, explaining the challenges, technical consideration, implementation, and the overall experience. In Sect. 4, we report on the use of two small HSNs laid out next to each other, which supports the race of two groups of players and elevates engagement. In Sect. 5, we discuss extensions of these two activities that would be interesting to pursue in the future, and conclude in Sect. 6.

We hope that this report will encourage educators to organize similar events and that our experience and considerations will be useful for such endeavors.

2 Sorting Network Theory

Sorting networks are data-oblivious sorting algorithms, meaning that the sequence of comparisons performed is not influenced by the input list. This characteristic makes them ideal for implementation in hardware circuits, where the size determines the number of gates required and the depth determines the circuit’s delay, but sorting networks are also used for propositional encodings of cardinality constraints [6]. Knuth [7] and Parberry [8] provide comprehensive overviews of sorting networks.

Sorting networks are often depicted as Knuth diagrams that show parallel lines, called channels, instead of input nodes, and lines connecting channels representing comparator nodes. Figure 2 shows the sorting network of Fig. 1, both as a directed acyclic graph and as a Knuth diagram.

Fig. 2.
figure 2

Left: sorting network from Fig. 1 as a directed acyclic graph. Right: the same sorting network as a Knuth diagram.

Full size image

Comparator nodes that do not depend on each other can be executed in parallel and are therefore combined into layers. The depth of a sorting network is its number of layers, which equals to the largest number of comparator nodes that lie on a path from an input node to an output node, hence the depth is also called the delay time of the network. For instance, the sorting network in Fig. 2 has depth 3. The size of a sorting network refers to its number of comparator nodes. Since the introduction of sorting networks, researchers have been seeking to construct sorting networks, aiming at minimal depth and minimal size networks. Asymptotically, there exist sorting networks of logarithmic depth and size \(O(n \log (n))\) for n input nodes [1, 9, 10]. However, the constants hidden in the asymptotic expression are huge, so that in any practical setting, one rather resorts to other constructions, like Batcher’s bionic sorting networks [2] of depth \(O(\log ^2(n))\) and size \(O(n\log ^2(n))\). The very simple odd-even transposition sorting networks [7], on the other hand, have depth n and size \(n(n-1/2)\). Optimal networks are only known for a small number of inputsFootnote 1 as one needs to exhaustively search a quickly growing search space. Interestingly, for \(n\le 11\), there exist sorting networks that are simultanously of minimial depth and minimal size, for \(n\ge 12\) one needs to decide which of the two measures one wants to minimize.

3 A Giant HSN

To stimulate public awareness of algorithmic thinking and create an engaging team project for high school students, we implemented a large-scale HSN with 50 input nodes in Vienna, Austria, in September 2018. This ambitious endeavor presented several unique challenges in terms of logistics, design, and coordination. In this section, we outline the key considerations and solutions we developed to successfully realize this giant HSN. We provide sufficient detail to make this event reproducible.

Fig. 3.
figure 3

Photos from the giant HSN event in Vienna.

Full size image
Fig. 4.
figure 4

Left: Odd-even transposition network with 8 input nodes and color coding; input nodes are on the top, output nodes on the bottom, and edges are directed top-down. Right: the same network drawn without edges.

Full size image
  1. 1.

    The location for setting up the HSN needs to be sufficiently large, ideally with paved ground, easily accessible by public transport, and providing facilities like lockers and washrooms for the participants. After location scouting in Vienna, we settled on the free space next to a large sports stadium.

  2. 2.

    We invited about eighty high school students from the region, mostly from the age group 14–16, to participate in the event which included helping to set up the network and performing as players.

  3. 3.

    For the timing, we planned the event to fit into one day, including set up and removal. This way, we only needed to rent the space for one day, and the participating students required only one day out of school. A day in September, just after school starts, with expected warm weather, seemed a good choice.

  4. 4.

    The total length of all the edges would be several miles; hence, drawing edges would be too time-consuming and challenging to clean up afterward. Hence, we decided on an edgeless network layout.

  5. 5.

    For the nodes, we used ceramic square tiles, size \(34 \times 34\) cm, in different colors, which are placed on the ground and can easily be picked up afterwards without any residue to clean, making the setup even weatherproof.

  6. 6.

    We used an odd-even transposition sorting network (see Sect. 2) so that all the comparator nodes can be placed along a rectangular grid. Moving from one transition node to the next, the player only needs to move to an adjacent grid layer, where the larger number moves left and the smaller number moves right. Figure 4 shows such a network with 8 input nodes, once with edges drawn and once edgeless.

  7. 7.

    To provide additional orientation so that players do not get lost, we applied a color coding to the comparators nodes: the larger number stays on the same color, the smaller number doesn’t (unless the left or right border of the network is reached), see Fig. 4.

  8. 8.

    For the dimensions, we opted for a distance of 70 cm between adjacent input nodes and 60 cm between adjacent layers. This allowed us to fit a network with 50 input nodes in the space available at the venue.

  9. 9.

    For setting up the network, we used a rope with markers placed every 70 cm so that two helpers were stretching the rope across the area and several helpers could place the ceramic tiles along the rope; once done, the rope was moved to the next layer, and this was repeated until all layers where set up. This way, all tiles could be placed within an hour of teamwork. A megaphone proved to be useful for coordination.

We had the tiles delivered the day before the event. On the day of the event, a small team started tracing out the network outline and preparing the measuring rope. When the students arrived, we started to place the tiles. The entire setup was accomplished within about two hours. Then, we gave some instructions on the sorting process and did some demonstrations on a small part of the network with edges indicated by chalk. We already had some instruction sessions with the students at their schools a few days prior. Then, we proceeded to the actual sorting with all 50 numbers.

The first two runs produced some mistakes; the third run went smoothly and reasonably fast. We repeated once more so that everybody could participate as a player at least once. On the reverse side of each sorting card, we printed a letter so that after the sorting was completed, we issued a command to all players to reveal the reverse side of their cards, which displayed a message (see Fig. 3).

Although this activity retains the learning objectives of the original HSN activity, the increased scale of the network provides an excellent basis for discussing the topic of algorithm efficiency with the students. In addition to the educational purpose, a giant HSN activity opens an excellent channel for communicating the topic of algorithms to the general public.

For documentation, we had a photographer and a videographer team present, who captured the setting up of the network and the sorting activity. A video documentation is available at YouTubeFootnote 2 and ZenodoFootnote 3. We consider the event successful based on the positive feedback from the participating students and their teachers; for any similar events in the future, we recommend a more systematic gathering of feedback with questionnaires. Since the event was featured in several Austrian newspapers, it helped to raise public awareness on the importance of the subject.

4 Parallel HSNs

After organizing several events with participants from different age groups, using a 6-input HSN, we observed that a race character can improve the overall experience and engagement. The participants are divided into groups of six, then the time is recorded for each group completing the sorting, the fastest group wins.

We realized that performing the race in parallel with two sorting networks is more fun so that time-tracking is not necessary. This way, one can have a tournament where pairs of groups compete with each other, while retaining the learning objectives of the single-network HSN activity.

To this aim, we replaced our improvised sorting network drawn with colored tape on a tarp with two identical networks professionally printed. We found a company specialized in printing large advertisement banners. Banners of width 310cm and arbitrary length can be ordered.

We designed several variants of sorting networks (with minimal size and depth) as shown in Fig. 5, with 6–8 input nodes. We settled on the one with 6 input nodes. Minor and major edges are distinguished by color and by the width of the line; it is easy to memorize “smaller number—thin line, larger number—thick line.”

Fig. 5.
figure 5

Templates for HSNs with 6, 7 and 8 input nodes.

Full size image

We note that the logical structure of a sorting network does not determine the way it is drawn. In fact, it is a nontrivial task to find a drawing that, for instance, minimizes the number of crossings or the distance between adjacent nodes. For a drawing of a sorting network one would require that all input nodes, output nodes, and comparator nodes of the same level, are placed along a line, respectively. But only the output nodes are required to appear in sorted progression, for the other nodes, any permutation is admissible, hence the total number of possibilities is exponential.

We organized HSN races with the two parallel networks on several occasions. Recently, the parallel networks were part of an activity at the FPT FestFootnote 4 in Bergen, Norway. Since most of the participants were researchers in parameterized complexity [5], we printed parameterized complexity classes

figure a

linearly ordered by set inclusion, on the sorting cards. This is just one example on how an HSN activity can be adjusted to a special group of participants (Fig. 6).

Fig. 6.
figure 6

Mike Fellows conducts a sorting race with two parallel sorting networks at the FPT Fest in Bergen, 2023.

Full size image

5 Future Work

As discussed above, we chose the simple odd-even transposition sorting network for the giant HSN because of its grid-like layout, so an edgeless drawing was still working. This choice is somewhat unsatisfactory from the computer science perspective, given the existence of significantly more efficient sorting networks of smaller depth and size (see Sect. 2). Therefore, we propose an approach that allows us to use more efficient sorting networks for a large HSN based on an edgeless drawing for future HSN events.

Fig. 7.
figure 7

Left: an optimal sorting network for 8 input nodes. Right: an edgeless drawing of the network using annotations.

Full size image

The idea is to place the comparator nodes on a grid and annotate them with coordinates \((\ell ,i)\) where \(\ell \) is the level and i the index within the level, and with the coordinates of the successor nodes via the minor and the major edge, \((\ell ',i')\) and \((\ell '',i'')\), respectively, possibly drawn as follows:

figure b

Output nodes are referred to by their index. Figure 7 shows an example of a sorting network with 8 input nodes with the smallest possible depth of 6. Already here, the reduction in depth by 2 compared to the odd-even transposition sorting network, as displayed in Fig. 4, will compensate for the more difficult task for the players to find and proceed to the next node; for a larger number of inputs, this reduction is even more pronounced.

Indeed, it might be exciting to have in parallel two large sorting networks with, say, 50 input nodes each, one based on the odd-even transposition sorting and one based on Batcher’s bionic sorting, and to conduct a race. This could provide a strong educational effect on the value of designing efficient algorithms.

For the drawing of a given sorting network that works well as an HSN, it is essential to keep the edges short, so that during the sorting, the players do not need to cover long distances when moving from one node to the next. As mentioned above, finding such a drawing is an interesting optimization problem on its own, and could be solved together with the participating students at workshops to be held before the actual sorting event.

6 Conclusion

The extensions to the Human Sorting Network (HSN) activity presented in this paper demonstrate the versatility and scalability of this educational tool. The large-scale 50-input HSN successfully engaged high school students in a collaborative, full-day event that brought algorithmic concepts to life on a grand scale. This implementation showcased the potential for adapting sorting networks to create impactful public events that promote computer science awareness.

The parallel HSN setup, on the other hand, introduces a competitive element that enhances engagement and allows for tournament-style activities. This variant has proven effective across various age groups and can be easily customized for specific audiences, as demonstrated by its use with parameterized complexity classes at a research conference. Both extensions offer valuable lessons for educators and researchers looking to expand the reach and impact of CS Unplugged activities. These innovations in HSN activities offer several benefits:

  1. 1.

    They provide hands-on experience with algorithmic concepts for a wide range of participants, from children to adults.

  2. 2.

    They foster teamwork and collaborative problem-solving.

  3. 3.

    They can be adapted to different contexts and knowledge levels.

  4. 4.

    They create opportunities for public outreach and raising awareness about computer science concepts.

By sharing our experiences and methodologies, we hope to inspire further innovations in hands-on computer science education and contribute to the ongoing effort to make algorithmic thinking accessible and engaging for diverse audiences.

Future work could explore more efficient network layouts for large-scale HSNs and investigate the educational outcomes of these extended activities compared to the traditional HSN setup.