Last Tech Tuesday, we looked at complexity classes which group problems by their intrinsic difficult. There we encountered one of the great unsolved questions of Computer Science. Is P = NP? The class P is easy to define. It is the set of all problems that can be solved by a Turing machine in polynomial time, i.e O(n^k) for some k. So you might think that NP stands for non-polynomial time but you’d be wrong. Instead the class NP has the same definition as P except for a non-deterministic Turi...

The last few weeks in Tech Tuesday we have looked at various aspects of computational complexity. So far whenever we have looked at a sample problem, such as finding words on a web page, we have studied the characteristics of a particular algorithm for solving the problem (in many cases starting out with looking at a brute force solution). But we have skirted the central question of computational complexity: how hard is the problem? Or asked differently, for a given problem, what is the best ...

The last few Tech Tuesdays have all been about computational complexity. One of the problems that we looked at a couple of times was finding a match (eg a word on a page). And for good reason as matching is a very common real world task. One important practical consideration that I mentioned briefly before is: are we doing a one-off match or will we run many matches against the same data? Why is this important? Because if we know that we will do many matches or lookups we can do some or a lot...

Today’s Tech Tuesday will let you in on a bit of computer science secret language. Sometimes when discussing a solution to a problem an engineer will say something like “that’s too slow – it’s O of n squared” (that’s the letter “O” not a zero). What does it mean? Well it is a shorthand way of describing the growth behavior in the time or space required by an algorithm as n (the number of things we are processing) grows large. More formally it is known as “Big O Notation.” As we have seen in t...

In the last two Tech Tuesdays, I introduced the topic of computational complexity. Today as promised I want to dig a bit deeper into the question of best, average and worst case complexity. The canonical example used for this is sorting. For simplicity we will assume that we are sorting a list of numbers. Several different sorting algorithms have been developed over the years that go by fun names such as Insertion Sort, Quicksort and even Bubble Sort (here is a past Tech Tuesday three-part in...

Last year’s Tech Tuesday ended with a first look at computational complexity. We saw how crazily long a brute force attempt to find a 40 character string would take. This was the result of exponential growth in the runtime of our algorithm. Today we will start to dig a bit deeper. Let’s consider a very common problem: checking whether a word is part of a group of words. For instance, if you use the “find on page” feature in your browser you can check if this page contains the word “freezing” ...

So far in the Tech Tuesday series on the theory of computer science we have covered questions of computability. We have looked at ways of formalizing computation through abstract machines such as the Finite State Machine and the Turing Machine to explore limits on what can be computed at all. We saw with the Halting Problem that the power to compute lots of things is gained at the cost of not being able to say much about the computation (e.g. will it stop?). Now we will turn our attention to ...

My two favorite quotes these days are Ward Cunningham’s “What’s the simplest thing that could possibly work?” and Einstein’s “Simplify as much as possible, but no further.” I believe these to be essential to startup success, especially in a highly connected world, where what might have previously been a feature can now be a company. The temptation, however, always goes in the other direction of making things too complicated or complex. Hence the title of this post. Here are just some of the t...