Hello Readers, we all have heard about Algorithms in computer science. Many of us have wrote and created algorithms for different problems to solve but we always have wondered concept of algorithms itself. So in this post, I will try to expand on the concept itself, my understanding of it and some noteworthy points we should remember while working with algorithms. But before everything is started, what is an algorithm? Algorithm is well defined computational procedure i.e. sequence of computational steps, that takes some set of values as input and produces some set of values as output. It is a tool for solving well specified computational problem, thus achieving desired relationship between input and output.
Instance of a problem consist of input which satisfies all constraints set by problem statement, needed to compute a solution to the problem. So an algorithm is said to be correct if for every input instance, it halts with correct output. Thus correct algorithm solves given computational problem. That means, incorrect algorithm won't be able to halt at all for some input instance or halt at some incorrect answer. But does it mean incorrect algorithm are useless? Not at all, if we can control error rate, even incorrect algorithm is useful.
There are some problems for which no efficient solution is known. Here we are not discussing exact definition but we are only considering set of problems for which algorithm can be a magically guessed which will solve problem in polynomial time. A subset of such interesting problems are called NP (nondeterministic polynomial) problem. For NP complete problem, even though no efficient algorithm is found yet, it is also not proved yet that no efficient algorithm exists. One interesting property of NP complete problem set is that, if even a single problem has efficient solution exist, that means all the problems in set would have efficient solution in existence. Also here interesting thing to note is that, even though for a problem there exist an efficient solution, a slight tweak in problem and that problem may become NP complete.
With current fast evolution of technology, do we really need to have efficient algorithm, question every computer science enthusiast should think about. Any problem can be solved with different algorithms which may have different efficiency. In real world, computers have limited with their speed, memory and resources. So with different algorithms, however, may written with best standard software practices, computers may take different times either to completely run algorithm or may get crashed due to lack of resources. With such situation, it is far more necessary to have most efficient algorithm for particular problem.
Algorithms are core at every technology and so this leads to continuous research, development and enhancement of algorithms. For computer enthusiast, Algorithms research is considered to be great opportunity.