Author Archives: Paul Curzon

by - 0 comments

TUDOR COMPUTATIONAL WITCHCRAFT

  • Learn a Tudor Algorithm to do hard times tables
  • See a simple (and useful) example of what algorithms are.
  • Understand why algebra is really useful – for proving algorithms ALWAYS work

Algorithms are magic. Even simple algorithms can sometimes look like witchcraft. My favourite is one of the ways the Tudors did multiplication. It is all down to Welsh Tudor polymath Robert Recorde. As well as being a mathematician, who wrote the first arithmetic text book, he was also the physician to two Tudor Monarchs: Edward VI and Mary. Not only that, but along the way he also invented the equal sign using it for the first time as a shorthand for the phrase “ is equalle to” when doing maths (he would have liked the C programming language!). He was particularly good at algorithms and his book contained a cunning way to make the times tables easier.

Learning times tables is a rite of passage of primary school students. Those up to 5 are not too difficult but the 6, 7, 8 and 9 times table are particularly hard to remember (though of course the 9 times table does have a cunning pattern that makes it easier). Robert Recorde had a solution. In his book he gave an algorithm that made those larger times tables easy. If you know your tables up to the 5 times table (the easy ones), then the rest become simple too. It is just a matter of knowing the algorithm and doing some simple subtractions combined with the multiplications you do know. That the algorithm works is barely believable though, it is so odd.

The Algorithm

Here is how it goes. Suppose you have two of those nasty higher numbers to multiply like 8×7.

  1. Draw 7 boxes labelled A, B, C, D, E, F and G. Write one of the numbers you want to multiply in box A and the other in box B.
    • eg if you want to calculate 8 x 7, put 8 in box A and 7 in box B.
  2. Subtract the number in box A from 10 and put the answer in box C.
    • 10-8 = 2, so put 2 in box C.
  3. Subtract the number in box B from 10 and put the answer in box D.
    • 10-7 = 3 , so put 3 in box D.
  4. Multiply the two numbers in box C and D together. Put the answer in box E.
    • 2 x 3 = 6 so we write 6 in box E
    • Because your original two numbers in A and B were above 5, the new ones you must multiply instead are both below 5 so its a nice easy multiplication.
  5. Now subtract the number in box C from Box B (ie the diagonal numbers) and multiply the answer by 10 (stick a 0 on the end) writing the answer in box F.
    • 7-2 = 5, so multiplying by 10 means you put 50 in box F.
  6. Construct the final answer in box G by adding the number in box F to the number in box E.
    • E holds 50 and F holds 6 so 50+6 = 56 is the answer to the original multiplication of 8×7.

TudorMultiplication.jpg

Try the algorithm yourself on some more examples, like 6×9, 7×6 and 8×9. It seems a bizarre way to do multiplication – were the Tudors slightly bonkers? Well possibly, but Robert Recorde was just very clever. At a stroke his clever algorithm gives a way to do all those hard multiplications using only a few much simpler calculations.

Does it always work?

This little computational ‘spell’ seems like witchcraft! Surely it doesn’t really always work? Actually it does. The point of an algorithm is that it always guarantees you get the right answer. We can prove this one does with a bit of algebra.  Of course, as long as you trust Recorde, you don’t have to understand the proof for the algorithm to work for you. It is good to do the proof though (or at least have a rigorous argument) to be sure the algorithm really is fool proof.

The Proof

STEP 1: Let’s call the number in box A, a, the number in box B, b and so on. So we are trying to work out the answer to:

ab (thats just another way to write: a x b)

Now (see the diagram below) instead of doing the multiplication directly we work out

TuderMultiplicationAlgebraProof.jpg

STEP 2: c = 10-a and

STEP 3: d = 10-b

We multiply these together e = c x d so to get the number in box E, replacing c and d by the terms they are equal to, we do

STEP 4:  e = (10-a)(10-b).

We also subtract 10-a from b, and multiply it by 10 to get the number in box F, so

STEP 5: f = 10(b-(10-a))

The final answer is then just g = e + f. This means the calculation we ultimately do is

