I love algorithms. I’m not good at them, but I think they’re a wonderful expression of human creativity. An algorithm is a formal procedure which – in simple terms – works out the answer to a problem. A good algorithm has few frills, is general and is usually beautiful and can be proved to give the right answer.
So here are two algorithms which I think are beautiful and slightly mystical. Each carries the author’s name. I’m going to leave you to work out what each does. I have created meaningless variables and names so as to give few hints. I have written them in Java, but you should be able to follow them (int means integer;
The original version of the first algorithm (using iteration) (!= means notEqual):
int foo(int a, int b) {
while (a != b) {
if (a > b) {
a = a  b
} else {
b = b  a
}
}
return a
}
“To Iterate is Human, to Recurse, Divine” wrote James O. Coplien of the legendary Bell Labs. Here is the same algorithm using recursion (a mod b means the integer remainder after dividing a by b):
int foo(int a, int b) {
return (b == 0) ? a : foo(b, a mod b)
}
Isn’t that beautiful? Even if you’re not a programmer you can see that it’s very clever to create an algorithm with only one line.
If you don’t recognize this algorithm you can probably work out what it does by running a few trial variables throuh it. But what about this one…
void foo(int c, int d, int e) {
int a = 0;
int b = c;
int sum = 3  2 * c;
while(a <= b) {
outputProcedure(a, b, d, e);
if (sum <= 0) {
sum = sum + 4 * a + 6;
} else {
sum = sum + 4 * (a  b) + 10;
b = b  1;
}
a = a + 1;
}
(* means multiply; <= means lessThanOrEqual). Here we pass 3 integers (c, d, e) into a routine which runs through a loop and outputs something each time. What does it output? What are c,d,e?
The numbers 2, 3, 4, 6, 10 are fundamental parts of the algorithm – I find this remarkable!
============
PS If any of you are still struggling with the mystery molecule, the answer is completely contained within http://wwmm.ch.cam.ac.uk/blogs/murrayrust/?p=160 – just save the picture.

Recent Posts
Recent Comments
 pm286 on ContentMine at IFLA2017: The future of Libraries and Scholarly Communications
 Hiperterminal on ContentMine at IFLA2017: The future of Libraries and Scholarly Communications
 Next steps for Text & Data Mining  Unlocking Research on Text and Data Mining: Overview
 Publishers prioritize “selfplagiarism” detection over allowing new discoveries  Alex Holcombe's blog on Text and Data Mining: Overview
 Kytriya on Let’s get rid of CCNC and CCND NOW! It really matters
Archives
 June 2018
 April 2018
 September 2017
 August 2017
 July 2017
 November 2016
 July 2016
 May 2016
 April 2016
 December 2015
 November 2015
 September 2015
 May 2015
 April 2015
 January 2015
 December 2014
 November 2014
 September 2014
 August 2014
 July 2014
 June 2014
 May 2014
 April 2014
 March 2014
 February 2014
 January 2014
 December 2013
 November 2013
 October 2013
 September 2013
 August 2013
 July 2013
 May 2013
 April 2013
 March 2013
 February 2013
 January 2013
 December 2012
 November 2012
 October 2012
 September 2012
 August 2012
 July 2012
 June 2012
 May 2012
 April 2012
 March 2012
 February 2012
 January 2012
 December 2011
 November 2011
 October 2011
 September 2011
 August 2011
 July 2011
 May 2011
 April 2011
 March 2011
 February 2011
 January 2011
 December 2010
 November 2010
 October 2010
 September 2010
 August 2010
 July 2010
 June 2010
 May 2010
 April 2010
 August 2009
 July 2009
 June 2009
 May 2009
 April 2009
 March 2009
 August 2008
 July 2008
 June 2008
 May 2008
 April 2008
 March 2008
 February 2008
 January 2008
 December 2007
 November 2007
 October 2007
 September 2007
 August 2007
 July 2007
 June 2007
 May 2007
 April 2007
 December 2006
 November 2006
 October 2006
 September 2006
Categories
 "virtual communities"
 ahm2007
 berlin5
 blueobelisk
 chemistry
 crystaleye
 cyberscience
 data
 etd2007
 fun
 general
 idcc3
 jisctheorem
 mkm2007
 nmr
 open issues
 open notebook science
 oscar
 programming for scientists
 publishing
 puzzles
 repositories
 scifoo
 semanticWeb
 theses
 Uncategorized
 www2007
 XML
 xtech2007
Meta
When I got into programming with microcomputers, what was most interesting was drawing things on the screen. Here is a graphical algorithm, whose result I won’t describe:
(1) Pick three points on the XY plane; let’s call them a, b, and c
(2) Place a point, p, at one of a, b or c
(3) Move the point p halfway from its current position to one of a, b, or c (chosen randomly)
(4) Repeat (3) indefinitely, plotting the point p on the screen
A good way of learning recursion, and depthfirst vs. breadthfirst is to:
(1) Draw a rectangle
(2) Recursively draw a smaller rectangle at each of the four corners of that rectangle.
(3) Try doing it depthfirst, vs. breadthfirst.
Also, drawing the Mandelbrot fractal with lots of nice colours is a good introduction to manipulating complex numbers.
(1) I haven’t run this so here’s my suggestions. (a) This is not deterministic so there can be no single answer. For example if the the random point is always C, then the point will slowly move to C. If the point is always the next in cyclic order (A,B,C,A,B,C…) then the point will converge (quite rapidly) to the vertices of an included triangle (I cannot work out the sides but I guess they are about 1/3 of the original. For a random distribution I’m guessing the results are similar but the triangle is somewhat larger.
I would be *very* impressed if you could figure out the solution without running the program. Try coding it – a picture tells a thousand words. 🙂
(3) All right. I have to decide yet again what graphics system I should aim for – GTK, Swing, or even SVG.
My latest guess is a Cantor set of some sort (perhaps a Sierpinski gasket) with an empty triangle in the middle
In the old days, this would take 5 minutes on a BBC to code up and run. Even in Windows with Qbasic, it was easy. The barrier is higher now…Python requires an additional module such as PyGame.
BTW, I *am* impressed 🙂
I just stumbled across these over the weekend… I am interested to know if there are any mistakes in the last algorithm foo(c, d, e)
d and e are never altered and don’t have any effect on the behaviour of foo.
(6) I don’t believe there are mistakes – I copied it from Wikipedia. d and e are simply passed to the output routine (whose name would give the game away). They are required in the real world, but are not involved in the algorithm.
Try running it with different values of c and tabulate a and b.
Pingback: Unilever Centre for Molecular Informatics, Cambridge  Staudinger’s Semantic Molecules » Blog Archive » D’oh…..