Algorithmic thinking problems

Question

In Norway we will have a new national mathematics curriculum for all ages including high school beginning august 2020. A fundamental change is the new focus on so called algorithmic thinking. In practice this means that we are going to add the use of Python to explore and solve mathematical problems.

Many of the examples we (teachers) have been exposed to in courses are simply traditional types of problems that are shoehorned into programming exercises, even though they would be easier to solve in a traditional way.

I think we need to modify our intuition for what kinds of mathematical problems that will become relevant in this new setting. But it is difficult to break out of old ways of thinking.

What I'm asking is, does anyone here know of (resources of) mathematical problems that are difficult to impossible to solve with "traditional school mathematics", but relatively easy to handle with programming (even Excel)?

Answer 1

One well-known source is Project Euler. The concept behind it is that each problem is mathematical and designed to be solved by an efficient algorithm on a "normal" computer in less than a minute. The early problems are all extremely accessible. As the problems go on, they become (in my mathematical opinion) far more esoteric from either a mathematical or algorithmic standpoint, but there are more than enough of the former problems to either provide or generate ideas that could satisfy a class.

I suspect that they are generally not expecting problems will be solvable in Excel, but some of them certainly could be. For instance, the second problem in the list asks for the sum of all of the Fibonacci numbers less than four million that are even. It took me a little digging into the formula documentation, but I did that in Google Sheets. ^_^ Python will be a completely excellent and authentic language for solving the problems -- you could even make a decision about whether to include things like number theory libraries or if you want to code your own library.

Answer 2

Any puzzle game which requires students to plan the entire problem before executing it might help. Also, there are physical puzzles which can be solved algorithmically much more neatly than if they use 'trial and error'.

In English, one resource which I have not seen mentioned yet is Code.org which has themed coding puzzles for all ages. Other puzzles, including physical puzzles, which promote algorithmic thinking include the Turing Tumble game. And surely even elementary students can understand the problem statement of the Towers of Hanoi and understand that trial-and-error makes moving a large tower difficult, but that it's possible to construct an algorithm (and a recursive one at that!) which lets them move it consistently.

Lastly, board games are an excellent avenue for learning conditional reasoning, as the rules are enforced by other players. Conditional reasoning is absolutely necessary to develop algorithmic thinking past "this is the order of steps to do things." Obvious examples include Ricochet Robots or any other sort of abstract strategy game. I found a lot of reviews for child-appropriate games on fathergeek.com. However, even a "silly" card game like Fluxx, with its constantly-changing rules, can lead to entertaining logical loops and conditionals. I acknowledge that these resources are, again, in English, but my hope is that they give enough inspiration to find equivalent resources in other languages. Students writing their own board games with rules that include conditional statements and loops could also be meaningful.

Answer 3

Challenging question! Two ideas. (1) Calculate the Greatest Common Divisor of two natural numbers, not so easily accomplished by hand on moderately large numbers. The Euclidean algorithm could be used to illustrate recursion/induction. Here is Python3 code:

trace = True # True turns on tracing prints.
def GCD( a, b ):
    '''Returns the Greatest Common Divisor to a & b.
       Assumes a & b are both positive ints.
    '''
    if trace:
        print( '=>GCD(',a,',',b,')' )

    if a == b:
        return a
    elif a > b:
        return GCD( a-b, b )
    elif b > a:
        return GCD( a, b-a )
############################
=>GCD( 24 , 116 )
=>GCD( 24 , 92 )
=>GCD( 24 , 68 )
=>GCD( 24 , 44 )
=>GCD( 24 , 20 )
=>GCD( 4 , 20 )
=>GCD( 4 , 16 )
=>GCD( 4 , 12 )
=>GCD( 4 , 8 )
=>GCD( 4 , 4 )
############################
4

(2) Any result that employs randomness. For example, Buffon's Needle approximation to $\pi$. Here is Python3 code:

from math import sin,cos,pi
from random import uniform

def CreateNeedle():
    '''Returns y-coords of endpts of unit-length needle'''
    ang = uniform( 0, 2*pi )
    x2,y2 = cos( ang ),sin( ang )
    # x1=0
    y1 = uniform(-1,1)
    y2 = y2 + y1
    return y1,y2

def Buffon( n ):
    '''Throws n needles, counts hits across
       x-axis'''
    hits = 0
    for i in range( n ):
        y1,y2 = CreateNeedle( )
        if (y1<0 and y2>0) or (y2<0 and y1>0):
            hits += 1
    print( hits,'out of',n,':n/hits=',n/hits,'::',pi )