STEP 6: g = 10(b-(10-a)) + (10-a)(10-b)

We need to show this value g is the same as a x b.  It looks a bit unlikely but let’s simplify it all.

g = 10(b-(10-a)) + (10-a)(10-b)

Expanding the brackets for the part that came from f gives:

= 10(b -10 + a) + (10-a)(10-b)

= 10b -100 + 10a + (10-a)(10-b)

Similarly, multiplying out the brackets from e’s part gives:

= 10b -100 + 10a + 100 -10a -10b + ab

Now having expanded everything, we simplify: the terms +100 and -100 cancel out

= 10b + 10a -10a -10b + ab

The +10b and -10b cancel out too.

= 10a -10a + ab

The +10a and -10a also cancel out, leaving just a single term.

= ab

So what this says is that following the algorithm leaves the answer of calculating a x b in box G which is just what we wanted.

Algorithms

Algorithms are just sequences of steps to follow that guarantee a result (whether you understand why it works or not). Here the result is to multiply two numbers doing only simpler calculations. Of course, computers don’t know what they are doing. They can only follow rules blindly. While perhaps not using exactly this algorithm, they do use lots of clever algorithms to allow them to do arithmetic quickly.

This bit of witchcraft also shows why algebra is such a useful thing. It is a great way of proving useful algorithms really do always work.

The Tudors may still mistakenly have believed in witchcraft, and may not have had computers, but their computational witchcraft was still a really useful thing.

This one is for Peter,  the only person I imagine ever to get spontaneous applause from a class of teenagers for algebra… and a wonderful computational magician. 

He also loved hiding Easter Eggs in our work.

by - 0 comments

Feedback matters

Here is the next in our series of tips about learning to learn (to program).

TIP 8 :  Immediate, Frequent Feedback Matters

Paul Curzon, Queen Mary University of London

The real key to deliberate practice, to putting in hours of practice that is as effective as possible, is to have immediate and frequent feedback. You need to find ways to be sure what you are doing is right (or wrong). You need to practice the right things and fix the causes when you get things wrong. Otherwise, with all that practice you could just  be getting better and better at doing it badly.

Building appropriate mental models of sub-skills is an important part of this as it can give a basis of being able to providing feedback yourself. The understanding you have can help you work out what you must have done wrong. When a musician plays the wrong note, if they can hear it sounds wrong, they have some feedback. They can work on that note until they consistently get it right.

Programming provides natural forms of feedback. If you write nonsense that isn’t a program at all, perhaps because a single bracket is missing, or because something was mis-spelled, then when you compile the program, the compiler will tell you about your mistakes. The feedback is immediate.  Compile your program frequently and you will get frequent feedback.

Similarly with a good test plan, and knowing what you are trying to implement you can get immediate feedback as to whether a program does the thing you intended or not in all situations.

This will only be helpful if you were not trying to do too much at once. If you spend days (or even hours) trying to write complex programs, before compiling and running then the feedback is not immediate. You only get feedback when you finally finish the whole thing. Therefore it is really, really important you practice by writing small programs, not large ones bigger than anything you’ve tried before.

When you do write larger programs, it is important that you build them a step at a time, adding to them a little at a time, then recompiling and testing them. This requires you to have understanding of the structure of programs as you need with each change to still have what you think is a valid program. This is a skill to gradually develop too.

So again we see that it is important to not try and make too large steps at once, to learn to program effectively.

It is because there are these natural feedback mechanisms in programming that many people teach themselves to program. As long as they are not put off by making mistakes and see them as learning opportunities they can use feedback from compiling and running programs to get better and better.

If you are a:

  • student
    • Practice writing small programs that introduce single new things at a time.
    • Write programs a little at a time, recompiling, running and testing frequently.
    • Don’t be frustrated by compiler messages, see them as feedback to help you improve.
    • Test programs thoroughly, not just once and then assume it works
  • teacher:
    • Set programming exercises that are small
    • For large programs encourage iterative development.
    • Provide exercises with test plans, teaching debugging skills.
    • Provide other mechanisms for immediate feedback if you can, eg marking programs on the spot as a student completes them, not having them handed in with feedback days or weeks later.

