jeudi 30 juin 2011

Discution Question: About Algorithms

 

What makes one algorithm better than another?

To determine which algorithm is better than another, often we compare the efficiency of one or the other. The efficiency of an algorithm is mostly associated to the time the latter takes to perform a task according to the amount "n" of the inputs, but it can also be related to any other computational resources as memory usage, required to perform the task.

Depending about inputs, there are 3 scenarios. Best-Case (input offer optimal condition), Average-Case (input has uniform distribution) and Worst-Case. The worst-case is used to define the upper bound of resource usage with non optimal input and is the most used scenario in algorithm analysis.

For the same problem (and needs), the best algorithm will be the one that will consume less resources than other in worst-case

An example of problem

To illustrate above, let us take the well know sorting list problem, and compare the Merge sort and Timsort algorithm

Merge sort was developed by John Von Neumann in 1945. The unsorted list is split in 2 and each sublists are sorted recursively using the same algorithm until sublist with a length of 0 or 1 is found (sorted). Then each sorted sublist is merged into one list. (The pseudo code can be found at http://en.wikipedia.org/wiki/Merge_sort)

Timsort a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language (Wikipedia, 2011).

Worst-case for both are O(nlogn), but timsort have Θ(n) for best-case and merge sort O(nlogn). This means that timsort and merge sort will have similar behaviour in worst-case but timsort will be more efficient in best case than merge sort.

Why programming is considered as an art

Science (from Latin word scientia meaning knowledge) is more about logical, rational, testable, explainable, reproducible facts that can be expressed in form of statement, laws, theorem etc and form a formal knowledge that can be taught. Science tends to be objective.

Art (from Latin word ars, artis standing for skills) is more about inspiration, creativity, beauty, skills, insight or enlightenment. Art tends to be subjective.

Programming is about solving problem and “teaching” a computer to execute the solution to the problem. One of programming step is the discovery of algorithm that will describe the solution executions steps. And as all discovery and solving problem process, there are no formal procedure that can be entirely applied successfully since the process induce insight, skills that cannot be objectively explained or reproduced, artistic sense, observation, etc. All these elusive qualities found in Art that allows classifying programming as art.

But programming is also science. There are formal procedure, laws, theorems, build from the past experience and knowledge in computer area. Donal Knuth, in 1974, have talked about “Computer programming as an Art” and at my point of view, provide the best description about this duality about programming.

Why neither of the solutions that you provided can be generated with a prescribed methodology

Even if some scientist as Georges Poly (Brookshear,2008, p.216) has tried to formalize the process of solving problem, there are still the insight inherent to creative activity that will “make appear” the solution to solver. For instance, the Tim Peter has taken the performance of insertion sort on best-case and merge sort on worst-case to provide an algorithm that perform efficiently on both case where these two was not competitive. This insight cannot be formalised by procedure known so far.

How do you envision the ways program verification and performance tuning will be accomplished in the future? Will it still be a work of art? Will it always be the result of one's experience?

Computing is augmenting our mind the same way industrial revolution has magnified what hands and arm can do(Moore,2005). In this quest, computer scientists are ultimalty searching for algorithms that could reproduce the solving problem processes (brookshear,2010, p.216). Even if it has been shown to be impossible, this research has produced numerous concepts and tools that help human mind in the process of solving problem, that detect conceptual errors or potentials issues that could arise on runtime in programs.

Based on that and personal observation about computer science evolution, I thinks in the future, program verification and performance tuning will be assisted by computer as done by syntax checker in current IDE with the possibility to automatically apply the best algorithm that suit to a particular context.

But the part of human skills will still be required, unless computer since capture the essence of intuition, enlightenment and dream that is unique (as we know) to human being. So there still be a part of art and experience in this area, even if assisted by computer.

Reference List:

Publié par à
Libellés : , , , , ,

Aucun commentaire:

Enregistrer un commentaire

Inscription à : Publier les commentaires (Atom)