Home > Algorithm 2 > GAMIFIED APPROACH TO LEARN ALGORITHMS – Exploring Basics of Algorithmic Approach

GAMIFIED APPROACH TO LEARN ALGORITHMS – Exploring Basics of Algorithmic Approach

1 Introduction

The two-course sequence in Data Structures and Algorithms (DSA) in a typical Computer Science undergraduate programme assumes that students have some maturity in mathematical and computational thinking. At most institutions outside the top-tier, however, the majority of students struggle with basic skills such as manipulating inequalities and expressing algorithms that they know (e.g., determining whether a given integer N is prime or not) in some executable form (code or even pseudocode). As an example, when the first author asked second-year (and some third-year) students in his algorithms class to provide an algorithm for determining whether N is prime or not, the majority of the class proposed: “Check if N is divisible by 2, 3, 5 or 7. If yes, N is not prime, else it is prime.” We express this heuristic in pseudocode as follows (here % is the modulus operator):

Heuristic(N)

if (N % 2 == 0) or (N % 3 == 0) or (N % 5 == 0) or (N % 7 == 0)

return Not_Prime

else

return Prime

It is possible that this heuristic was adequate for some students at the school level because they were only asked to test small values of N for primality. Indeed, when students were presented N = 143 or N = 221, several initially stated that these numbers were prime. When informed that 143 = 11 × 13 and 221 = 13 × 17, their immediate approach to fixing the above algorithm was to add additional checks to the if-condition: … or (N % 11 == 0), etc. Based on our collective teaching experience at multiple institutions outside the top-tier, we have no reason to believe that this group of students was unusually poor in their mathematical and computational thinking abilities. The recommendations of the National Education Policy (NEP 2020)[1] may, in time, provide school students with greater opportunities to hone these abilities. For the foreseeable future, however, we believe it is reasonable to expect many students will lack these abilities. Our Gamified Approach to Learning Algorithms (GALA) seeks to engage such students in the DSA courses by helping them overcome these deficiencies. This article builds on our previous article [2] and further demonstrates the GALA approach in two ways. First, we use games and puzzles to concretely demonstrate abstract mathematical insights that can lead to more efficient algorithms. Second, we use the GALA approach to motivate the study of problems that might initially seem uninteresting, but are valuable from a pedagogical perspective. We illustrate our ideas using examples from primality testing and properties of Fibonacci numbers, since most computing curricula expose students to these concepts.

Puzzle 1: Rectangular arrangements

A classical interpretation of factorizing an integer N as p × q is rearranging a single row of N blocks as a rectangle with p rows, each containing q blocks. For example, factorizing 33 as 3 × 11 is shown in Table 1. A prime number is an integer N ≥ 2 for which only the two trivial rectangular arrangements (1 row of N blocks, and N rows of 1 block) are possible.

Table 1: A rectangular arrangement of 33 blocks as 3 × 11 blocks

image

To help students develop an algorithmic solution for testing primality (i.e., beyond the heuristic of testing divisibility by a small set of integers), we present the rectangular arrangements task as a puzzle, starting with N = 33 blocks. We observe that most students are able to articulate one of the two correct solutions (3 × 11 or 11 × 3) quite easily. Next, we present N = 35 blocks and ask students to “think of a solution in small steps”, starting with trying a rectangular arrangement with 2 rows. Most students recognize that such an arrangement will leave one block unused because N is odd. Thereafter, students typically try an arrangement with 3 rows (which fails) before successfully finding an arrangement with 5 rows (Table 2). (A few students also try an arrangement with 4 rows, failing to recognize that this is unnecessary.)

Table 2: An unsuccessful 3-row arrangement (left) and a successful 5-row arrangement (right) with N = 35 blocks

image image

