2. Characteristics of Algorithm.ppt

Characteristics of an algorithm

1. 1. What is Algorithm?
2. Characteristics of Algorithms
Properties of AlgorithmWhat is an Algorithm ?

2. 1. What is Algorithm?
2. Characteristics of Algorithms
Properties of AlgorithmWhat is an Algorithm ?

3. Properties of AlgorithmWhat is an Algorithm ?
An algorithmis a
is a sequence of unambiguous instructionsfor solving a problem, to obtain
a required outputfor any legitimate inputin a finite amount of time.

4. 1. What is Algorithm?
2. Characteristics of Algorithms
Properties of AlgorithmWhat is an Algorithm ?

5. Characteristics of an Algorithm
1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:
Simplywritingthesequenceofinstructionsasanalgorithmisnotsufficientto
accomplishcertaintask.Itisnecessarytohavefollowingpropertiesassociated
withanalgorithm.
Properties of Algorithm

6. Problem
Statement
Algorithm
Design
Program
Programming
Language
Statements
C/C++
Statements
Analysing
Algorithm
Correctness
of
Algorithm
Algorithm Design and Analysis
Analysis 2
Analysis 1
Solving a Problem With a Computer
Algorithmic Problem Solving
Algorithm
Design

7. 1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:
Characteristics of an Algorithm Properties of Algorithm

8. The range of valuesfor which an algorithm works has to be specified carefully
1. Input
Thisalgorithmdoesnotworkcorrectlywhenoneofitsinput
numbersiszero.
Thisillustrateswhyitissoimportanttospecifythesetofan
algorithm’sinputsexplicitlyandcarefully.
GCD (m , n )
t= min(m, n)
while (t<=0) {
if (m % t = 0){
if (n % t = 0)
return t;
}
t = t –1;
}
Greatest Common Divisor :(Consecutive Integer Checking Algorithm)
Every algorithm has zeroor more inputs:
these inputs are taken from specified set of objects.
Here,twoinputsmandnaretakenfromthesetofpositive
integers.
Therefore,
Properties of Algorithm

9. 1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:
Characteristics of an Algorithm Properties of Algorithm

10. From each set of input values, an algorithm producesoutput valuesfrom
a specified set.
An algorithm has oneor more outputs:
The algorithm must clearly define what output will be yieldedand it should
be well-definedas well.
1. Output Properties of Algorithm

11. Characteristics of an Algorithm Properties of Algorithm
1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:

12. 3. Finiteness
An algorithm must always terminateafter a finite number of steps.
Euclid’s Algorithm
Given two positive integers m and n, find their greatest common divisor.
GCD (m , n )
Step 1 divide mby nand
let rbe the remainder. ( 0≤ r< n )
Step 2 if r= 0, terminate, nis the answer
Step 3 Set mn, nrand go backto Step 1
This algorithm satisfiesthe condition of finiteness, because
the value of rdecreasesevery time the Step 1is encountered.
the value of rbecomes 0after finite number of steps, So, algorithm must terminate
Properties of Algorithm

13. 15
6
Case 1: The lengths of line segments are commensurable
3. Finiteness Properties of Algorithm
Commensurablemeans
having a common measure
Find the “Greatest Common Measure“ of the two line segmentsExample:

14. 15
6
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

15. 9
6
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

16. 9
6
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

17. 3
6
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

18. 3
6
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

19. 3
3
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

20. 3
3
3. Finiteness Properties of Algorithm
Find the “Greatest Common Measure“ of the two line segments
Case 1: The lengths of line segments are commensurable
Example:

21. 3
3. Finiteness
3 is the “Greatest Common Measure“ of the these two line
3. Finiteness Properties of Algorithm
Case 1: The lengths of line segments are commensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:
Algorithm mustterminate in case ofcommensurable line segments
So, fulfils the property of Finiteness

22. The algorithm does not terminate if the given lengths are incommensurable.
3. Finiteness Properties of Algorithm
Find the “Greatest Common Measure“ of the two line segmentsExample:
Incommensurable:
having no common standard of measurement.
Case 2: The lengths of line segments are incommensurable

