What is Algorithm and properties of Algorithm.

  What is Algorithm and properties of  Algorithm.

A finite set of instruction that specify a sequence of operations to be carried out in order to solve a specific problem or class of problems is called an algorithm.An algorithm is an abstraction of a program to be executed on a physical machine.A problem to solve the design phase produces an algorithm.Algorithm are very popular design approaches.Just like Divide and Conquer,Greedy Approach,Dynamic programming.Therefore an algorithm can be defined as a sequence of definite and effective instructions while terminates with the production of correct output from the given input.

Difference between Algorithm and Program 

Problem to solve the design phase produces an algorithm and the implementation phase then produce a program that expresses the design algorithm.Main difference between program and algorithm is Algorithm must complete after a finite number of instructions have been executed program does not have to satisfy the finiteness condition.     

  Algorithm must have the following properties

• Finiteness.
• Absence of ambiguity.
• Definition of sequence.
• Feasibility.
• Input/Output.

Finiteness

Algorithm must complete after a finite number of instructions have been executed. 

Absence of Ambiguity

Each step must be clearly defined having only one interpretation.Thus every step should be made unambiguous.An unambiguous step is called definite instruction.

Definition of sequence

Each step must have a unique defined preceding and succeeding step..First step and Last step must be clearly noted.

Feasibility

It must be possible to perform each instruction.

Input/Output

Number and types of required inputs and results must be specified.

Example

Problem 

Man brushing his own teeth as an algorithm

Algorithm

Step 1: Take the brush.

Step 2: Put the paste on it.

Step 3: Start brushing.

Step 4: Clean

Step 5: Wash

Step 6: Stop.

Algorithm Design Techniques

• Divide and Conquer.
• Greedy Approach.
• Dynamic Programming.
• Branch and Bound.
• Randomized Algorithm.
• Backtracking Algorithm.

 An algorithm is a step by step formalization of a mapping function to map input set onto an output set.

  

Divide and Conquer

Divide the original problem into a set of sub problems and solve every sub problem .Combine the solutions of sub problems of the sub problems into a solution of the whole original problem.   

Greedy approach

which are the best locally but do not look at the global problem.The result is a good solution but not necessarily the best one.

Dynamic Programming

It is a method of solving problem of  overlapping sub-problem and optimal substructure that takes much less time.

Branch and Bound

Given sub problem which cannot be bounded has to be divided into at least two new restricted sub problems.

Randomized Algorithm

An algorithm that is allowed to access a source of independent,unbiased random bits and it is then allowed to use these random bits to influence its computation.

Backtracking Algorithm 

Backtracking Algorithm try each possibility until they find the right one.Example Depth first search.