Introduction to Algorithmic strategies

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.

Search

To search an item in a data structure using linear and binary search.

Sort

To sort items in a certain order using the methods such as bubble sort, insertion sort, selection sort, etc.

Insert

To insert an item (s) in a data structure.

Update

To update an existing item (s) in a data structure.

Delete

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.

Characteristics of an Algorithm

An algorithm should have the following characteristics:

Input

Zero or more quantities to be supplied.

Output

At least one quantity is produced.

Finiteness

Algorithms must terminate after finite number of steps.

Definiteness

All operations should be well defined. For example operations involving  division by zero or taking square root for negative number are unacceptable.

Effectiveness

Every instruction must be carried out effectively.

Correctness

The algorithms should be error free.

Simplicity

Easy to implement.

Unambiguous

Algorithm should be clear and unambiguous. Each of its steps and their inputs/outputs should be clear and must lead to only one meaning.

Feasibility

Should be feasible with the available resources.

Portable

An algorithm should be generic, independent of any programming language or an operating system able to handle all range of inputs.

Independent

An algorithm should have step-by-step directions, which should be independent of any programming code.

Writing an Algorithm

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.

Example

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.

The procedure for preparing coffee is as follows:

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.

Analysis of Algorithm

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.