Radix Sort and Story Cards

Year: 2023 Authors: Manish Jain; Neha Garg

Core claim

Punched story cards and skewer-based sorting can concretely demonstrate Radix sort, binary and ternary number representation, and computational thinking.

Topics

Radix sort, computational thinking, binary representation, ternary representation, tangible learning

Domains

sorting algorithms, number systems, binary, ternary, discrete mathematics, educational design, story cards, tangible interface

Methods

punched-card construction, skewer sorting, classroom activity, workshop demonstration, design iteration

Media

cards, punches, slit markings, skewer, needle

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2023 Conference Proceedings

Radix Sort and Story Cards

Manish Jain¹ and Neha Garg²

Center for Creative Learning, IIT Gandhinagar, India ¹manish.jain@iitgn.ac.in, ²neha.g@iitgn.ac.in

Abstract

In this paper, we describe a tangible recreational activity that can instantiate computational thinking. In order to demonstrate a sequencing algorithm, we developed a set of story cards that can be sorted using a binary-based Radix sort. Each card has a set of punched markings that represent the assigned position of the card in the story sequence. On passing a skewer through the cards one-by-one, they can be sorted. This idea is extended to ternary representations using three different kinds of markings on the cards. This activity helps to demonstrate both the algorithm and the representation of numbers in Binary and Ternary in a tangible and accessible manner for students.

Introduction

Computing has become an integral part of today’s education system. In recent years, there has been a dramatic shift from the focus on computer science to a broader perspective on computational thinking (CT), which is less about technology but more about a way of thinking and solving problems - “a fundamental skill for everyone, not just computer scientists”, in the words of Jeanette Wing, author of a seminal article on CT [10]. In an effort to retain the emphasis on computational thinking rather than computing, researchers have designed several analog (see for instance [6][7]) or “unplugged” [3] activities whose goal is to demonstrate computational thinking without computers.

At the Center for Creative Learning, our aim is to encourage computational thinking among school and university students across a country where computer access is limited. Even with the presence of computers, the concepts of algorithms being abstract and intangible, are difficult for students to grasp. Thus our center aims to leverage the benefits of tangibility to demonstrate the traditionally virtual algorithms and their underlying concepts using a simple analog activity. In this paper, we present a recreational activity using punched cards that demonstrates a binary-based sorting algorithm, the Radix sort. While the concept of punched cards dates back to the pre-PC times when they were used to collect census data, maintain personal databases, and library catalogs [4][8], our intent was to take it into classrooms and give it an educational context. Thus, in the following sections, we first briefly explain the algorithm and then elaborate on a few activities based on it.

The Binary Radix Sort and its Extension to Ternary

A sorting algorithm arranges the elements of a list in an order and there are different classes of sorting algorithms. The punched cards used for our activities are based on Radix sort, which is a non-comparative sorting algorithm. It arranges the elements in order by relatively sorting each bit. In a number with more than one significant digit, the sorting begins with the least significant digit. The algorithm groups the individual digits at the same place value, arranges them in order, and continues the process until all the digits have been considered. The numbers are thus arranged in an increasing order.

Our goal was to identify ways to integrate this algorithm with recreational games and activities that could be taken into the classrooms to make them fun and engaging. Below, we share the design process of our binary number system based punched cards to be sorted in order and then extend the algorithm to the ternary number system.

We created 26 cards with the letters of the English alphabet written on them [1][2][5]. The task was to arrange the cards in ascending order using Radix Algorithm. To facilitate this, we punched the cards with

Jain and Garg

two different types of markings: a hole and a slit (Figure 1), in a fixed configuration (Figure 2) and a skewer was used to pass through the two markings and sort the cards.

(a)

(b)

(c)

(d)

(e)

Figure 1: Steps to make the markings (a) Punch the holes on the first card using the punching machine (b) Use the first card as stencil and trace holes on the second card (c) Extend the circle to slit using two straight lines (d) Punch holes on the second card (e) Use scissors to make slit Figure 2: Cards A-Z with their respective positions in binary numbers

As can be seen in Figure 2, each card has been punched with 5 markings and there are two different types of markings: the slit and the hole which relate to the states of on (1) and off (0) respectively. These markings correspond to the binary representation of the number of the card in alphabetical sequence. Further, each marking can either be 0 or 1, thus the number of elements that can be represented by 5 markings is $2^5=32$ . Therefore, to represent 26 letters, we punched 5 markings of two different types.

As the skewer is passed through the first marking from the right (Figure 3), the cards with the hole (0) get stuck in the skewer and are brought in front. This brings all the cards with 0 at the rightmost marking in front of the cards with 1. In the next step, the skewer is passed through the second marking and the same process continues with every bit being relatively sorted with respect to the previous one until we get the desired order.

(a)

(b)

(c) Figure 3: Sequence of inserting the skewer: (a) Start inserting from the right most hole (b) Bring the cards stuck in the skewer in the front (c) Move to the next right hole (d) Continue through all the 5 holes.

(d)

Conducting the Activity

