In a typical Computer Science undergraduate programme, students take a two-course sequence in Data Structures and Algorithms (DSA). These courses build on an introductory programming course which usually offers only a light introduction to these topics (e.g., the list data structure implemented as an array, and simple algorithms such as linear search and Bubble Sort). Hence, the two-course DSA sequence is critical to help students to develop the skills necessary to create efficient algorithmic solutions to real-world problems. These skills are highly valued in industry, and the technical rounds in most job interviews evaluate these skills immediately after assessing the candidate’s basic programming proficiency. Many students, particularly in institutions outside the top tier, fail to clear these hurdles because they have not been given enough opportunity to hone these skills. In this series of articles, we describe a new approach to address these shortcomings – a Gamified Approach to Learning Algorithms (GALA). We describe our approach in the context of the Algorithms course (typically the second in the 2-course DSA sequence). Student feedback (drawn from an institution outside the top tier) confirms that this approach enables students to grasp key concepts, and to develop a better understanding of how and why the algorithm works. Following the introduction of GALA, we are also starting to see improved student performance on job interviews.
A recent report by Aspiring Minds [1] estimates that more than 90% of graduating engineers “do not have the desired programming and algorithm skills required to work in IT product companies”. Such companies expect graduates to have the ability to create an algorithmic solution to a real-world problem (and then implement this solution in code). The former task involves at least three key skills: modeling the concrete problem in abstract terms, recognizing opportunities (if any) to reduce this problem to one for which an efficient algorithm (using appropriate data structures) already exists, and (when necessary) developing an algorithm to solve this problem as efficiently as possible. Note that each of the three action verbs associated with these tasks (modeling, recognizing , and developing) are at the higher levels of Bloom’s Taxonomy. However, in many of the Data Structures and Algorithms (DSA) courses we have reviewed at institutions outside the top-tier, the emphasis is on tasks at the two lowest level of Bloom’s Taxonomy: Remembering (e.g., memorizing an algorithm or the detailed implementation of a particular data structure) and Understanding (e.g., tracing an algorithm’s behaviour on a given input, or tracing the evolution of a data structure on a given sequence of operations). As the Aspiring Minds report [1] indicates, such courses do not prepare graduates adequately for industry needs.
This series of articles describes a pedagogical approach to teaching an Algorithms course that meets two simultaneous objectives:
Institutions outside the top-tier lack many of the advantages that top-tier institutions possess. For instance, many of their students have limited language proficiency, analytical reasoning, and mathematical maturity. Further, almost no course prior to their Algorithms course hones their higher-order thinking abilities. (Even the introductory programming course tends to be syntax-heavy, and focused on skills at the two lowest levels of Bloom’s Taxonomy.) As an illustration, consider the Algorithms course taught by the first author. In the preceding introductory programming course, almost all students were able to correctly reproduce the Bubble Sort algorithm when asked. The first author reminded students of the Bubble Sort algorithm, and then asked them to use it to sort the university roll numbers of 10 students. About 80% of the class was unable to apply this algorithm to the given data (a task that is no higher than level 3 of Bloom’s Taxonomy). In the same institution, when the first author asked senior students to analyze the time complexity of the algorithm(s) implemented in their final-year project, the vast majority of students were unable to apply these skills to the given task. Such a context requires an approach that students find initially accessible yet sufficiently engaging that they are motivated to spend enough time grappling with the problem. (Tasks associated with higher levels of Bloom’s Taxonomy require students to spend time evaluating multiple possible ways of tackling them.)
Our Gamified Approach to Learning Algorithms (GALA) is designed to be both accessible and engaging. We assume a lecture of between 40 and 60 minutes, and we split this into two approximately equal parts. In Part 1 (20 to 30 minutes), students play a game that, by its design, requires interactive engagement to develop an algorithm. We ensure accessibility in two ways. First, the rules are specified using language that is as simple and unambiguous as possible. Second, wherever possible, students play the game with physical artefacts. As we shall explain, these can be created easily and inexpensively. In Part 2 (the remaining 20 to 30 minutes), the instructor explains one or more efficient algorithm to solve the problem, leveraging the student’s familiarity with and interest in the problem developed in Part 1. In many cases, the games themselves are well-known. Our contribution lies in weaving these games into a pedagogy to support desired learning outcomes in the Algorithms course.
In-class observations confirm that students find the games accessible and deeply engaging. Further, the feedback collected from our students confirms that GALA enables students to grasp key concepts, and to develop a better understanding of how and why certain algorithms work. Following the introduction of GALA, we are also starting to see improved student performance on job interviews. In the next three sections, we illustrate GALA through examples.
The purpose of this game is to help students understand the classical algorithm for converting positive integers from decimal to binary representation (Table 1) at a deeper level than a mere sequence of steps. One way to achieve this is through a formal (inductive) proof of correctness.
As we have noted above, we cannot assume that students will have the requisite mathematical maturity to fully understand (let alone develop) such a proof. Hence, the game aims to help students understand the “core” of such a proof, without using the language of induction. More importantly, the game gives students an opportunity to hone their skills in developing algorithms.
Table 1: Algorithm for converting decimal to binary
There are several versions of this game, and we first describe the rules of the simplest version (Version 1). All versions of this game are played with two players: P1P1 and P2P2. Player P1P1 has a set of 7 cards numbered C1,C2,…,C7C1,C2,…,C7, each with 64 numbers (Table 2). Player P2P2 begins the game by guessing a number NN between 1 and 127 (both inclusive) without revealing it to P1P1. Next, for each card C1,C2,…,C7C1,C2,…,C7, P1P1 asks P2P2 whether NN appears on this card. For each question, P1P1 notes P2P2’s response (yes/no). Note that P2P2 must never lie! (If P2P2 lies, at the end of game, P1P1 can easily prove that P2P2 lied). At the end, P1P1 must correctly identify the number that P2P2 had guessed based on the set of yes/no response for each card CiCi.
While a “brute force” approach is possible by carefully ruling out all numbers except one, this is clearly a tedious process. Students quickly realize that they need to come up with some clever “formula” (i.e., an algorithm!) to combine the yes/no answers into a single number that P2P2 has guessed.
Table 2: A set of 7 cards for Version 1
We split the class into groups of 4, and we give each group a full set of 7 cards. (An entire set can be printed on a single A4 sheet of paper and easily cut out.) Each member of the group is asked to take turns playing the role of P2P2, while the rest of the group plays the role of P1P1. Before proceeding further, we encourage you to pause and try the game! For example, if we play the role of P2P2 and tell you that our number appears only on cards C1,C2,C6C1,C2,C6 and C7C7, can you identify our number?
When students in a class of about 60 students (15 groups) were allowed to play this game for 15-20 minutes, only two groups were able to correctly identify an algorithm to compute the guessed number. However, neither of these groups was able to explain why their algorithm worked. Even with this limited success, each group had their “Aha!” moments. Finally, when the logic and the underlying theory was explained (in Part 2), almost the entire class was thrilled. We will now discuss the concepts involved and why the logic works.
To compute the guessed number, we should sum up the values 2i−12i−1 for each card CiCi for which P2P2 answers yes. For our example above (yes to C1,C2,C6C1,C2,C6 and C7C7), the sum is 20+21+25+26=9920+21+25+26=99. You can confirm that 99 is the only number that appears on precisely this set of four cards.
To understand why the logic works, we should refresh the theory of number representation using the underlying number base and place value of digits. For example, the decimal number 4763 corresponds to 4×103+7×102+6×101+3×1004×103+7×102+6×101+3×100. The position of the digit in the number has its corresponding place value, determined by respective power of 10 (decimal base value). Thus, in a 4-digit decimal number, place values are defined corresponding to unit place, tenth place, hundredth place and thousandth place value. The digit in each position is to be multiplied with its position-based place value and when all the values are summed, we get the number. When the number is represented in binary, the base value is taken as 2. When a number is represented using 7 binary digits, the value NN is computed as N=x726+x625+x524+x423+x322+x221+x120N=x726+x625+x524+x423+x322+x221+x120, where xixi corresponds to the ithith binary digit. The decimal number 99 in binary is written as 1100011. In this binary representation, digits x1,x2,x6x1,x2,x6 and 4x74x7 are 1, and remaining 3 binary digits x3,x4x3,x4 and x5x5 are zero. Thus, the value would be computed as,
A closer analysis of card CiCi reveals that the first number is precisely 2i−12i−1. More interestingly, every number on card CiCi contains 2i−12i−1 in its binary expansion. Thus, whenever player P2P2 responds to a card CiCi, player P1P1 learns the ithith bit of NN (yes means 1, no means 0). While this is clearly not a formal proof of correctness, understanding this key point helps students better understand why the algorithm in Table 1 works: each iteration ii of the loop is evaluating the ithith bit of NN. Of course, we can present this as a dry fact to students, and they could certainly reproduce this fact on an exam. Instead, GALA provides a much deeper learning experience: students quickly realize that there is some pattern to the numbers, and they immediately engage with trying to discover this pattern. The ability of a student to recognize patterns (or more abstractly, “properties”) is critical to their ability to develop algorithms, since algorithms exploit these patterns/properties.
To further hone this skill, a variant of the same game can be played (Version 2) using a different set of cards C′1,C′2,…,C′7C1′,C2′,…,C7′ (Table 3). In this variant, the logic is reversed: a “yes” to card C′iCi′ means that the ithith bit of NN is 00 (“no” means the bit is 1). Several other variations of the game can be played by mixing cards from these two sets – care must be taken to map yes/no answers for the two types of cards (CiCi and C′iCi′) to 1/0 bits. Cards can be printed in different colours (blue vs. orange), or students can recognize that all cards of type C′iCi′ start with the number 0. Another variant could be to use a set of 5, 6 (or N) cards instead of 7, in which case count of numbers appearing on each card would change accordingly. For example, for a set of 5 cards, each card would have 16 numbers and so on.
Table 3: A set of 7 cards for Version 2
Next, we discuss a classic game known as Euclid’s game [2][3]. Once again, our purpose is to use this game to hone student’s abilities to develop algorithms. This 2-player game requires nothing more than a sheet of paper and a pen. Player P1P1 writes down two unequal positive numbers, and player P2P2 must decide whether to make the first move or the second move. Thereafter, the two players make alternate moves as decided by P2P2. In each move, a player must write a positive number xx that satisfies two properties:
The first player who cannot write such a number xx loses the game. The algorithmic task for students is to determine a winning strategy for P2P2. In other words, students must write an algorithm whose inputs are two distinct positive integers mm and nn (the numbers written by P1P1), and whose output is 1 if P2P2 should make the first move, or 2 if P2P2 should make the second move.
We split the class into groups of 4, and we work out an example such as the following. Suppose P1P1 writes m=25m=25 and n=35n=35, and suppose P2P2 decides to make the second move. Then the game could proceed as follows:
At this point, P2P2 loses because no new number can be written. We now split students into groups of about 4 and allow them 10 minutes to come up with a winning strategy for P2P2. Most groups start (sensibly) by playing the game with the same numbers mm and nn, but with P2P2 making the first move. These groups are often able to convince themselves that no matter what numbers P1P1 writes, P2P2 can win the game. In fact, these groups recognize that no matter what choices the players make, the same numbers 5, 10, 15, 20, 25, 30 are written down when m=25m=25 and n=35n=35. At this point, we observe many groups proposing incorrect or incomplete algorithms. For instance, some groups surmise that P2P2 should make the first move when both numbers are odd and the second move when both numbers are even. We then provide counter-examples such as m=30m=30 and n=70n=70 where P2P2 must make the first move in order to win, and m=25m=25 and n=40n=40 to point out cases that students have not considered.
These counter-examples make the problem more interesting, and students continue to look for patterns in the games. Given enough time, most groups realize that the set of all numbers written on the paper (including mm and nn) can always be sorted to produce numbers of the form: a,2a,…,min(m,n),…,max(m,n)a,2a,…,min(m,n),…,max(m,n). Since all these numbers are multiples of aa, it becomes clear that a is a common factor of both mm and nn. A handful of groups realize that the number a must be the highest such common factor (also called the greatest common divisor or GCD) of mm and nn. Even groups that fail to grasp this insight on their own are able to recognize its truth when we present it to them. From this point, their task is to merely recognize that if max(m,n)=k×amax(m,n)=k×a, then P2P2 should go first if kk is odd, and P2P2 should go second otherwise.
It is useful to reflect for a few minutes on why this strategy is correct. There are kk numbers that can be written: a,2a,…,k×aa,2a,…,k×a. Since two of these numbers are mm and nn, the players can only write the remaining k–2k–2 numbers. Hence, P2P2 can guarantee a win by going first when k–2k–2 is odd (which implies that kk is odd) and going second when k–2k–2 is even.
Finally, we describe a game that can hone student’s abilities to abstractly model a simple real-life problem and also recognize the similarities between this problem and one already solved. We ask students to consider a vendor who sells milk from a large tanker. The vendor extracts milk using one of two jugs, one with capacity mm liters and another with capacity nn liters, where mm and nn are distinct positive integers. (Attentive students and the reader might start seeing connections with the previous game already!) The jugs have no intermediate markings, so the only known volumes of milk the vendor can directly measure is by filling a jug to capacity (mm liters or nn liters). We ask students to design an algorithm to give a customer exactly kk liters of milk using the two jugs, or to report that this is impossible. Note that kk must also be a positive integer.
As an example, see if you can find a solution when m=5,n=7m=5,n=7, and k=1k=1. When we present this problem to students, some of them indicate that they have seen similar puzzles before, but usually with specific numbers only (not in the general form with numbers m,n,m,n, and kk). Although this is not a 2-player (or multi-player) game, we once again ask students to work in groups with about 4 members each. Most groups, especially those in which a student has seen this type of puzzle before, quickly realize that the vendor can measure some volumes (other than mm and nn) by pouring milk from one jug to the other. Specifically, if the vendor fills the 7-liter jug to capacity from the tank, then pours the milk from this jug into the 5-liter jug until it reaches capacity, then the 7-liter jug now contains precisely 2 liters of milk. At this point, some groups recognize that the vendor has computed the difference (7 – 5 = 2) of the given numbers m=5m=5 and n=7n=7, and they sense there are similarities with Game 2.
Indeed, it is possible to precisely measure only those volumes k that are multiples of the GCD of mm and nn. In the above example, the GCD of 5 and 7 is 1, and hence it is possible to measure out 1 liter. Algorithm to compute GCD of two numbers using repeated subtraction is given in Table 5 (Appendix) and its optimized version using remainder operation is given in Table 6. To find a sequence of steps, students must create an appropriate abstract model to represent the current volume of milk in the two jugs as they pour milk in and out of them. The simplest mathematical representation is a tuple (p, q), where p represents the volume of milk in the jug with capacity mm (0≤p≤m)(0≤p≤m), and qq represents the volume of milk in the jug with capacity nn (0≤q≤n)(0≤q≤n). Students with weak mathematical maturity may not use such a concise notation, but we do observe many groups developing similar notation. We present the tuple notation when we discuss our approach in Part 2 of this exercise.
In this notation, the vendor starts with the tuple (0, 0) representing the situation where both jugs are initially empty. We now describe a sequence of steps the vendor can perform to measure 1 liter of milk for the customer. The sequence starts with these four steps: (0, 0)→→(5, 0)→→(0, 5)→→(5, 5)→→(3, 7). Thus, starting with both jugs empty, we first fill the 5-liter jug to capacity (step 1), leading to the tuple (5, 0). Then, (step 2) we transfer this milk to the 7-liter jug (0, 5), then (step 3) we again fill the 5-liter jug to capacity (5, 5). Lastly (step 4), we transfer milk from the 5-liter jug to the 7-liter jug until it reaches capacity. At this point, 2 liters of milk have been transferred, leading to the tuple (3, 7). The remaining steps are: (3, 7) →→ (3, 0) (0, 3) →→ (5, 3) →→ (1, 7). (Note that we go from (3, 7) to (3, 0) by emptying all the milk in the 7-liter jug back into the milk tanker!) At this point, the 5-liter jug contains precisely 1 liter of milk, as desired by the customer.
By allowing students enough time (about 20 minutes) to experiment with several examples, a few groups realize that they can “make progress” (i.e., measure new volumes of milk) using a systematic process which lies at the heart of the solution (i.e., the while-loop) shown in Table 4. Note that we are assuming that m<nm
Table 4: Algorithm for Game 3
When we discuss our approach, we work out several examples using the tuple notation to help students model the problem and start seeing the pattern. We also point out the similarities between Games 2 and 3. By pouring milk from one jug to another (Game 3), we are essentially computing the same differences that we saw in Game 2. Although this idea can be made more precise, we do not delve into these connections here. In a later article, we will present examples of games where we highlight the connection between two games to demonstrate the powerful idea of reduction.
We have found the GALA approach effective in maintaining student engagement in classes of more than 50 students, both during the initial game-play (Part 1) and during the subsequent explanations (Part 2). Student feedback on this approach is consistently positive, and students demonstrate greater confidence in attacking algorithmic design challenges.
As an instructor, you may wonder whether this approach can be applied to “all algorithms in the syllabus”. We have found that GALA is useful for only a few algorithms, so it cannot be applied wholesale for all topics in a typical Algorithms course. Nevertheless, as we will demonstrate over the next few articles, it can be used to enhance student learning for several interesting algorithms.
Table 5: Algorithm for computing GCD using repeated subtraction
Table 6: Algorithm for computing GCD using remainder
[1] Aspiring Minds, “National Employablity Report – Engineers Annual Report 2019”,
https://www.aspiringminds.com/wp-content/uploads/2019/05/NER\_Engineer\_2019-V5}, last accessed March 2021
[2] Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 2ndnd edition, Pearson Education.
[3] Alexander Bogomolny, “Interactive Mathematics Miscellany and Puzzles”,
http://www.cut-the-knot.org/blue/EuclidAlg.shtml, last acchessed March 2021.
