Design and analysis of algorithms is the core field of research in which the designing of new innovative algorithms for some specific problem domains is done and then the in depth analysis of that algorithm design is done by considering various execution factors like CPU cycle requirement, memory requirements etc. As we said Algorithm let’s start with this…..
What is an algorithm?
An algorithm is a finite set of instructions that if followed accomplishes a particular task. An algorithm must satisfies the following criteria
1. Input : Zero or more inputs are supplied.
2. Output: Atleast one output should be produced as result of procedure.
3. Definiteness: Each instruction should be clear and unambiguous (i.e.) not more than one meaning.
4. Finiteness: If all the instructions are traced in algorithm, then for all cases the algorithm must terminate after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can be carried out briefly said “Operation must be feasible”.
Also algorithms that are definite and effective are also called as computational procedures. Operating system is the best example for this. Operating system(OS) is designed to control the execution of jobs in such a way that when no job are available, it do not terminate but continues in waiting state until a new job is entered. This waiting state of OS is generally known as sleeping threads.
What is program?
A program is the expression of an algorithm in a programming language. An algorithm can be implemented in any language as per the requirement of the process to be implemented.
Now whenever an algorithm is needed to be designed and analyzed generally there are following four questions that arise:
1. How to devise algorithm?[the most confusing thing among the newbies but the most interesting]
2. How to validate an algorithm?
3. How to analyze an algorithm? [this needs some sense of basic engineering mathematics and Discrete mathematics, so please brush up your very basic concepts not too much depth is required]
4. How to test a program? [this is done only after implementing the algorithm in some programming language]
Let us go through all the above mentioned how’s
How to devise an algorithm?
This is the most interesting and most sophisticated art which can never be fully automated. There are number of base techniques using which the algorithms are designed like dynamic programming, linear, non-linear techniques etc. and we are going to discuss them in future posts in detail. This is the first step which reap the seeds for analysis of the algorithm devised.
How to validate algorithm?
Once an algorithm is devised, it is necessary to show that it computes the correct answer for all possible legal inputs, this process is referred as algorithm validation. The purpose of validation is to assure us that this algorithm will work correctly and independently of the issues concerning the programming language. Once the validation of method is done, a program can be written and the phase of program proving or program verification starts.
How to analyze algorithm?
As an algorithm is converted into a program and is exceuted, it uses the computer central processing unit to perform operations and its memory to hold the program and data. Analysis of algorithm or performance analysis refers to determining how much computing time and storage resources an algorithm requires. This analysis allows:
(i) to make quantitative judgement about the value of one algorithm over another.
(ii) to predict whether the software implementing the algorithm will meet any efficiency constraint that exist.
During analysis of algorithm the following gategories were considered : Best case, worst Case and average case.
How to test a program?
Testing a program consist of two phases:
(i) Debugging: The process of executing program on sample data set to determine whether faulty error occurs & if so, correct them.
(ii) Profiling: The process of executing correct program on datasets & measuring the time and space it takes to compute the results. This helps in optimizing the algorithms. Profiling is also known as performance measures.
Above all four questions actually provides an idea about the concepts that Analysis of algorithm hold. In next post will be going to discuss in detail about complexities.
Reference for above contents is from Cormen , sahni and wiki.
No comments:
Post a Comment