Finally, we present N = 37 blocks. Most students try out various unsuccessful rectangular arrangements (Table 3) before realizing that no arrangement is possible. In the subsequent discussion, we articulate two key points. First, we assert that no non-trivial rectangular arrangements exist precisely when N is prime. (Note that our three tasks have prepared students to accept this fact via inductive generalization – we believe that providing a deductive proof at this stage can be detrimental to understanding the overall algorithm for many of our students.) Second, we point out similarities between certain pairs of attempts. For instance, we represent the top-right arrangement in Table 3 (which has 5 rows) as 37 = 5 × 7 + 2 and the bottom-left arrangement (with 7 rows) as 37 = 7 × 5 + 2.

Table 3: Unsuccessful rectangular arrangements with N = 37 blocks

image image
image image

This typically triggers a discussion where students recognize a symmetry that can be exploited for improved efficiency: if it is impossible to create a p-row arrangement for N blocks, it is also impossible to create an N/p-row arrangement – hence it is unnecessary to check the latter arrangement. (Here, x denotes the largest integer less than or equal to x.) Once again, we rely on students to grasp this symmetry via inductive generalization from concrete values of N and p. To avoid the unnecessary check, we point out that our algorithm can check p-row arrangements for progressively larger values of p, until p becomes larger than N/p. At this point, students are better prepared to understand the following naïve primality testing algorithm and the faster algorithm shown alongside (Table 4). Note that the while-loop executes N – 2 times for the former algorithm and less than (√N)/2 times for the latter. We do not delve into a formal analysis of running time at this stage.

Table 4: Two algorithms for testing primality based on insights from Puzzle 1

NaivePrimalityTest(N)

if N <= 1

return Not_Prime

p = 2

while p < N

if N % p == 0

return Not_Prime

p += 1

return Prime

FastPrimalityTest(N)

if (N <= 1) or (N > 2 and (N % 2 == 0))

return Not_Prime

p = 3

while p <= N/p

if N % p == 0

return Not_Prime

p += 2

return Prime

Game 1: Coin-flipping

We now discuss a second example of using the GALA approach to concretely demonstrate abstract mathematical insights that lead to more efficient algorithms. Consider the following game between two players P1 and P2. There are N one-rupee coins [4] numbered 1 to N in a row with their heads down (tails up), as shown in first row of Table 5. The game with N coins involves N rounds, with each player (starting with P1) taking turns to complete an entire round. In the kth round, the player whose turn it is flips every kth coin (i.e., coin k, coin 2k, coin 3k, …). Thus, in the first round, P1 flips every coin after which all coins now have heads up. In round 2, P1 flips coin 2, coin 4, coin 6, … (i.e., the even numbered coins now have heads down). The first 5 rounds of the game are show in Table 5. The winner of the game is determined by counting the number of coins with their heads up after N rounds. P1 wins if this number is odd. Otherwise, P2 wins. After introducing students to the game, we ask them to determine whether they would rather be P1 or P2 for a given value N. A naïve algorithm is, of course, to simulate the game for different values of N. (Once N is fixed, the outcome of the game is deterministic.) We encourage students to implement the simulation as coding practice, but during the lecture hours we have students play the game manually in pairs with multiple values of N to discover a pattern. As with Puzzle 1, we claim no originality for this game (e.g., it appears as Locked Doors in Question 11 Exercise 1.1 [3]). Our contribution here is to develop the GALA pedagogy around such games and puzzles.

Table 5: The first 5 rounds of the Coin-flipping game

image

After about 15 minutes of play, we poll the class to see if they have noticed any interesting patterns during the simulations. Multiple pairs of students usually report that at the end of N rounds, the coins with heads up are numbered 1, 4, 9, 16, etc. Some students may be able to offer an explanation for why this happens (coin number k is flipped once for each factor of k, all integers k except perfect squares have an even number of factors, and an even number of flips leaves a coin in its initial configuration – heads down). However, we can once again proceed on the basis of inductive generalization that at the end of N rounds, the m coins numbered 12, 22, …, m2 will have heads up, where m is √N. Thus, we are able to create a straightforward algorithm to determine the winner of the Coin-flipping game with N coins:

CoinFlipWinner(N)

m = floor(sqrt(N))

if m % 2 == 0

return P2

else

return P1

The staggering simplicity of this algorithm compared to the cumbersome N-round simulation helps even the mathematically weakest of our students recognize that understanding the structure of the solution can lead to a much better algorithm. Thus, our approach has the potential to motivate such students to try and improve their mathematics fundamentals. Further, this algorithm can be revisited later in the course when discussing computational complexity, particularly to correct a common student misconception that highly optimized library functions (such as sqrt()) run in constant time.

Puzzle 2: Gadget testing

Our purpose with this puzzle, which is adapted from Question 3 exercise 2.2 in [3], is to introduce students to the idea of “worst case” while analysing algorithms. We want to determine the highest floor H of an N-storey building from which a certain type of gadget can be dropped without breaking (assuming HN). We determine this highest floor experimentally, by dropping such gadgets from various floors according to some strategy. We are allowed to break a maximum of two such gadgets during these experiments, and we assume that as long as a gadget does not break, its structural integrity is unaffected and the same gadget can be reused for another experiment. Students are asked to come up with a strategy that minimizes the number of drops needed.

To help students better understand the problem, we spend some time discussing the “cautious” strategy: drop a single gadget from floor 1, 2, … until it breaks or until we have dropped it from the top floor. Note that the gadget survives the first H drops and if H < N, it will break on the next drop (by definition of H). Thus, this strategy requires H + 1 drops if H < N, and it requires N drops if H = N. Hence, the strategy uses N drops in the worst case. Notice that this strategy does not utilize the second device, so we encourage students to think of a more “aggressive” strategy that requires fewer than N drops.

A natural variation, which students often suggest, is to drop a gadget from even-numbered floors: 2, 4, … etc. until it breaks at some floor 2B.1 We already know that the gadget does not break when dropped from floor 2B – 2, but we must do an extra drop from the “skipped” floor 2B – 1. If the second gadget breaks when dropped from floor 2B – 1, then H = 2B – 2. Otherwise, H = 2B – 1. This reduces the number of drops to B + 1. Many students are unable to express this quantity precisely in terms of N, but they do recognize that B + 1 ≈ N/2 in the worst case. At this point, at least one student suggests a further improvement to the strategy: drop the first gadget from every third floor: 3, 6, … etc. until in breaks at some floor 3B. Here, again, the second gadget is used to test the “skipped” floors (there are two such floors here). This strategy requires about N/3 drops in the worst case. Students now immediately recognize that a bigger jump will produce an even better strategy. In their eagerness, however, students may overlook the fact that the “skipped” floors must be examined with the “cautious” strategy since one gadget is now broken. Thus, for a jump of size k, about N/k + k drops are needed, where the latter term accounts for drops during the “cautious” phase.

Thus, the best strategy is the one for which the quantity N/k + k is minimized by varying k. Here again, we find that only a few students have sufficient mathematical maturity to utilize their knowledge of calculus to determine that the minimum occurs for k = √N. Hence, the optimal strategy requires about 2√N drops in the worst case.

Fibonacci Sequence

Similar to prime numbers, numbers in the Fibonacci sequence have several interesting properties [5][6]. The first two terms in this sequence are defined as F0 = 0 and F1 = 1. Each subsequent term Fn is defined as the sum of the preceding two terms in the sequence: Fn = Fn-1 + Fn-2. Thus, the first few numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, …. While there are several unexpected ways in which Fibonacci numbers show up in nature [7][8][9][10], we believe that the most compelling example arises from a property of these numbers in the following puzzle.

Puzzle 3: Missing/New Squares Paradox

