# Algorithmic thinking problems

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)?

• I don't have any suggestions, but this reminds me of the difficulties created when graphing calculators came on the market (late 1980s) in the usual precalculus and first semester (differential) calculus courses regarding the teaching of curve sketching techniques. Also, a similar curriculum issue when student-friendly computer algebra based calculators like the TI-92 began appearing in the late 1990s. Then again with the rise of the internet and students being able to google for homework help or answers. – Dave L Renfro Nov 21 '19 at 11:58
• problems that are difficult to impossible to solve with "traditional school mathematics", but relatively easy to handle with programming --- In looking at this 2-3 hours later, I noticed that the issues I mentioned are somewhat opposite of what you're looking for. For the issues I mentioned, the concern was in finding ways to create non-trivial tasks that made use of the new technology and provided appropriate content training. Without the requirement of "non-trivial" this was easy, but coming up with cognitively challenging tasks that did this proved to be, well, challenging. – Dave L Renfro Nov 21 '19 at 14:09
• IMHO, algorithmic thinking is an oxymoron. I don't think that Brahmagupta or al-Khwārizmī or Descartes were thinking algorithmically when they were solving quadratic equations. The product of their efforts — quadratic formula — can be used now without much thinking, just plug in numbers and get the result, which is the whole point of algorithm. School math includes many algorithms like stacked addition or quadratic formula. Calculators or computers are not needed for these tasks and are actually detrimental. On another hand, numerical integration is where computers are applicable and useful. – Rusty Core Nov 21 '19 at 20:48
• @RustyCore Nah, it's more that algorithmic thinking has nothing inherently to do with programming. The core idea is "how do you make a todo list an idiot can follow to get the correct result". The reason it's so important in programming is that computers are such wonderful idiots; you can't use any shortcuts like "See? It must be X!", you have to represent everything as the simplest arithmetic operations. Use the right tool for the job - only use a programming language for algorithmic thinking if it 1) limits the "smarts" of the interpreter enough, 2) produces concise, non-ambiguous todo list. – Luaan Nov 22 '19 at 11:16
• @Luaan Quadratic formula is an algorithm, it produces unambiguous list of steps to obtain the result. It does not require a computer to follow the steps, but a computer can be used exactly because the steps are predefined. Following an algorithm does not require thinking at all — like you said computers are stupid, all they do is follow commands. Inventing algorithms is a whole different cup of tea, but I don't think the requirement from Norwegian curriculum meant inventing new algorithms. – Rusty Core Nov 22 '19 at 17:39

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.

• @Namaste As I mentioned in my answer, there is a large range of questions in the Project Euler database that can either be used in a class or can inspire teachers to devise more appropriate content for their class. I inferred from the question that students old enough to understand Python would also be old enough to understand divisibility and the Fibonacci sequence. Also, I noted that I solved one of the easier problems in a Google Sheets spreadsheet, so your assertion that students need to master programming first seems less founded than my experience. – Matthew Daly Nov 21 '19 at 15:56
• I've done some of the Project Euler problems. Many of them need no programming. Playing with those in Excel is sufficient. – Sue VanHattum Nov 21 '19 at 16:11
• @Namaste You could easily use Project Euler problems as a stepping point for teaching younger kids, if teaching does not equal "setting a problem and asking them to solve it unaided". For example, you could definitely explain Fibonacci to a 3rd grader, have them calculate a few by hand, ask them how long it would take to add up 4 million by hand ("forever"), and then demonstrate turning that into an algorithm and letting the computer solve it quickly. – user3067860 Nov 21 '19 at 23:02
• – Rusty Core Nov 22 '19 at 0:11

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.

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
############################

• @Namaste: I was responding to the OP's phrases "all ages including high school," and "we are going to add the use of Python." – Joseph O'Rourke Nov 21 '19 at 17:23
• It might be a bit more impressive if you could create the needle without using $\pi$ in the definition. How about sampling randomly from the unit square, discarding any outside the disc, and rescaling any inside the disk? – Steven Gubkin Nov 22 '19 at 16:43
• @StevenGubkin: Good point! I was just simulating Buffon's random needle drop. – Joseph O'Rourke Nov 22 '19 at 16:51
• Incidentally, here is a very nice animation: ventrella.com/Buffon. – Joseph O'Rourke Nov 22 '19 at 16:52

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.

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

• Also, there are probably practice problem sets people use to train for the ICPC that are easier. – xdhmoore Nov 21 '19 at 22:50

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?

• for how long does a lightbulb stay hot after you turn it off? – njzk2 Nov 24 '19 at 0:43
• Time is not a factor; you could replace the lightbulbs with coins showing heads and tails, and the same algorithm should work. This is purely an algorithmic puzzle – Loke Gustafsson Nov 24 '19 at 13:00

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)).

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.