The word algorithm is come from the name of a Persian author, Abu Ja’far Mohammed Ibn Musa al Khowarizmi, who wrote a text book on mathematics. This word Algorithm has a special significance in computer science, where it refers to a methods that can be used by a computer for the solution of a problem.
What is the definition of Algorithm?
An algorithm is a finite set of instructions that if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria:
- Input: Zero or more quantities are supplied externally.
- Output: At least one quantity is produced.
- Definiteness: Each instruction is clear and unambiguous.
- Finiteness: If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
- Effectiveness: Every instruction must be very basic so that it can be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in case 3 but it also must be feasible.
What is difference between computation problem and instance?
Let us take problem of sorting a sequence of numbers into non decreasing order. Here is how we formally define this sorting problem.
Input: A Sequence of \(n\) numbers \(\lt a_1, a_2, …, a_n \gt\).
Output: A permutation (reordering) \(\lt a_1^\prime, a_2^\prime, …, a_n^\prime \gt\) of the input sequence such that \(a_1^\prime \le a_2^\prime \le … \le a_n^\prime \).
For example, given the input sequence \(\lt 31, 41, 59, 26, 41, 58\gt\), a sorting algorithm returns as output the sequence \(\lt 26, 31, 41, 41, 58, 59\gt\). Such an input sequence is called an instance of the sorting problem.
In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.
The study of algorithms include many important and active areas of research. There are four distinct areas of study one can identify.
1. How to devise algorithms
Creating an algorithm is an art which may never be fully automated. A major goal of algorithm courses is to introduce various design techniques that have proven to be useful as they have often yielded good algorithms. By mastering these design strategies it will become easier to devise new and useful algorithms.
2. How to validate algorithms
Once an algorithm is devised, it is necessary to show that it computes the correct answer for all possible legal inputs. This process of proving correctness is called algorithm validation. There is no need to express an algorithm in the form of program to validate. It is sufficient to state it in any precise way often in pseudo code. The purpose of validation is to assure that the algorithm will work correctly independent of whichever programming language used to implement it.
3. How to analyze algorithms
This field of study is called analysis of algorithm. As an algorithm is executed, it uses CPU to execute the instruction and memory to store the program and data. Analysis of algorithms or performance analysis refers to the task of determining how much computing time and storage an algorithm requires in platform and language independent way. This is challenging area, which sometime requires advance mathematical skill.
An important result of this study is:
- It allows us to compare two algorithm without implementing them.
- It enable us to predict, whether the software will meet any efficiency constraints that exists.
4. How to test a program
Testing a program consists of two phases:
Debugging is the process of executing the program on sample data sets to determine whether the faulty results occur and, if so, to correct them. However, as E. Dijkstra has pointed out:
Debugging can only point to the presence of error, but not to their absence.
Profiling or performance measurement is the process of executing a correct program on data sets and measuring the time and space it takes to compute the results. These timing figures are useful in that they may confirm a previously done analysis and point out logical places to perform useful optimization.
This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to email@example.com. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.