Consider the square ABCD with sides of length 8 units shown in Figure 1. The area of the square is clearly 8 × 8 = 64 square units. For this puzzle, we provide students with these instructions: First, cut the square into 4 parts: the two trapeziums APSR (with sides as AP = 5 units, PS = 5 units, and AR = 3 units) and DQSR (with sides DR = 5 units, DQ = 5units, and DS = 3 units), and two right angle triangles PBC (with sides PB = 3 units and BC = 8 units) and CQP (with sides CQ = 3 units and QP = 8 units). Next, rearrange these four shapes as shown in Figure 2 to form a rectangle with sides of length 13 units and 5 units. Students are now confronted with a paradox: the area of the rectangle is 65 square units. Where did the additional square unit come from?

image

Figure 1: Square with each side of 8 units

image

Figure 2: Rearranging the square parts

To deepen the mystery, we present students with another example (Figure 3) where the reverse happens: the four pieces of a square totaling an area of 13 × 13 = 169 square units is rearranged to form a rectangle of only 21 × 8 = 168 square units (Figure 4). This time, one square unit has vanished! Finally, we inform students that there is an infinite number of such paradoxes.

image

Figure 3: square with each side of 13 units

image

Figure 4: Rearranged the square with side of 13

The mystery of missing and new squares can be understood as follows. To begin with, let us analyze the arrangement of pieces in Figure 2. The diagonal PS of rectangle consists of two parts PC and RS. These two diagonals have slightly different slopes (tan138=20.6\tan^{- 1}\frac{3}{8} = 20.6{^\circ} for PC and tan125=21.8\tan^{- 1}\frac{2}{5} = 21.8{^\circ} for RS), although to the naked eye they appear to align quite well. Thus, there exists a slight gap between the hypotenuse of the upper and lower triangles. Students are likely to attribute this gap to a slight inaccuracy in cutting the squares, but this narrow gap has an area of precisely 1 square unit and accounts for the first paradox. A similar discrepancy in the slope of the hypotenuse of the two triangles (tan138=20.6\tan^{- 1}\frac{3}{8} = 20.6{^\circ} versus tan1513=21.03\tan^{- 1}\frac{5}{13} = 21.03{^\circ}) causes the upper and lower triangles to overlap slightly in Figure 4. Once again, this overlap is easy to overlook, but it corresponds to the disappearing 1 square unit.

We find that these exercises spur students’ curiosity to find other such apparent paradoxes, and we bring up the topic of Fibonacci numbers and Cassini’s theorem [3] at this point:

Fn1×Fn+1(Fn)2=(1)nF_{n – 1} \times F_{n + 1} – \left( F_{n} \right)^{2} = {( – 1)}^{n}

Based on this theorem, an apparent paradox can be created with any three consecutive Fibonacci numbers Fn-1, Fn, and Fn+1. Specifically, a square whose sides have length Fn can be cut into two trapeziums and two right angled triangles, and these pieces can be rearranged to form a “near rectangle” whose sides have length Fn-1 and Fn+1. The right-hand side in Cassini’s theorem indicates whether the “rectangle” has a new square (when n is even) or a missing square (when n is odd). We do not expect students to prove Cassini’s theorem, but we ask them to write an algorithm to verify that it holds for all n in the range 1 to N for a given integer N. Our purpose in doing so is to convey a key point about reductions (discussed below), and we use the GALA approach to motivate the verification of Cassini’s theorem. Here is a naïve algorithm, which calls a helper function Fib(n) to compute Fn:

VerifyCassini(N)

n = 1

while n <= N

if n % 2 == 0

if Fib(n+1) * Fib(n-1) – Fib(n) * Fib(n) != 1

return Not_Verified

else

if Fib(n+1) * Fib(n-1) – Fib(n) * Fib(n) != -1

return Not_Verified

n += 1

return Verified

Although this algorithm is extremely inefficient, it exemplifies a key concept that we expect students to master during their DSA courses: reduce the unknown problem (here, VerifyCassini) to a known problem (here, Fib, which we assume has already been discussed, either in the introductory programming course, or earlier in the DSA sequence). Since modern programming languages come with libraries of highly optimized implementations of data structures and algorithms, students must possess the ability to solve new problems by utilizing built-in data structures, and reducing the given problem to one for which an efficient algorithm already exists. Our central purpose in discussing the VerifyCassini problem is to highlight that a reduction may not always be the most efficient solution to the original problem.

