Try something new. Everyday.

Monday, 8 February 2016

Algorithms and Computer Science

Why is computer science a science?

What is the difference between say Physics or Biology and Computer Science? Is there a difference at all?

Well for starters science constitutes of experimentation which makes if fundamentally difference from other subjects that may seem similar at first glance. The field of computer science is a machine science. It deals with a particular type of machine that we colloquially refer to as a PC or a personal computer. So why don't we have something like a tube-light science or a pressure cooker science?

That is something debatable but computers unlike a tube-light or a pressure cooker doesn't inherently have a singular purpose such as glowing or boiling your favourite veggies. If you can encode your thoughts in a precise and particular manner, the personal computer can function based on that. These may vary from solving problems that occur while studying particle physics and trying to make sense of the humongous amount of variegated data or as inconsequential as calculating the amount you spent on groceries at the market.

Alan Turing, the father of theoretical computer science wrote a scientific paper in which he described "computers" as people (mostly women at that time, primarily due to their patience while performing arduous calculations) who did math on pen and paper according to the whims of a set of sequential instructions also known as an algorithm.

Let's go back to the pressure cooker. 
Could there be a microwave oven science, since we already have one that caters to a pressure cooker? What cooks faster in a pressure cooker: a chicken or some potatoes? Potatoes or rice? Rice or wood? Wood or Iron? That escalated quickly.

On closer observation, there seems to be some sort of classification. Things that cook slow, other food items that cook quicker and some others, even quicker. And then there's this class of items that are so stubborn that they won't boil in a pressure cooker, like a piece of metal. Every science begins with classification and so does the one that deals with theoretical computer science.

Absurd as it may sound, in this context, we are dealing with the contents or what we can actually come up with, rather than the tool itself. We are worried about the chicken or the rice or perhaps the potatoes in the cooker rather than the humble pressure cooker itself. Similarly theoretical computer science at it's heart doesn't believe in discriminating based on the tool we use, whether it's a microwave oven or an old school pressure cooker, all we are worried about is getting nice boiled potatoes in the end. It doesn't really matter whether you have a super computer of this generation or a quantum technology powered device of the next era. This is what is computational complexity.

Things cooking at various speeds can be compared analogously to the various complexity classes in computer science, that instead of rating food items classify algorithms on their efficiency for easy comparison and deciding what maybe difficult for a computer to solve.

Difficulty is relative. Someone may find talking to a girl really difficult while another one may deem waking up early in the morning a difficult task. Many may also find it laborious to prove the Pigeon-hole principle. Computer science calls problems difficult that require at least exponential number of steps in the size of an input to an algorithm. But a database scientist may treat anything worse than a logN or a linear algorithm as inefficient. Depending on the context the definition of hardness may vary. The algorithms are compared in terms of the number of instructions required, space occupied (as a scratchpad), etc. These metrics are technology independent and that's where the universality lies. You'd compare them in the next century as you would in this. Doesn't matter what kind of specification the system has. The tool is just a means, it's the method that we bother about.

While mathematics has this puzzle kind of perspective to it. If you have solved a jigsaw puzzle or say a Rubik's cube, which you most certainly have, for the first time it may seem more of a challenge. But once you know how a jigsaw puzzle works and understand the concept behind it, you can solve any puzzle with the same technique. If you know how to computer 33+12, you can surely compute 132144+39427438 with little difficulty. Once a mathematical problem is solved, it is like you've become aware of the great magician's secret. Any local fair you visit and you see a person performing the trick you'll be aware of how it's done, irrespective of whether it's happening.

A solution for the travelling salesman problem for the cities in Germany.

On the other hand, computer science deals with skewing the problem. Let's say that now you take a 4x4 Rubik's cube to solve. What happens to your step-wise procedure? Does it work as expected or fails miserably? What happens to the number of steps when you consider a cube of an arbitrary size NxN? How much space does the computer need as a scratch pad to find a conclusive solution? Here, as soon as you fish out an algorithm it is then that you have even more questions to answer than you had to begin with in the first place.

P.S.: I attended a talk on algorithms and this is what it was all about. Really simple stuff but made a lot of sense. I thought I'd share it with my readers. :)

No comments:

Post a Comment