Buffon( 1000000 )
############################
318405 out of 1000000 :n/hits= 3.1406541982694995 :: 3.141592653589793
############################

Answer 4

An "old school" answer (nearly 60 years old now!) which works for any age range is turtle graphics, which is (are?) implemented as a Python module.

We can only guess how much of your curriculum is officially labelled "geometry", but it will certainly teach algorithmic thinking, and also be fun.

Answer 5

These may be too hard, but the ACM's International Collegiate Programming Contest (ICPC) has a set of past programming problems that require algorithmic thinking. I took a class in college where we basically just worked on these for 3 hours a week. It was really good problem-solving experience.

https://icpc.baylor.edu/worldfinals/problems

Answer 6

This isn't a resource, but a fun algorithmic problem that I remember solving back in 7th grade:

Consider a long loop of train wagons, $1 ... N$ for some unknown $N$ where wagon $i$ is connected to wagons $i-1$ and $i+1$. You can walk from one wagon to its neighbors. In every wagon, there is a lightbulb connected to a switch. You start in a wagon and want to figure out how many wagons there are in the loop. If the lightbulbs all started out as turned off, this would be easy: Turn on the light in all wagons you pass and count the number of wagons until you find lights that are already turned on. But there is a catch; to begin with, the state of every lightbulb is randomly chosen.

Are you still able to find $N$? How many steps from a wagon to the next (or previous) one do you have to take? Can you minimize this number by making some modifications to your algorithm?

Answer 7

The de Casteljau algorithm for generating polynomially parameterized curves in the Beziér representation admits a simple geometric interpretation in terms of the control polygon that is easily implemented in Python.

More precisely, a polynomially parameterized curve in the affine plane or affine three-space can be represented in the form $P(t) = \sum_{k = 0}^{n}\binom{n}{k}t^{k}(1-t)^{n-k}p_{k}$ where the $n+1$ points $p_{0}, \dots, p_{n}$ are the control points. The de Casteljau algorithm constructs $P(t)$ in the following way. First one considers the control polygon which is the polygonal curve whose sides join $p_{i}$ to $p_{i+1}$ for $0 \leq i < n$. One subdivides each of these sides into two subsegments of relative lengths $1-t$ and $t$. There results $n$ points $b^{1}_{0}, \dots, b^{1}_{n-1}$ given explicitly by $b^{1}_{i} = (1-t)p_{i} + tp_{i+1}$. One repeats the process with the $b^{1}_{i}$ in place of the $p_{i}$. At each stage the number of points is reduced by $1$, so at stage $k$ one has $b^{k}_{0}, \dots b^{k}_{n-k}$ where $b^{k}_{i} = (1-t)b^{k-1}_{i} + tb^{k}_{i+1}$. It is not hard to see that $P(t) = b^{n}_{0}$, the point obtained at the $n$th stage. This algorithm can be used to generate the curve by running it for $t$ chosen from some partition of $[0, 1]$. The polygonal curve used at each stage can be drawn (by hand or using the computer) and the algorithm can be implemented in Python in a few lines.

The explicit expression for $P(t)$ is not needed in any of this. One could simply start with the algorithm as a way of producing a curve from the data of an ordered collection of points.

For a low degree curve it can be instructive for students to compare generating the curve by plugging values into the explicit expression for $P(t)$ and by running the de Casteljau algorithm. These are two very different ways of constructing the curve on a computer. Students often have never thought about how functions or graphics are represented in a computer or calculator. It can be very instructive for them to see that it is not necessarily achieved by substituting values. Also they often do not realize that what looks like a curve on the computer screen is really a discrete approximation of the mathematician's idealized continuous curve (everything is discrete on a computer!). Moreover this method (or, better, modifications and improvements of its analogue for splines, known as the Cox-de Boor algorithm, are used in practice in computer assisted geometric design (CAD)).

Answer 8

Although some of the puzzles might be appropriate only for extra credit, have a look at Algorithmic Puzzles by Anany and Maria Levitin.

The ad copy for this book gives a good description:

While many think of algorithms as specific to computer science, at its core algorithmic thinking is defined by the use of analytical logic to solve problems. This logic extends far beyond the realm of computer science and into the wide and entertaining world of puzzles. In Algorithmic Puzzles, Anany and Maria Levitin use many classic brainteasers as well as newer examples from job interviews with major corporations to show readers how to apply analytical thinking to solve puzzles requiring well-defined procedures.