23. What if we try to find the “greatest common measure” of the sideand the diagonalof a square?
5
5
5
5
Apply Euclidean algorithm to find the “greatest common measure” of the sideand the diagonalof a
square.
Here side and diagonal’s lengths are incommensurable.
It doesn’t end.
Case 2: The lengths of line segments are incommensurable
3. Finiteness Properties of Algorithm
Find the “Greatest Common Measure“ of the two line segmentsExample:

24. 5
5
5
5
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

25. 5
5
5
5
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

26. 5
5
5
5
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

27. 5
5
5
5
3. Finiteness3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

28. 5
5
5
5
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

29. 5
5
5
5
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

30. 5
5
5
5
3. Finiteness3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

31. 5
5
5
5
3. Finiteness3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:

32. 5
5
5
5
it doesn’t end.
3. Finiteness Properties of Algorithm
Case 2: The lengths of line segments are incommensurable
Find the “Greatest Common Measure“ of the two line segmentsExample:
The algorithm does not terminate if the
given lengths are incommensurable.
So, a methodto find Greatest Common Measure of two line segments of incommensurable lengthsis
not a legitimate algorithm-It is just a computational method
Violating Finiteness

33. An algorithm must always terminateafter a finite number of steps.
If it is already proven to be correctto the extent that it will produce the desired resultsand
terminate, then
it is inefficientand needs tuning up.
3. Finiteness Properties of Algorithm

34. Example 1
Supposewedevelopanalgorithmtogenerateallsentencesinalanguage.Everytime
anewsentenceisgenerated,itisprintedout.Now,asatypicallanguagehasan
infinitenumberofpossiblesentences,thealgorithmasspecifiedwillneverterminate.
Insuchcases,theterminationconditionisunderstoodtomeangenerationofan
output,whichistheinnercomponentofthealgorithm,andthemainalgorithmsimply
repeatsthissub-algorithminfinitenumberoftimes.
This requirement of termination of the algorithm should not be confusedwith the behavior of algorithms for problems
which themselves may generate infinite output.
Example 2
Interactive programwaiting indefinitely for a user input and then giving a response.
In such case, the main algorithm loops continuously, invoking an inner sub-algorithm,
which must prompt the user and give response within a finite time, that is, it should
terminate.
3. Finiteness Properties of Algorithm

35. Characteristics of an Algorithm Properties of Algorithm
1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:

36. The steps of an algorithmmust be defined precisely(unambiguously specified)
Every instruction in an algorithm should have ”one and only one” interpretation.
4. Definiteness
Designerwritealgorithms,butsomeotheragent(personorcomputer)willexecutethem.
So,algorithmshouldbesoclearthattheagentcanfollowitwithouttheinterventionofthe
others.
Every step must be clear, well definedand precise. There should be no ambiguity.
-clearly specifying what is meant to be done.
Properties of Algorithm

37. Every instruction in an algorithm should have ”one and only one” interpretation.
” Repeat steps 1to4a few times”
Unambiguous:
” Repeat steps 1to4until xis equal toy“
A statement, Like
-ambiguous because
:Different triesby different people
4. Definiteness Properties of Algorithm

38. The steps of an algorithmmust be defined precisely(unambiguously specified)
4. Definiteness
GCD (m , n )
Step 1 divide mby nand
let rbe the remainder. ( 0≤ r< n )
Step 2 if r= 0, terminate, nis the answer
Step 3 Set mn, nrand go backto Step 1
Euclid’s Algorithm
Although,mostofthetextinthisalgorithmisin
English,stillitsatisfiesdefiniteness.
As English language is ambiguous,
so there is a possibility that the readermight not understand exactly what the author(designer)
intended.
4. Definiteness Properties of Algorithm

39. 4. Definiteness
Inordertoachievedefiniteness,
instructionsmustbeexpressedinsomestandardlanguage,sothey
canbeunderstoodbyall.
4. Definiteness Properties of Algorithm