To introduce the activity to the students, we first demonstrate the sorting of the cards using the skewer in an effort to trigger their interest. Once the result makes them curious, we introduce them to the logic of the sort. The activity paves the way for further questions like:

Radix Sort and Story Cards

• If the cards are to be sorted in descending order, what should be the order of passing the skewer through the markings?
• How many holes would you need to make cards of the alphabets of your regional language?
• If you have to bring a particular letter from the whole deck in the front, what algorithm would you apply?

These questions allow the students to think of the steps to be performed to get the desired outcome and thus develop computational and algorithmic thinking. Further, we also explored other educational scenarios for the use of these cards in the classroom. A set of 52 cards retelling an Indian mythological epic, the Ramayana [9] (Figure 4), cards depicting the Indian Freedom Struggle, and the Periodic Table have been developed. This activity has proved especially useful to make curricular concepts engaging by integrating maths, computer science, and the particular subject. These cards have also been used in teacher training workshops conducted by our center.

Figure 4: The set of 52 Ramayana cards

Another possible use of such cards could be in the literary arts. While teaching the importance of sequence in narrative arc, students could be encouraged to sketch key events on the punched cards depicting a story. Further, they could try different arrangements of the events to get different narrative arcs, which will show the effect of change in sequence of the cards on the narrative structure. Returning to the originally selected order can be easily achieved by following the algorithm.

While preparing the cards for Ramayana, we created 6 holes which are hard to position on cards that can easily fit in the hand of a child. Increase in the number of holes gave rise to the question - is there a way to decrease the number of holes by increasing the types of holes used? We were moving towards the ternary number system and to explore the idea, we created three different markings (Figure 5) to represent the three numbers 0, 1, and 2 and two different sticks of unlike thickness to pass through the markings. The difference in the thickness of the stick allows the cards with half slit to only stick in the needle while the skewer picks up cards both with the half slit and the hole.

As each marking (hole, half slit, and full slit) represents 3 numbers (0,1, and 2) respectively, we can now represent $3^{\mathrm{n}}$ numbers where $\mathfrak{n}=$ number of markings. So, for 52 cards, we punched 4 markings and mapped the position of each card to their ternary representation. Now for sorting the cards, we first passed the skewer through the first marking from the right and lifted the stuck cards forward. We then passed the needle through the same marking and brought the lifted cards forward. In this manner, the cards with the digit 0 assembled before 1 and those with 1 before 2. We also explored the possibility of any change if the order of the sticks being used was changed. However, the order does not matter and whichever way the sticks are being used, the algorithm worked. In comparison to the binary system, the number of times the sticks were being passed through the holes had increased but the number of holes had decreased.

Jain and Garg

Figure 5: The three different markings representing the three digits and the sticks of unlike thickness used for sorting through the ternary system

Summary and Conclusions

In this paper, we present a series of card sorting activities that can be used to illustrate concepts of binary and ternary representations, and sorting algorithms. This activity has shown potential to introduce the students to computational thinking, concretely, to the understanding of an algorithm and its design for a particular sorting task. Integrating this with curricula by creating cards for historical, mythological, or sequential events can bring excitement in the classrooms and make learning fun. We have tried these activities with our participants in various workshops and online sessions. Preliminary anecdotal evidence suggests that students enjoyed the activity, were engaged throughout the session, and that this can be a useful approach to bridge Mathematics with other disciplines. As an extension, the team at Center for Creative Learning has been working to explore the number of arrangements of letters of the English alphabet that can be obtained by passing the sticks through the hole in any order. We also plan to empirically measure the benefits of such activities in learning.

Acknowledgements

Thanks to the entire team of Center for Creative Learning and in particular- Jay Thakkar, Pankaj Godara, and Dinesh Rathod for the research involved in the extension of binary to ternary number system and the design of the cards.

References

[1] T. Bell, I. H. Witten, and M. Fellows. Computer Science Unplugged, 2015 https://classic.csunplugged.org/documents/books/english/CSUnplugged_OS_2015_v3.1.pdf [2] Cut Out Fold Up. https://www.cutoutfoldup.com/402-self-sorting-cards.php [3] CS Unplugged. https://www.csunplugged.org/en/ [4] Edge-Notched Cards. https://youtu.be/v8qHPXPnQps [5] M. Gardner. “The Binary System.” New Mathematical Diversions (Chapter-1), The Mathematical Association of America, 1995. [6] S. Goyal, P. Kalita, C. Monga, and R. S. Vijay. “Code bits: An Inexpensive Tangible Computational Thinking Toolkit for K-12 Curriculum.” In Proceedings of the TEI’16: Tenth International Conference on Tangible, Embedded, and Embodied Interaction, 2016, pp. 441-447. [7] Z. Liu, D. Wang, and T. Wang. “A Tangible Programming Tool for Children to Cultivate Computational Thinking.” The Scientific World Journal, 2014. [8] Punched Cards. https://en.wikipedia.org/wiki/Punched_card [9] Ramayana. https://en.wikipedia.org/wiki/Ramayana [10] J. M. Wing. “Computational Thinking.” Communications of the ACM, 49(3), pp. 33-35, 2006.