It’s the holiday time of year: so a slightly lazy post for August. Adapted from a letter published in this month’s edition of Mathematics Today …
For anyone who’s worked in the ‘Twilight Zone’ between mathematics and computer science for any time, June’s Mathematics Today article, Urban Maths: A Roundabout Journey [on rounding issues in computer calculations], would have struck a distinct chord. They will have often come across situations in which mathematicians and computer scientists don’t quite see eye to eye. The following, fairly well-known, combinatorial exercise is another good example.
How many ordered ways are there of summing contributions of 1 and 2 to a given integer, n? So, for example, 1+1+2+1+1 and 2+2+2 are two of the 13 different ways of making 6. Call this number f(n) so that, in this example, f(6) = 13.
The standard combinatorial approach is to consider the first term. The only two options, 1 (leaving n-1 to make) and 2 (leaving n-2) lead readily to the recurrence relation f(n) = f(n-1) + f(n-2). Easy enough, yes, but the interesting question now is what to do with it?
Leave a comment | tags: Complexity, Fibonacci Sequence, Iteration, Recursion | posted in Algorithms, Computer Science, Mathematics, Programming, Software
(A case study in bad and good algorithm design. Hopefully, a bit of fun for anyone in a programming frame of mind, but also serving as a useful reference for the ‘Are There Any Hard Problems?’ post that follows.)
In ‘A Scandal in Bohemia‘ (Arthur Conan Doyle, 1891), Holmes and Watson discuss the difference between seeing and observing: “You see, but you do not observe [Watson]. The distinction is clear. For example, you have frequently seen the steps which lead up from the hall to this room.” “Frequently.” “How often?” “Well, some hundreds of times.” “Then how many are there?” “How many? I don’t know.” “Quite so! You have not observed. And yet you have seen. That is just my point. Now, I know that there are seventeen steps, because I have both seen and observed.”
Who knows; perhaps, if they hadn’t moved on to discuss more pressing issues (that King of Bohemia has a lot to answer for), Holmes may have set Watson something a little more interesting: “How many of these steps do you generally take in a single stride, Watson?” “I suppose one or two, Holmes, it varies; never three. Sometimes I take different combinations of one and two steps as the mood takes me” “Excellent, Watson; another challenge! So, taking these steps one or two at a time, in any combination you wish, how many different ways are there of climbing the seventeen steps?” “Well, I’m quite sure I don’t know, Holmes; rather a lot, I would imagine!” Continue reading
9 Comments | tags: Complexity, Exponential complexity, Fibonacci Sequence, Iteration, Program design, Recurrence relation, Recursion, Recursive definition, Software efficiency | posted in Academia, Algorithms, Computer Science, Computing, Mathematics, Programming, Software