40. Properties of Algorithm
Peoplewritealgorithms,butsomeagent(computerorperson)willexecutethem.
So,theymustbeexpressedinsomestandardlanguage.
It is written in a language which is easy for humansto understand
4. Definiteness

41. Natural Language(human language: English, Chineseetc.)
Natural languages are ambiguous languages. There is a possibility that the implementer
might not understand exactly what the designerintended.
Computer Language(C++, Javaetc.)
IfwespecifytheinstructionsofthealgorithmsinanyComputerlanguage,these
languagespecificinstructionswillbedifficulttounderstand,evenotherlanguageuser
couldn’tunderstandit.Instructionsshouldbeprogramminglanguageindependent.
It is written in a language which is easy for humans to understand
Properties of Algorithm4. Definiteness

42. Pseudocode(English+Programminglanguagenotation)
Pseudocodeisthebestchoicetospecifyalgorithms.Asalgorithms’instructions
consistofsimplestatement,conditionalstatement,andrepeatstatement(whichare
basicforalllanguages),sotheyareunderstandableforall.
As you all know, all programing languagesshare code constructs such as
Loops(for,while,dowhileetc.)
FlowControls(ifelseetc.)
An algorithm can be written using these constructs.
Flow Chart (Graphical Way) -another way to write an algorithm
Properties of Algorithm4. Definiteness

43. 4. Definiteness
While writing instructionsin programming language, where you feel difficulty, use English like instructions
forx=1ton
” Repeat steps 1to4few times“
do
1.-------
2.-------
while(x==y)
” Repeat steps 1to4until x= y“
While writing instructionsinEnglish, where you feel ambiguity, use programming language instructions.
for(floatx=1;x<=n;x++)
” Repeat steps 1to4until x= y“
#1
#2
4. Definiteness Properties of Algorithm

44. ” Sortthe numbers”
The computer has no basic operation for Sorting.
-ambiguous because
A statement, Like
It is not easy for theagentto understand this instruction.
Inordertoavoidthistypeofambiguousness,simplebasicstatementslike
-assignments
-finiteloopand
-conditionalstatements
areusedinwritingalgorithms
WehavetodefineSort
(anotheralgorithm)using
simplebasicstatementsi.e.,
assignments,finiteloopand
conditionalstatements.
Instructionsshouldbeclearandstraightforward(basic).
4. Definiteness Properties of Algorithm

45. Characteristics of an Algorithm Properties of Algorithm
1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:

46. in the sense that
they can be doneexactlyin afinite length of time by someone usingpencil and paper.
An algorithm is also generally expected to be effective,
Effective Operations
its operations must all be sufficiently basic,
These areeffective, because
It must be possible to perform each step exactlyin a finite amount of time
GCD (m , n )
Step 1 divide mby nand
let rbe the remainder. ( 0≤ r< n )
Step 2 if r= 0, terminate, nis the answer
Step 3 Set mn, nrand go backto Step 1
integercan be represented on paper in a finite manner.
testingif an integer is zero
division
settingthe variable values
The same operations would not be effective,
if the values involved were arbitrary real numbersspecified an infinite decimal expansion.
(can not specify exactly)
5. Effectiveness Properties of Algorithm

47. Characteristics of an Algorithm Properties of Algorithm
1. Input:
2. Output:
3. Finiteness:
4. Definiteness:
5. Effectiveness:
6. Generality:

48. 6. Generality
The procedure should be applicable for all problemsof the desired form, not just for a
particular set of input values.
Properties of Algorithm

49. 1. Input: An algorithm has input values from a specified set(clearly specified Inputs)
2. Output:From each set of input values, an algorithm produces output valuesfrom aspecified set.
4. Definiteness:The stepsof an algorithm must be defined precisely(unambiguously specified)
3. Finiteness:An algorithm should produce the desired outputafter a finite number of steps
for any input in the set(terminates after a finite number of steps)
5. Effectiveness:It must be possible to perform each step of an algorithm exactly and in a finite amount of time
(steps are sufficiently simple and basic)
6. Generality:The procedure should be applicable for all problemsof the desired form, not just for a particular set of
input values.
Characteristics of an Algorithm Properties of Algorithm