Now the distinction between “theory” and “practice” is often conceptualised as opposing ends of a spectrum. Maybe you consider the former admirable for being pure, maybe the latter for being useful – I mean, people can have a difference in taste here, right, and I’m not interested in arguing one way or the other. Recently on Twitter I saw Jeremy Cohen make the argument that a one-dimensional view of theory versus practice is not very productive.…

Last time I asked how to sort one million 32-bit integers. That sounds like a fairly concrete question that we should be able to answer, but even in our quick experiment it turned out the contents of the list matter quite a bit. And here we see that there’s a bit of difference between what you learn in an undergrad algorithms class and how things work out in practice. You may heard that insertion sort is efficient on nearly-sorted lists.…

At Uni Würzburg I was sometimes involved with the first-year algorithms and data structures exam. We usually had a question where we make you pick the appropriate sorting algorithm for a particular situation. And it was always kind of hard to come up with the exact scenarios, because the theory just isn’t very granular. Here: let’s try it. This is from an interview that subsequent president of the United States of America, Barack Obama, gave at Google.…

(You can watch the video version of this post on YouTube.) We’ve talked about “reasonable encodings” of integers, and why that matters, but what about real numbers? You could give a finite expansion, that’s fine, or use rational numbers - though in either case you might have to be a little bit careful about how large your representation is and, uh, if you can actually work with that representation efficiently.…

(You can watch the video version of this post on YouTube.) I would like to take you on a bit of a journey. We will start out by looking at some very high level stuff – philosophy of science, if you want to call it that. We don’t usually talk about that in algorithms classes, because we take it for granted. But if we want to talk about algorithms in practice, we kind of need to talk about what we mean when we talk about algorithms in theory.…