Tag Archives: Complexity

Mathematicians and Computer Scientists

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?

Continue reading

Are There Any Hard Problems?

That looks like a hopelessly vague question, and it is unless we’re prepared to clarify it a bit.  On the other hand, we already know there are some impossible problems so surely there are some that are just hard?  Again, we’ll need to work out what on earth we’re talking about here.  Let’s start with what we actually mean by a problem in a computational sense …

(Be warned: There are one or two simplifications and liberties with precision in what follows; it’s well-intentioned but may upset the purist.)

Well, actually, even that isn’t simple and there’s no absolute agreement on what a good definition would be.  (We’ve seen previously that mathematicians and computer scientists don’t always see eye-to-eye.)  It’s cheating a bit but it’s probably easier to give examples and this should work well enough for us.  At least in the context of computing, these are all valid problems:

  1. Calculate    2 x 4 + 9 – 3
  2. If   5 – x  =  2   what’s x?
  3. Find the largest from    5, 7, 1, 4, 8, 5, 2, 4, 8, 5, 2, 6, 7, 7, 3, 3, 2, 4, 3, 6, 7, 7, 6, 5, 4
  4. Sort    25, 44, 66, 72, 12, 45, 56, 90, 45, 69, 11, 10, 12, 42, 88     into ascending order
  5. Arrange   1, 2, 3, 4, 5, 6, 7, 8, 9   into a magic square
  6. What’s the best way to get to Paris?

Continue reading

How to Write a Really Bad Program

(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