METHODS OF PROOF
,ALGORITHM AND CORRECTNESS OF
ALGORITHM
Algorithm:
The word algorithm refers to a step-by-step method for performing some
action. OR
An algorithm M is a finite step-by-step list of well-defined instructions for
solving a particular problem, say, to find the output f (X) for a given
function f with input X. (Here X may be a list or set of values.)
Properties of Algorithms
Input: An algorithm has input values from a specified set.
Output: From the input values, the algorithm produces the output values
from a specified set. The output values are the solution.
Correctness of algorithm: An algorithm should produce the correct output
values for each set of input values.
,MATHEMATICAL PROOF OF ALGORITHM
CORRECTNESS
Proof by:
• Mathematical Induction
• Counterexample
• Direct Proof
• Indirect Proof
• Proof by contradiction
, PROOF BY INDUCTION
Mathematical induction is a very useful method for proving the
correctness of an algorithms.
Definition (Mathematical Induction)
1. Prove the formula for the smallest number that can be used in the
given statement. (Pre-condition – initial state)
2. Assume it’s true for an arbitrary number n.
3. Use the previous steps to prove that it’s true for the next number
n + 1. (Post-condition- final state)
,ALGORITHM AND CORRECTNESS OF
ALGORITHM
Algorithm:
The word algorithm refers to a step-by-step method for performing some
action. OR
An algorithm M is a finite step-by-step list of well-defined instructions for
solving a particular problem, say, to find the output f (X) for a given
function f with input X. (Here X may be a list or set of values.)
Properties of Algorithms
Input: An algorithm has input values from a specified set.
Output: From the input values, the algorithm produces the output values
from a specified set. The output values are the solution.
Correctness of algorithm: An algorithm should produce the correct output
values for each set of input values.
,MATHEMATICAL PROOF OF ALGORITHM
CORRECTNESS
Proof by:
• Mathematical Induction
• Counterexample
• Direct Proof
• Indirect Proof
• Proof by contradiction
, PROOF BY INDUCTION
Mathematical induction is a very useful method for proving the
correctness of an algorithms.
Definition (Mathematical Induction)
1. Prove the formula for the smallest number that can be used in the
given statement. (Pre-condition – initial state)
2. Assume it’s true for an arbitrary number n.
3. Use the previous steps to prove that it’s true for the next number
n + 1. (Post-condition- final state)