In the above algorithm, most students are able to recognize that the expression Fib(n) * Fib(n) wastefully calls the Fib() function twice with the same input. Hence, a more efficient solution calls the function Fib(n) once, saves the value in a variable (e.g., F_n = Fib(n)) and then calculates the expression F_n * F_n. Developing this idea further, a few students typically point out that the values of Fib(n) and Fib(n-1) are computed while calculating Fib(n+1). Thus, a much more efficient algorithm that eliminates all calls to the Fib() function is as follows:

FastVerifyCassini(N)

n = 1

F_prev = 0

F_n = 1

while n <= N

F_next = F_n + F_prev

if n % 2 == 0

if F_next * F_prev – F_n * F_n != 1

return Not_Verified

else

if F_next * F_prev – F_n * F_n != -1

return Not_Verified

n += 1

F_prev = F_n

F_n = F_next

return Verified

Before closing this section, we note that a similar comparison of solutions with and without reductions can be considered with prime numbers. Assuming an efficient IsPrime(N) helper function, students can work on to devise algorithms for the following problems [11]:

  1. List all prime numbers less than a given number N.

  2. List all twin prime numbers between two numbers M and N. Twin prime numbers are primes that differ by 2 (11 and 13, 17 and 19, 29 and 31, etc.)

  3. Check if a number is circular prime i.e., whether all rotations of a number are also prime numbers. For example, 1193 is circular prime since all of its rotations 1931, 9311, and 3119 are also prime numbers.

  4. Check if two consecutive Fibonacci numbers Fn, and Fn+1 for n>2 (since F2=1 is not a prime) are relatively prime. Two numbers are said to be relatively prime if they have no common factor among them except 1.

  5. Some of the Fibonacci numbers follows the property that number Fk is divided by k. For example, for k=1,5,12, F1=1 divided by 1, F5=5 is divided by 5, F12=144 is divisible by 12. List first 10 Fibonacci numbers such that Fk is divisible by k.

Summary

We have proposed a gamified approach to learning algorithms – GALA. This article has demonstrated how our approach can help many of our students to develop mathematical and computational thinking abilities. In the next article, we will discuss recurrence relations and algorithmic efficiency in terms of time and space complexity.

References

  1. National Education Policy 2020, https://www.education.gov.in/sites/upload_files/mhrd/files/NEP_Final_English_0.pdf

  2. Ram Rustagi, Viraj Kumar, A Gamified Approach to Learning Algorithms, ACS Journal of Computing and Communications, March 2021, Volume 5 issue 1. https://journal.accsindia.org/gala-a-gamified-approach-to-learning-algorithms/

  3. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 2nd edition, Pearson Education.

  4. Republic India coinage, https://rbi.org.in/Scripts/mc_republic.aspx, last accessed on Apr 2021.

  5. https://www.whitman.edu/Documents/Academics/Mathematics/clancy.pdf

  6. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html

  7. Thomas Koshy, “Fibonacci and Lucas Numbers with Applications”, Volume 1, 2nd Edition, Wiley publications, Dec 2017.

  8. Enchanter Nightshade, https://en.wikipedia.org/wiki/Circaea_lutetiana

  9. Earth information: https://imagine.gsfc.nasa.gov/features/cosmic/earth_info.html

  10. Math is Fun (Fibonacci Sequence) https://www.mathsisfun.com/numbers/fibonacci-sequence.html

  11. Programs for understanding properties of Fibonacci sequences. https://github.com/rprustagi/GALA-Fibonacci-Number-Programs.git


  1. For a full analysis, we must also consider the case when the gadget does not break when dropped from any even-numbered floor 2B, and examine two sub-cases: N is even and N is odd. We ignore this possibility here.↩︎

Leave a Comment:

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.