Recipes for Computing

I love Turkish food (try it and you will see why). Unfortunately, there are very few Turkish restaurants in US and there isn't any in Santa Barbara. So, when I want to eat a Turkish dish, I have to make it myself. Luckily, I have several Turkish cookbooks that contain recipes for most of my favorite dishes. Without those recipes I would need to fly back to Turkey to eat the food I like (which is not a short flight).

But why am I talking about cooking and recipes? Because in this post I want to talk about a concept computer scientists call "algorithm" and the best analogy I can find is that an algorithm is like a recipe.

Let's first think about what a recipe is. A recipe is a description of how to take a bunch of ingredients and process them to generate the output you want: something to eat. So, the first thing a recipe describes is the list of ingredients, which are the input to the cooking process. Then, the recipe gives you step by step instructions on how to process the ingredients. At some point the recipe tells you that the food is ready to eat, and that is when the cooking process ends.

An algorithm is a recipe for computing. An algorithm describes how to take an input, say a set of numbers, and transform them into an output, say another set of numbers. Like a recipe, the algorithm gives step by step instructions on how the input (the ingredients) are processed to produce the output.

Using algorithms you can write programs, but an algorithm is not a program. You cannot take an algorithm and run it on a computer. You see, the algorithms are not written for computers, they are written for people. A programmer has to take the algorithm and translate it to a language that a computer can understand (we call those programming languages). In fact, there are books on algorithms and, like cookbooks contain recipes for cooking, algorithm books contain recipes for computing that programmers use to build their programs. Depending on the type of computing you want to do, you can open one of these algorithm books and pick a recipe. Then, you can translate that recipe to the computer's language to do the computing.

It is time for an example. Assume that I want to do the following computation: Given a set of numbers, I would like to produce a list that lists the given numbers in ascending order. In other words, I want to sort a set of numbers using a computer. How can I do it? Well, many computer scientists already thought about this and they came up with many sorting algorithms. If you pick one of them and write it in a programming language, you will end up with an implementation of the sorting computation. (The task of translating the algorithm to a language that computers understand is called implementing the algorithm).

It turns out that the best way to sort a list of numbers using computers is the following: First divide the given list to a bunch of lists that are as small as possible. Well, the smallest possible list is a list of size one, so we will first divide the input list to a bunch of lists of size one. Here is the nice thing, a list of size one is always sorted! Now start merging the lists. The key is, you can assume that you are always merging sorted lists since we start with lists of size one which are always sorted. And, it is not difficult to merge two sorted lists to obtain a merged sorted list. You can just go over the two lists together while always removing the next smallest element (which is going to be in front of one of the lists) and adding it to the merged list. If you keep merging the lists, eventually you will obtain one sorted list which is what we wanted. The algorithm that describes this process is called the merge sort algorithm.

But why do I think that this is the best way to sort a list of numbers? How can one know if an algorithm is better than another algorithm? This is a question that computer scientists study a lot. Let me make it more clear. Assume that there are two algorithms that produce identical outputs for the same input. So, in terms of getting the computation done, they are both good. How can I say one is better than the other if they can both get the job done? It is like having two recipes for cooking a pie where both recipes use identical ingredients and produce identical pies. So, then, which recipe would you prefer? I don't know about you but I would prefer the recipe that gets me the pie as fast as possible. In comparing algorithms, we think the same way, we prefer the algorithms that get the computation done as fast as possible.

There is a problem with this. As I said before, algorithms do not run on computers so we cannot measure the time it takes to get the computation done on a computer without implementing the algorithm. Can we measure how fast an algorithm is without implementing it and running it on a computer? Well, I can figure out how long it will take me to cook with a recipe without actually cooking with the recipe. I can count the number of steps required to cook with a recipe and add the length of each step to get the total time. If I am comparing two recipes, I can count how many steps each recipe requires and pick the recipe with the smallest number of steps. But number of steps required for cooking can change based on how many people are invited to dinner. A recipe may require me to repeat a certain number of steps for each person I am cooking for (like seasoning each steak separately) and a recipe can also contain certain number of steps that does not depend on how many people I am cooking for (like heating the grill). So depending on the number of people we are cooking for different recipes could be faster. But, if you want to cook for a large number of people, you are likely to pick a recipe which requires the least amount of work for each person.

We use the same basic ideas in comparing algorithms. For each algorithm we count the number of steps required and then we pick the algorithm with smallest number of steps. When we are counting the steps in an algorithm we divide the algorithm to small enough steps so that the length of each individual step is the same. Like with recipes, the number of steps required can depend on the size of the task. For example, for the sorting algorithm, the number of steps required will depend on the size of the input list. In studying an algorithm, computer scientists first figure out the relation between the input size and the number of steps required for the algorithm. When choosing an algorithm we typically pick the algorithm that requires the least amount of work for each input. Such an algorithm will produce the fastest program when a programmer translates that algorithm to a program.

There is another important criteria one can use in choosing an algorithm. Assume that you have a small kitchen and what you really care about when choosing a recipe is the amount of pots and pans you will need to get the cooking done. Since you do not have too much space in your kitchen you want the recipe that will let you cook using the smallest amount of space. And, this may be more important for you then the amount of time it takes to cook. The analogous concept in computing is the amount of intermediate results one requires to store while computing. The space required for storing the intermediate results could be very large and the computer we plan to use may not have a lot of memory. If that is the case, one can prefer an algorithm that requires more number of steps as long as it requires less amount of memory.

Algorithms are a very important body of knowledge for computer scientists. They save us from reinventing the wheel every time we write a program. When we are faced with a computing task, we first ask ourselves if we can use some existing algorithm to solve that task. Actually, a single program is likely to use many algorithms, not just one. Typically there are many subtasks a program has to do and each one may require a different algorithm. But there will be times when you will be faced with a task without a known algorithm. Then you have to make up your own. It is like creating your own recipe for your own dish. The knowledge of existing algorithms is very helpful when you are making up your own algorithm. There are some basic approaches to developing an algorithm, like different cuisines for cooking, and based on the problem you are facing you can use one of the existing approaches to develop your own algorithm. The more styles of cooking you know the more likely you will be able to develop the best recipe for the occasion. And, while developing your recipe you may want to pay attention to how long it is going to take to cook the dish and how much space you are going to need to cook it.

Like creating your own recipe, creating your own algorithm is a very creative activity and, in  my view, it is one of the most fun activities for a computer scientist. You may base your algorithm on some existing styles, but in the end the algorithm you come up with is your own recipe. And if it is really good it may end up in a cook/algorithms book one day and other people can cook/program with it!