More on Learning to Learn (to program)

IoC logo on white

 

 

 

by - 0 comments

Draw Concept Maps

Here is the next in our series of tips about learning to learn (to program).

TIP 7 :  Reinforce understanding with concept maps

Paul Curzon, Queen Mary University of London

Once you have worked out the basics of a mental model (such as what a programming construct does), you need to reinforce and refine that understanding. You need to do that actively. Weak learners often try and memorise explanations by repetition but that doesn’t help understanding. Reading an explanation and then drawing a concept map, by contrast, is a powerful way to reinforce your understanding.

A concept map is just a simple kind of diagram. It has:

  • circles which represent concepts (think nouns) and
  • arrows between circles that show their relationship (think verbs)

You start by making a list of all the concepts (the nouns) that are relevant. For example, having encountered a print statement you might (based on your initial limited understanding) include in your list:

  • A print statement
  • A print command
  • A String

and draw them as circles. Then you work out how they are related with those links giving you the arrows. So you might draw a concept map of a print statement as:

PrintStatement1

This focusses on the structure – the bits that make up a print statement – rather than what it does. There are lots of ways to draw a concept map around any given concept or area – its not about right and wrong so much as getting down your current personal understanding. However, in programming you will get most benefit if the concept map focusses on what a programming construct does when it is executed.

Including what the print statement does may lead your next version of the concept map to be a little more sophisticated, so something like:

PrintStatement2

As you understand more then future versions will be more sophisticated still – for example you might in a later version include how the print statement actually takes a string expression not just a string and it is evaluated first to give a string value.

Reading (or listening to) the explanations of experts is important when creating concept maps as that is how you pick up the terminology of an expert – and so the concepts that matter like “statements” and “expressions”. To become an expert you need to talk the language of experts, not just have the skill of an expert. Concept maps can help bring together the terminology and your developing mental models.

Having created a concept map you can now turn it in to your own explanation, in your own words. From the above we get an explanation in our own words such as:

A print statement consists of a print command and a string. The execution of the print statement makes the string appear on the screen.

The benefit of drawing concept maps is it helps reinforce your understanding of the relationships of concepts to each other and to the concepts you have come across previously….and that is the core of what understanding is about.

If you are a:

  • student
    • Draw a concept map for each new programming concept you learn
    • Keep redrawing it again later as you understand more: you will probably be able to draw a more complex concept map.
    • Write explanations based on your concept map
  • teacher:
    • Show students how to draw concept maps
    • Provide some simple examples to show the idea, but remember the biggest benefits come when students create their own concept maps.
    • Set exercises to create concept maps for each new concept, once students have done some experimentation.
    • Set exercises to write prose explanations from concept maps.

More on Learning to Learn (to program)

IoC logo on white

 

 

 

by - 0 comments

Learning to Learn (to program): Experiment to learn

Here is the next in our series of tips about learning to learn (to program).

TIP 6 :  Build mental models by experimenting

Paul Curzon, Queen Mary University of London

Before you can practice effectively you need to have built the right mental models. Knowledge and skill join. One way to do this is to read explanations written by others. Sometimes there is a much better way: work it out for yourself! Learn by experimenting! For programming, this is a really powerful way to learn. Instead of building a mental model of constructs from explanations, first try and build your own mental models by reading programs others have written (simple ones to start with), and trying to work out how they work. Learn by making changes based on that and predicting what will happen, then trying by running the program.

This works well with programs because you can execute them and see what they do. Take a program, execute it, then look back at the program and see if you can see how it does what you can see it doing. Make a small change with a clear idea in your head now of what you think it wilo now do, then execute it again. If you were right then you have some confirmation of the mental model you have started to form. Try a different change, and so on.

To take a simple example, here is a Python program.

print "Hello World"

If you execute it, the following appears on your screen:

Hello World

Looking back at the program form an idea of what is happening… Try it before reading on.

 

