Tag Archives: Pedagogy

British Informatics Olympiad: Breaking Down Problems

Make sure you’ve read this post on the Olympiad Format before reading on…

Here’s an old BIO question

Goldbach Conjecture

A prime number is a whole number, greater than 1, that can only be divided by itself and the number 1.  It is known that all even numbers between 4 and 300,000,000,000,000,000 are equal to the sum of two primes (a fact that is believed to be true for all larger even numbers as well, and called the Goldbach Conjecture).

For example, 30 = 7 + 23.  There are two other ways of expressing 30 as the sum of two primes, which are 11 + 19 and 13 + 17.  These are the only ways of expressing 30 as the sum of two primes, since the order of the numbers in the additions does not matter.

1(a) [ 25 marks ]
 Write a program which inputs a single even number (between 4 and 10,000 inclusive) and outputs a single number which is the number of different ways the input can be expressed as the sum of two primes.
 Sample run
 22
 3

This problem can look quite daunting at first.  Don’t let that put you off.  All the questions in the BIO are there to test you as a programmer, there will be a way to solve them.  As a matter of fact, this is a classic programming problem, one that I included as one of my 99 Java Problems

So let’s break the problem down

The Goldbach problem consists of three separate programming problems:

  1. Testing if a number is prime
  2. Looping over the possible pairs of numbers
  3. Testing if the Goldbach Conjecture holds true for each pair of numbers in the loop

Solving the Goldbach problem requires solving these three problems

The first problem, writing a method to check if a number is prime, is a classic programming problem. Many solutions can be found online.

The second problem, thinking of all the possible pairs of numbers that need to be tested, is more interesting.  At this time it’s worth using the mathematicians trick of thinking about simple cases.   Suppose you were testing the number 10.  Which pairs of numbers add up to 10?  1+9, 2+8, 3+7, 4+ 6, 5+5.  Is that it?

What about the number 8? 12?  Does this help you to write a loop listing all the pairs of numbers adding up to 10?  Now think of the general case.
Now combine 1 & 2 to get your final solution.

Is there a more elegant way of solving the problem?  In terms of the BIO, it doesn’t matter.  As a programmer, though, you’ll always be thinking about ways to make your code more efficient.

What happens if you’ve got all the bits working but you can’t combine them?  The bad news is that you’re not going to gain very many marks.  But the good news is that you’ve had a go, and so you’re just a little bit better at coding than when you went into the exam…

Steps to Learning Programming

There are lots of programming languages designed to make learning programming easier. In my experience they are a waste of time for most students. Many of the languages will allow students to make apparent progress and to produce what appear to be impressive applications, but if students don’t understand what they’re doing, they’ll quickly lose interest.

Here are the things that students need to learn, and the rough order in which they need to learn them.

  • Imperative commands such as PRINT “hello”
  • Variables and types, particularly the difference between strings and numbers
  • Simple arithmetical operations e.g. a = 3, b =4, c = a+b
  • Branch commands such as IF answer = “Paris” THEN PRINT “Correct”
  • More complicated branch commands – IF THEN ELSE
  • For loops or equivalent
  • While loops or equivalent
  • Nested branch commands
  • Nested loop commands
  • Arrays
  • Traversing Arrays using for loops and while loops
  • Functions and Procedures, or equivalent

And that’s it. Everything else in programming can be achieved using the above. The rest is just readability, convenience and elegance

The problem with some languages, particularly the visual ones, is that students produce results without understanding the above. If students don’t understand the above, they don’t understand programming.

Python allows you to teach all of the above. And then once the student has learned, they can build on what they know, replacing the pieces of their Python toolkit with more advanced constructs as they learn. And as programmers, they’re always learning…