Introduction to Algorithmic strategies
An algorithm is a finite set of instructions to accomplish a particular task. It is a step-by-step procedure for solving a given problem. An algorithm can be implemented in any suitable programming language.
Algorithms must have input, output and should satisfy the following characteristics such as definiteness, correctness and effectiveness. Data are maintained and manipulated effectively through data structures. Algorithms can be developed to store, manipulate and retrieve data from such data structures. Examples for data structures are arrays, structures, list, tuples, dictionary etc.
To search an item in a data structure using linear and binary search.
To sort items in a certain order using the methods such as bubble sort, insertion sort, selection sort, etc.
To insert an item (s) in a data structure.
To update an existing item (s) in a data structure.
To delete an existing item (s) in a data structure.
The way of defining an algorithm is called algorithmic strategy. For example to calculate factorial for the given value n then it can be done by defining the function to calculate factorial once for the iteration-1 then it can be called recursively until the number of required iteration is reached.
An algorithm should have the following characteristics:
Zero or more quantities to be supplied.
At least one quantity is produced.
Algorithms must terminate after finite number of steps.
All operations should be well defined. For example operations involving division by zero or taking square root for negative number are unacceptable.
Every instruction must be carried out effectively.
The algorithms should be error free.
Easy to implement.
Algorithm should be clear and unambiguous. Each of its steps and their inputs/outputs should be clear and must lead to only one meaning.
Should be feasible with the available resources.
An algorithm should be generic, independent of any programming language or an operating system able to handle all range of inputs.
An algorithm should have step-by-step directions, which should be independent of any programming code.
Algorithms are generic and not limited to computer alone. It can be used in various real time activities also. Knowingly or unknowingly we perform many algorithms in our daily life such as packing books in school bag, finding shortest path to search a place, scheduling day-to-day activities, preparation for examination, etc. As we know that all programming languages share basic code constructs like conditions and iterations can be used to write an algorithm. A typical algorithm is shown in the following Figure 4.1.
Consider the example of Coffee preparation. To make coffee, we need to have the following ingredients: Water, milk, coffee powder and sugar. These ingredients are the inputs of an algorithm. Preparing a cup of coffee is called process. The output of this process is coffee.
1. Take a bowl with coffee powder
2. Boil the water and pour it into the bowl
3. Filter it
4. Boil milk
5. Mix sugar and filtered coffee along with boiled milk
6. Pour the coffee into the cup to serve
This kind of procedure can be represented using an algorithm. Thus, the algorithm consists of step-step-by instructions that are required to accomplish a task and helps the programmer to develop the program.
Problem: Design an algorithm to find square of the given number and display the result.
The algorithm can be written as:
Step 1 – start the process
Step 2 – get the input x
Step3 –calculate the square by multiplying the input value ie., square ← x* x
Step 4 − display the result square
Step 5 − stop
Algorithm could be designed to get a solution of a given problem. A problem can be solved in many ways. Among many algorithms the optimistic one can be taken for implementation.
Computer resources are limited. Efficiency of an algorithm is defined by the utilization of time and space complexity.
Analysis of an algorithm usually deals with the running and execution time of various operations involved. The running time of an operation is calculated as how many programming instructions executed per operation.
Analysis of algorithms and performance evaluation can be divided into two different phases:
1. A Priori estimates: This is a theoretical performance analysis of an algorithm. Efficiency of an algorithm is measured by assuming the external factors.
2. A Posteriori testing: This is called performance measurement. In this analysis, actual statistics like running time and required for the algorithm executions are collected.