What is an algorithm?

"...an algorithm is a systematic method (i.e. a precisely defined sequence of rules) for solving a given problem. Its execution must not include any subjective decisions, nor must it require the use of intuition or creative thinking."

Luca Aceto, Department of Computer Science, Aalborg University.

"I agree with the subjective decision bit, but I reckon that elegant algorithms, like fine art, are creative thinking at its best."

Mark.Kelly, McKinnon Secondary College

What ISN'T an algorithm?

Algorithms are strategies for solving a problem - e.g. working out whether a year is a leap year or not. Algorithms are often represented by pseudocode, flowcharts or N-S charts. An algorithm is not coding : the coding is the implementation of an algorithm. The algorithm is the brainwork on how to achieve a result; programming is the nuts and bolts of making the idea come into effect.

If you are asked for an algorithm, you are not meant to produce code: you are meant to describe a process. Given an effective algorithm, any chimpanzee coder can crunch VB or C to get a module working. The genius, however, was in inventing the algorithm.

Approaching Algorithms - a personal tip

1. Research the topic. You will never create a successful algorithm if you don't know how to actually solve the problem yourself. e.g. to convert Roman numerals to decimal you need to know the Roman symbols and the conversion rules; to work out which years are leap years, you need to know exactly what the rule is. Google it - don't guess!

2. Devise a simple sample problem and work out the solution manually, step by step, with pen and paper.

3. For each step, ask yourself, "Exactly what was I thinking when I did that step? What exactly did I do? What exact decisions did I make?" Write them down - those decisions and actions ARE the algorithm!

4. When you think you have a working solution, repeat it with more complex sample data, especially with unusual or "tricky" samples that are possible, but not common. Does the algorithm still work? An algorithm that only works most of the time but fails spectacularly under certain conditions is not really an algorithm!

5. Document the algorithm using a clear, unambiguous method such as a decision tree, flowchart or pseudocode.

6. Congratulate yourself, then try to work out a completely different and more elegant way of achieving the same result using less memory, CPU cycles or lines of code.

7. You might finally code the alternative candidate algorithms, create some devilishly difficult test data and time the modules as they run a million times. Decide which coded algorithm is more efficient, stable and flexible.

Fun #1 - round any decimal number UP to the next highest multiple of 0.25. e.g. 4.23 => 4.25. 3.98 => 4.00

Fun #2 -  Convert any Roman number to decimal (e.g. MCMLXIX to 1969) - and/or vice versa

Fun #3 - find the lowest (or greatest) common denominator of 2 integers (or report that there is no LCD or GCD).

Fun #4 - list prime numbers up to 100

Fun #5 - simulate the display of a single-digit liquid crystal display
Assume there are 7 LCD bars like this
 _
|_|
|_|

Feed it any numeral or alphabetic character  in hexadecimal range (0 to F) and it should turn on the right bars.  (Efficiency is the key requirement here!)

Fun #6 - given a price including 10% GST, give the ex-tax price and the tax component, e.g. $11 inc = $10 ex + $1 GST.

Fun #7 - create a virtual deck of cards encoded as numbers 1 to 52.  Given any number from 1 to 52, the algorithm should return the suit and rank (e.g. 7 Hearts) represented by the card. Note: in the game 500, suits go from Spades, Clubs, Diamonds to Hearts: ranks are 2 to Ace.

Fun #8 - create an algorithm to shuffle the virtual deck of cards

Fun #9 - create an algorithm to play naughts and crosses - it should be unbeatable if the algorithm plays first.

Fun #10 – given a number of dollars, calculate what notes or coins need to be given as change from $100.  e.g. $67 = 1 x $20, 1 x $10, 1 x $2, 1 x $1.

Fun #11 - given any year, your algorithm says how many days are in February of that year. Hint: what exactly is a leap year?

Fun #12 - create an algorithm that will detect if a hand of 5 virtual cards contains a pair of the same rank. (Extend to - three or four of a kind, or a straight, or a flush, or royal flush). Finish with a medal if you can compare two hands and determine which one wins according to Hoyle.

Fun #13 - Create a virtual chess board and populate it with the correct pieces for the start of a game. Be sure to cater for the black and white starting positions of the queen.

Fun #14 - You have a new, full, shuffled deck of cards and are playing blackjack (pontoon, 21, vingt et un). You are dealt a king and a four. What are the odds of the next card giving you exactly 21?

Any suggestions for other neat algorithms?