Algorithms

There is also a demonstration of some algorithms in the new Interactive section.

When you're writing any sort of program in Computer Science, the most important thing is that algorithm - that's effectively the plan, or design, for what your program is going to do. The algorithm should be written in a language-independent form - flowcharts and pseudocode are common forms used for representing an algorithm.

For any task you want to perform with your program, there is sure to be more than one way to do it. With programmming, there isn't necessarily a right or wrong way to do things, but there are efficient and inefficient ways. Which way you go about things will depend on a variety of factors, such as the platform on which the program is to run, and who will be maintaining the code.

If you're writing for an embedded system, for example, or maybe a web-site, you will want to minimise the amount of code you write, or try to reduce the amount of storage required. For a real-time or other time-critical application, you will want to make your code run as quickly as possible. If you're a commercial programmer, and other people are going to be maintaining your code, then you might be better to sacrifice "clever" programming techniques and maybe some performance at run-time in favour of producing easily intelligible functions.

Generally speaking, you will want to maximise the efficiency of your code at run-time. You may want to consider both iterative and recursive solutions, and if you go for the iterative option, your goal will normally be to minimise the number of iterations required to complete the task.

Computational Thinking

There are some general approaches that you can take to solving any problem and creating a new program:

the method is more important than the result - e.g. you could print the two-times table by printing 2, 4, 6, 8, 10, etc., but you'd get a shorter program (and one that you can generalise - see the next point) if you thought about looping through the number from 0 to 12 and multiplying by 2. Similarly, if you want to draw a square in Scratch, you need not to think about what a square looks like, but the process of drawing a square.
generalise where possible - if someone asked me to write a program to display the two-times table, I'd be thinking that tables are all the same, and that if we can print the two-times table we can do them all by just being a bit more careful. You can also apply this principle to whether you'd write a program in the first place. I'd never done a Sudoku puzzle when I saw one in the paper, and I thought "I could spend some time solving that one puzzle, or I could spend my time solving all Sudoku puzzles."
have I done this before? - try to get into the habit of abstracting your problem; that's ignoring any unnecessary detail to get at the fundamental essence of a problem. The real reason I made the Sudoko program was not because I was interested in Sudoku, but because I realised that Sudoku is basically the same as school timetabling - a problem that I did want to solve. You can see this if you think of the smaller 3 x 3 grids as a period on the timetable - you can't use a teacher or class twice in the same period in the same way that you can't use the same digit twice, and students don't want the same lesson twice in a day in the same way that you can't use the same digit twice in a row.

Specific Examples

Searching

A good example to consider when thinking about algorithms is the efficiency of searching. Imagine that someone is thinking of a number from 1 - 100, and you're trying to find out which one it is. You could ask, "Is it 1?", "Is it 2?", "Is it 3?", etc. This is called a linear search. If the person had chosen a number less than ten then you'd be OK, but, on average, you'd need to guess about 50 numbers before you got the right one.

A more effective method is to do what is called a binary search. If your first question is "Is it greater than 50?", then you've ruled out half of the possibilities with one question. That's why it's called a binary search - each question divides the number of possibilities by 2. If, for example, the number chosen was greater than 50, the next question would be "Is it greater than 75?". Using this method, you can find the number in no more than seven guesses.

You can compare the two methods in the Interactive section.

Sorting

The computing topic in which algorithms and efficiency are most frequently discussed is sorting. There are various sorting algorithms - some are always faster than others, and some are faster than others depending on the numbers being sorted - e.g. whether they're in reverse order, nearly sorted, random, etc. Some are easier to program, and some might be more tricky, so which one you use might depend on how many numbers you need to sort and how critical the performance is.

You can introduce the idea to KS3 Computing students and compare sorting algorithms, using your own numbers, in the Interactive section.

Quite often, when writing a program, you will want to sort some sort of list. I've done this myself on the Lottery page in the JavaScript section of the site. In that particular case there are only six numbers (i.e. performance isn't too great a consideration), so I went with the selection sort as it's easy to program.

Why not practice your sorting skills with the interactive games on Bubble Sort, Merge Sort and Insertion Sort?

Video

Watch the video on programming efficiency on the AdvancedICT YouTube channel.