The program prints messages, and there is only one line so that line must be a command to do so. Based on that, make a change to the program with a prediction that the new program will make Hello Paul (or perhaps your name) appear:

print "Hello Paul"

You execute it. It does. Now try a different change to the program:

print "Hello World"
print "Hello World"

What do you think it will do now? And so on…

You are working like a scientist, gradually building a theory based on experiment. As a good scientist you should look for changes that don’t just confirm your idea, but that will show you are wrong if you are, you want to stretch the edges of your understanding.

Once you have run out of experiments or are really stuck, then read (or listen to) the explanations. Now you have a solid basis to understand what they say. You know what they are talking about as you’ve seen it. You are also in a position to understand subtleties you have missed. If the explanations do tell you something you hadn’t worked out, go back and experiment with those aspects.

It is important that you don’t try and do too much in one go. Programs you start experimenting on should only be a little more complicated than you already understand. Changes you make should only be small and one at a time. If things go wrong, revert to a version that did work and you did understand.

Do this learning by experimentation with each new programming construct as you start to learn about it (having mastered the earlier ones first). Only read the explanations after you have experimented a little. You will understand and remember the explanations so much better that way round.

If you are a:

  • student
    • Don’t just rely on explanations, experiment with existing programs.
    • Don’t spend your time copying programs, spend it making small changes to existing programs and predicting what will happen.
  • teacher:
    • Encourage students to experiment and give them time to do so.
    • Provide a series of starting programs for them to experiment with.
    • Give them that code – don’t waste their time making them type it in.

Further Reading

A programming pedagogic framework that follows a similar investigative approach to this is PRIMM.

https://blogs.kcl.ac.uk/cser/2017/09/01/primm-a-structured-approach-to-teaching-programming/

A difference is we advocate above a first stage of Run code first to start a PRIMM like cycle with new constructs. The most important point though in both is that reading and predicting code in an experimental cycle matters.

More on Learning to Learn (to program)

IoC logo on white

 

 

 

by - 1 Comment

Learning to Learn (to program): Mental Models Matter

Here is the next in our series of tips about learning to learn (to program).

TIP 5 :  Focus on mental models.

Paul Curzon, Queen Mary University of London

To get the best out of practice, when learning a skill, you need to have the right mental models. That is where knowledge and skill can work together in tandem. The right sort of knowledge can be used both to base skills on, and to hone them. Practicing the right skills can develop the right kind of knowledge. What you need are good mental models, good understanding, of what you are trying to do.

You must focus on developing the right knowledge, the right mental models, if you are to get the most out of practice.

As a novice programmer, the first and most important mental models are those of the different programming constructs.  How does a variable work? What does a while loop do?

People often think syntax (spelling, punctuation) is what you have to learn first to program and they focus on that and worry most about missing semicolons or whether things should be in capitals or not. Actually far more important to get right first is semantics (what the constructs do) and structure (how programs are organised). Worrying about trying to remember the words and symbols turns programming in to a rote learning task with no real understanding – and nothing to base the right sort of practice on. That’s the wrong thing to do.

It is vital to avoid this trap. Instead practice should be based on understanding the concepts. This has to be the big, early focus to learn the deep skills of programmers. If you do not understand what a programming construct does, you won’t be able to write programs using it…and it is really, really easy to misunderstand if all you have is a basic technical explanation.

Luckily, there are a series of ways to build the right mental models. The first step is to have good explanations, and then make sure you can explain those things in your own words. Explaining is a skill too. As a learner you can practice explaining yourself either in writing or to others. If in a group everyone can then benefit. We will talk about more good explanations in a later blog. You can also draw concept maps that show the way concepts link. More on that later too. For now though actively read explanations. Make notes of some kind as you go, then take a blank sheet and without the original try and write your own explanation.

Another important way to build accurate mental models is to practice reading programs and fragments of programs based on what understanding you do have, and try and predict what they do (then see if you are right). Treat programs as a mini-scientific experiment. Closely related to this is to trace (or dry run) programs. Here you act like a computer stepping through the program. More on this later too.

