[40]

Introduction

Algorithm is any well defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. The word ‘algorithm’ comes from the name of a Persian author, Abu Jafar Mohammed ibn Musa Al Khowarizimi (825 AD), who wrote a textbook on Mathematics. A procedure for solving a mathematical problem in finite number of steps that frequently involves repetition of an operation; broadly: a step-by-step procedure for solving a problem or accomplishing some end (Webster's Dictionary).

An Algorithm is thus a sequence of computational steps that transform the input into the output. It is a tool for solving a well specified computational problem. It is the science that lets designers study and evaluate the effect of algorithms based on various factors so that the best algorithm is selected to meet a particular task in given circumstances. An algorithm is a sequence of unambiguous instructions for solving a problem i.e., for obtaining required output for any legitimate input in a finite amount of time.

Then what is a Program?

A program is the expression of an algorithm in a programming language, it is a set of instructions which the computer will follow to solve a problem.

Difference between Algorithm and Program

Algorithm Design Paradigms

General approaches to algorithm design:

• Divide and conquer

• Greedy method

• Dynamic Programming

• Basic Search and Traversal Technique

• Graph Theory

• Back Tracking

• Branch and Bound

How to analyze an Algorithm

There can be more than one algorithms for solving a particular problem one has to analyze them and use the most efficient one. The analysis of an algorithm is done base on its efficiency. The two important terms used for the analysis of an algorithm are “Priori Analysis” and “Posterior Analysis.”

• Priori Analysis: It is done before the actual implementation of the algorithm when the algorithm is written in the general theoretical language. In this, the efficiency of the algorithm is calculated based on its complexity. It is just an approximate analysis.

• Posterior Analysis: It is done after the actual implementation and execution of the algorithm using any programming language like C, C++, Java, or Python. It is the actual analysis in which the space and time complexity of the algorithm is calculated more correctly.

Difference between Priori and Posterior analysis

Characteristics of Algorithm

• Input: An algorithm can take 0 or more inputs.

• Output: An algorithm must produce at least 1 output.

• Definiteness: Every statement must be unambiguous. Every statement must have single and exact meaning.

• Finiteness: Finite set of statements. Algorithm must stop at some point of time.

• Effectiveness: No unnecessary steps in the algorithm. Every line written must contribute to the objective of solving the problem.

• Correctness: The algorithm must produce correct result.

• Generality: The algorithm must be applicable to all similar problems.

Study of Algorithms

Need for analysis

Software or any application especially those involving large dataset cannot be developed on trail and error basis. Programmers cannot waste time and resources in trying out all possible available alternatives to solve the problem at hand. Hence care must be taken at design phase in analyzing and filtering out the best suitable algorithm that solves the problem at hand.

Criteria to analyze an Algorithm

An algorithm’s performance depends on:

1. External Factors: Speed of the computer on which the runs. Quality of the compiler. Size of the input to the algorithm.

2. Internal Factors: Time required to run. Space (memory storage) required to run. Complexity measures the internal factors (usually more interested in time than space).

Two ways of finding Complexity

1. Experimental Study: Write a program implementing the algorithm. Run the program with inputs of varying size and composition. Get an accurate measure of the actual running time. Use a method like System.currentTimeMillis() (in Java). Plot the results

2. Theoretical Analysis: Computing space complexity for storage requirement and time complexity for calculating time. To analyze an algorithm, two things are taken into consideration:

Time

The amount of time an algorithm takes to run (the time is expressed as a function and not the watch time).The algorithm designed must be time efficient. Time complexity is the amount of time required by an algorithm for the execution and providing the desired output. It depends on the number of iterative or recursive steps involve in the execution of the algorithm.

Space

The memory space occupied by the algorithm (once implemented using any of the programming language). Space complexity is the amount of memory space the algorithm is required for giving the desired output. The memory space is consumed by the input data, temporary data, and output data of the algorithm.

Network Communication

The applications that are web based/internet based/cloud based then the amount of data transferred or network consumption also plays an important role. Performance analysis or analysis of algorithms refers to the task of determining the efficiency of an algorithm i.e., how much computing time and storage an algorithm requires to run (or execute). This analysis of algorithm helps in judging the value/compare one algorithm over another.