Q.11 What is an algorithm? Explain the termination and correctness of an algorithm.
Related Questions -
Q. What is an algorithm? Discuss basic characteristic of an algorithm. (AKTU. 2010-11)
Q. What do you mean by an algorithm? Explain the properties of algorithm.
(AKTU. 2011 - 12, 12 - 13)
Ans. Algorithm is a synonym for finite computational method with the additional property of finiteness. Every abstraction that belongs to the algorithm concept must have the termination property.
Computational Method :
· A Computational Method / Algorithm is a method for solvinging a specific type of problem by means of a finite set of steps operating on inputs.
· Input to a Computational Method / Algorithm: -
These are quantities given to it before execution of steps begins or during execution.
· Output to a Computational Method / Algorithm: -
These are quantities produced during the execution of an algorithm and they have a specified relation to the inputs.
· Data Independence of a Computational Method / Algorithm: -
This property ensures that steps of the method / algorithm are independent of the input quantities supplied. It means that data input to the algorithm must not change the steps of an algorithm.
· Definiteness of a Computational Method / Algorithm: -
It is the property that each step of the algorithm must have a precise definition which must be unique. It means that every step of an algorithm must convey one and only one meaning. If any step of an algorithm convey more than one meaning then that step is said to be ambiguous and it results an incorrect algorithm.
· Effectiveness of a Computational Method / Algorithm: -
It is a property of an algorithm that
(i) The algorithm will complete its execution in a reasonable amount of time.
(ii) The algorithm will require a feasible and reasonable amount of other hardware computing resources such as processors, memory etc.
· Resource Constraints of a Computational Method / Algorithm: -
It is the minimum amount of time and other computing resources such as processors, memory etc required by an algorithm to execute successfully.
· Correctness of a Computational Method / Algorithm: -
An algorithm is correct if for every input data that satisfy some condition, which is called precondition of the algorithm, the output data satisfy a certain predefined condition which is called the post condition of the algorithm.
· Termination of a Computational Method / Algorithm: -
Finiteness of computational method is the property that the number of steps in any execution of the method must be finite. The finiteness property is also called termination and the method is said to be terminating.
Q.12 Define the correctness of Algorithm with example.
Ans. Correctness of Algorithm: -
We say that an algorithm is correct if for every input data that satisfy some condition, which is called precondition of the algorithm, the output data satisfy a certain predefined condition, which is called the post condition of the algorithm. We give an example
Div (A, B)
1. R: = A/B
2. return R.
For this algorithm we have:
Pre-condition: A, B are real numbers and B 0
Post-condition: R = A/B
The proof of correctness of algorithm has two parts:
1. Partial Correctness: - If the algorithm will terminate then it will give the right result (the result will satisfy the post condition).
2. Termination: - Proof that the algorithm terminates.
Q.13 What are the steps of converting an algorithm to program? What specifications are required in doing so?
Ans. The stages of converting an algorithm to program are as follows.
1. Recognition of Need: -
It means to specify what is the actual problem for which algorithm is to be designed.
2. Feasibility Study: -
(i) It means to specify that whether there will be overall profit in solving the problem by designing its algorithm or not.
(ii) It also means to specify resources that are required solve the problem through that algorithm.
(iii) It ensures that all resources i.e. hardware as well as computing time are reasonable.
3. Analysis: -
It includes specification of detailed evaluation of all involved problems and sub-problems.
4. Design: -
It includes various specification like
(i) General design specifications
(ii) Detailed design specifications
(iii) Specifications of output, input, files and procedures involved.
In design stage it is specified, how the problem will be solved. It also includes design and analysis of efficient algorithms.
5. Program Construction and Testing: -
This step converts all types of previous specifications into programs by coding them into a suitable programming language.
A programming language that is chosen should have following properties.
(i) It should be preferably a special purpose programming language of the same problem domain for which the program is to be constructed.
(ii) It should be feasible to buy its license as most languages today are licensed.
(iii) It should not fail in actual implementation of software / program.
(iv) It should be compatible with diverse type of underlying hardware.
Testing of Program: -
Means -
(i) Unit Testing : It means to test single program individually.
(ii) Combined Module Testing : It includes testing of programs when combined together.
(iii) User Acceptance Testing : It includes testing of programs when they actually solve the problem.
6. Implementation: -
It means to actually deploy or install the software / program so that the program is ready to use.
7. Post Implementation And Maintenance: -
It means to fix any problem or to upgrade the program to make it better.
Q.14 What is stepwise refinement ? (AKTU. 2012 - 13)
Ans. Refinement of a program means to improve the quality of a program. There are various steps that lead to the refinement of a program. Altogether the process is known as stepwise refinement.
Step 1 : Find out which is the best type of strategy specialized algorithm that can be used to construct the program.
For Example : Divide and conquer algorithms are most suitable for sorting programs.
Step 2 : Find out which is the most suitable data structure for constructing that program.
For Example : Stack data structure is most suitable for programs that evaluate mathematical expressions.
Step 3 : Select the most suitable programming language for that application domain / problem domain.
For Example : (i) C, C++ are most suitable language for the application domain / problem domain of system softwares like operating system, linker, loader, etc.
(ii) Java, pHp etc are most suitable programming languages for web based applications.
(iii) SQL (Structured Query Language) is most suitable for constructing database application programs.
Step 4 : Construct the program using the language selected in step 3 and algorithm selected in step 1.
Step 5 : Design several input / output test cases and make sure that the program gives correct output for every corresponding input. If it does not happen even for a single test case the program is incorrect and needs to be checked. Rectify errors if any.
Step 6 : Try to make use of minimum number of variables and remove any extra variables. Extra variable require extra memory space and hence a bad memory optimization is achieved.
Step 7 : Try to avoid number of for loops, while loops do-while loops and nested loops. The greater the number of loops, the more is the time consumed and less time optimization is achieved.
Step 8 : Try to give comments before or after lines of code so as to refine the understandibility of program.
Step 9 : Keep checking for any refinement in steps 1 through 8 unless you prove that no more refinement is possible.