Notice these are skills too – the sub-skills we identified earlier – so you can practice them.

When you are stuck and do not understand a construct, when you cant write a program, can’t do the dry run and can’t predict what a program will do, it is easy to be dispirited. It doesn’t mean you can’t program though … it means you have just learnt something important – you have learn’t something you do not understand (yet). You’ve found something to work on. It just means you need to get a little bit of help. That might be from a teacher, from a good book or video, or another student (needing to practice their ability to explain), or possibly even the right, simpler exercise to try. You can understand and when you do you will have made another big step forward.

With the right mental models in place then you are in a much stronger position to practice all the programming sub-skills (including writing programs). You are also much more able to learn from your future mistakes.

It is absolutely vital you do focus on getting a clear understanding of the semantics. Then all your other practice will be so much more effective.

If you are a:

  • student
    • Focus on making sure you understand what each new construct does, then do lots of practice of all the sub-skills around until until you have mastered it.
  • teacher:
    • Make sure you make it clear to your students that understanding meaning matters, not memorising syntax.

More on Learning to Learn (to program)

IoC logo on white

 

 

 

by - 0 comments

Identify the sub-skills

Paul Curzon, Queen Mary University of London

Here is the next in our series of tips about learning to learn (to program).

TIP 4: Know the sub-skills and practice them.

Paul Curzon, Queen Mary University of London

To learn a complex skill you need to practice, and so master, the right things a little at a time. That means you need to break it into sub-skills that you can work on separately. This is the idea behind deliberate practice too. What sub-skills have experts mastered? Practice those.

What are the sub-skills to practice to learn to program effectively? It is not just to write programs. For a novice there are a whole series of sub-skills that matter and that you can practice separately:

  • Being able to explain the basic programming concepts (like variables, loops, etc).
    • This matters as it is closely linked to the idea of mental representations of deliberate practice. This is building the basic mental representations.
    • Being able to compare and contrast related concepts is a useful extension to this.
  • Being able to read / trace simple programs and program fragments using each concept.
    • Reading a program doesn’t just mean read the words but being able to work out what the program does.
    • This helps ensure you have the right mental representations the skills are based on
  • Being able to think logically and focus on detail
    • This is actually a foundation to all the others
  • Being able to debug a program. There are two completely different skills here:
    • Being able to interpret compiler messages and correct compile time errors
    • Being able to find and correct run-time errors.
  • Being able to choose the right programming concept to do a task.
  • Being able to modify a program to do something slightly different, including
    • using the same constructs in a slightly different way, and
    • incorporating a new programming construct into an existing program so that it has a little more functionality
  • Being able to take simple problems and write simple programs that solve them using the appropriate concepts.

Bearing in mind the need to do things a little at a time, and the need to practice a lot, you should practice all these sub-skills on fairly small bits of code to start.

This does NOT mean that you shouldn’t be writing programs at all. It is in writing programs that you get the motivation to do the practice. Its also where you practice putting it all together. A tennis player still plays matches, but in between they practice serves, and hitting the ball to precise places, as well as general fitness, and so on. Similarly a programmer needs to both practice and write interesting programs.

It’s a bad idea to start on a large, complex programming project though, that may then be way beyond your current skill level. Instead master the skills for individual constructs and then build a small program gradually in to a larger project as you master each level of skill.

Once you have mastered the basic concepts and skills, then there is another level of skills to master. These are essentially what people talk about as computational thinking. There are lots of sub-skills involved (which is why academics argue a lot about what it actually is) but here is one list used:

  • algorithmic thinking
  • decomposition
  • generalisation including pattern matching
  • abstraction
  • evaluation

Much of this is applying advanced versions of the earlier set of skills, and you certainly do need to practice more complex versions of the original set including:

  • Reading real programs
  • Writing more complex programs

If you are a:

  • student
    • As a novice, practice all the above novice skills separately, focussing on one construct at a time.
    • Exercises to read/trace programs are especially important to practice.
  • teacher:
    • Set exercises that practice each of the skills separately, for each programming construct.
    • Exercises to read/trace programs are especially important to provide.