We have already mentioned that not every problem has an algorithmic solution. The problem, which has at least one algorithmic solution, is called algorithmic or computable problem. Also, we should note that there is no systematic method (i.e., algorithm) for designing algorithms even for algorithmic problems.
In fact, designing an algorithm for a general algorithmic/computable problem is a difficult intellectual exercise. It requires creativity and insight and no general rules can be formulated in this respect. As a consequence, a discipline called algorithmics has emerged that comprises large literature about tools, techniques and discussion of various issues like efficiency etc. related to the design of algorithms. In the rest of the course, we shall be explaining and practicing algorithms. Actually, algorithmics could have been an alternative name of the course. We enumerate below some well-known techniques which have been found useful in designing algorithms:
i) Divide and conquer
ii) Dynamic Programming
iii) The Greedy Approach
iv) Backtracking
v) Branch and Bound
vi) Searches and Traversals.
Most of these techniques will be discussed in detail in the text.
In view of the difficulty of solving algorithmically even the computationally solvable problems, some of the problem types, enumerated below, have been more rigorously studied:
(i) Sorting problems
(ii) Searching problems
(iii) Linear programming problems
(iv) Number-theory problems
(v) String processing problems
(vi) Graph problems
(vii) Geometric problems
(viii) Numerical problems.
Study of these specific types of problems may provide useful help and guidance in
solving new problems, possibly of other problem types.
Next, we enumerate and briefly discuss the sequence of steps, which generally,
one goes through for designing algorithms for solving (algorithmic) problems,
and analyzing these algorithms.
1.7.1 Understanding the Problem
Understanding allows appropriate action. This step forms the basis of the other steps
to the discussed. For understanding the problem, we should read the statement of the
problem, if required, a number of times. We should try to find out
(i) the type of problem, so that if a method of solving problems of the type, is
already known, then the known method may be applied to solve the problem
under consideration.
(ii) the type of inputs and the type of expected/desired outputs, specially, the
illegal inputs, i.e., inputs which are not acceptable, are characterized at this
stage. For example, in a problem of calculating income-tax, the income can not
be non-numeric character strings.
(iii) the range of inputs, for those inputs which are from ordered sets. For example,
in the problem of finding whether a large number is prime or not, we can not
give as input a number greater than the Maximum number (Max, mentioned
above) that the computer system used for the purpose, can store and
arithmetically operate upon. For still larger numbers, some other representation
mechanism has to be adopted.
(iv) special cases of the problem, which may need different treatment for solving
the problem. For example, if for an expected quadratic equation ax2+bx+c=0, a,
the coefficient of x2, happens to be zero then usual method of solving quadratic
equations, discussed earlier in this unit, can not be used for the purpose.
1.7.2 Analyzing the problem
This step is useful in determining the characteristics of the problem under
consideration, which may help in solving the problem. Some of the characteristics in
this regards are discussed below:
(i) Whether the problem is decomposable into independent smaller or easier
subproblems, so that programming facilities like procedure and recursion etc.
may be used for designing a solution of the problem. For example, the
problem of evaluating
..
can be do decomposed into smaller and simpler problems viz.,
..
(ii) Whether steps in a proposed solution or solution strategy of the problem,
may or may not be ignorable, recoverable or inherently irrecoverable,
i.e., irrecoverable by the (very) nature of the problem. Depending upon the nature of the problem, the solution strategy has to be decided or modified. For example,
a) While proving a theorem, if an unrequired lemma is proved, we may ignore it. The only loss is the loss of efforts in proving the lemma. Such a problem is called ignorable-step problem.
b) Suppose we are interested in solving 8-puzzle problem of reaching from some initial state say
..
by sliding, any one of the digits from a cell adjacent to the blank cell, to the blank cell. Then a wrong step cannot be ignored but has to be recovered. By recoverable, we mean that we are allowed to move back to the earlier state from which we came to the current state, if current state seems to be less desirable than the earlier state. The 8-puzzle problem has recoverable steps, or, we may say the problem is a recoverable problem
c) However if, we are playing chess, then a wrong step may not be even recoverable. In other words, we may not be in a position, because of the adversary’s move, to move back to earlier state. Such a problem is called an irrecoverable step problem.
Depending on the nature of the problem as ignorable-step, recoverable-step or irrecoverable-step problem, we have to choose our tools, techniques and strategies for solving the problem.
For example, for ignorable-step problems, simple control structures for sequencing and iteration may be sufficient. However, if the problem additionally has recoverable-step possibilities then facilities like back-tracking, as are available in the programming language PROLOG, may have to be used. Further, if the problem additionally has irrecoverable-step possibilities then planning tools should be available in the computer system, so that entire sequence of steps may be analyzed in advance to find out where the sequence may lead to, before the first step is actually taken.
There are many other characteristics of a problem viz.,
* Whether the problem has certain outcome or uncertain outcome
* Whether a good solution is absolute or relative
* Whether the solution is a state or a path
* Whether the problem essentially requires interaction with the user etc.
which can be known through analyzing the problem under consideration, and the knowledge of which, in turn, may help us in determining or guessing a correct sequence of actions for solving the problem under consideration
1.7.3 Capabilities of the Computer System
We have already discussed the importance of the step in Section 1.5, where we noticed how, because of change in computational capabilities, a totally differentalgorithm has to be designed to solve the same problem (e.g., that of multiplying two natural numbers).
Most of the computer systems used for educational purposes are PCs based on Von-Neumann architecture. Algorithms, that are designed to be executed on such machines are called sequential algorithms.
However, new more powerful machines based on parallel/distributed architectures, are also increasingly becoming available. Algorithms, that exploit such additional facilities, are called parallel/ distributed; such parallel/distributed algorithms, may not have much resemblance to the corresponding sequential algorithms for the same problem.
However, we restrict ourselves to sequential algorithms only.
1.7.4 Approximate vs Exact Solution
For some problems like finding the square root of a given natural number n, it may not be possible to find exact value for all n’s (e.g., n = 3). We have to determine in advance what approximation is acceptable, e.g., in this case, the acceptable error may be, say, less than .01.
Also, there are problems, for which finding the exact solutions may be possible, but the cost (or complexity, to be defined later) may be too much.
In the case of such problems, unless it is absolutely essential, it is better to use an alternative algorithm which gives reasonably approximate solution, which otherwise may not be exact. For example, consider the Travelling Salesperson Problem: A salesperson has a list of, say n cities, each of which he must visit exactly once. There are direct roads between each pair of the given cities. Find the shortest possible route that takes the salesperson on the round trip starting and finishing in any one of the n cities and visiting other cities exactly once.
In order to find the shortest paths, one should find the cost of covering each of the n! different paths covering the n given cities. Even for a problem of visiting 10 cities, n!, the number of possible distinct paths is more than 3 million. In a country like India, a travelling salesperson may be expected to visit even more than 10 cities. To find out exact solution in such cases, though possible, is very time consuming. In such case, a reasonably good approximate solution may be more desirable.
1.7.5 Choice of Appropriate Data Structures
In complex problems particularly, the efficiencies of solutions depend upon choice of appropriate data structures. The importance of the fact has been emphasized long back in 1976 by one of the pioneer computer scientists, Nickolus Wirth, in his book entitled “Algorithms + Data Structures= Programs”.
In a later paradigm of problem-solving viz., object-oriented programming, choice of appropriate data structure continues to be crucially important for design of efficient programs
1.7.6 Choice of Appropriate Design Technology
A design technique is a general approach for solving problem that is applicable to computationally solvable problems from various domains of human experience.
We have already enumerated various design techniques and also various problem domains which have been rigorously pursued for computational solutions. For each problem domain, a particular set of techniques have been found more useful, thoughother techniques also may be gainfully employed. A major part of the material of the course, deals with the study of various techniques and their suitability for various types of problem domains. Such a study can be a useful guide for solving new problems or new problems types.
1.7.7 Specification Methods for Algorithms
In the introduction of the unit , we mentioned that an algorithm is a description or statement of a sequence of activities that constitute a process of getting desired output from the given inputs. Such description or statement needs to be specified in some notation or language. We briefly mentioned about some possible notations for the purpose. Three well-known notations/languages used mostly for the purpose, are enumerated below:
(i) Natural language (NL): An NL is highly expressive in the sense that it can express algorithms of all types of computable problems. However, main problem with an NL is the inherent ambiguity, i.e., a statement or description in NL may have many meanings, all except one, may be unintended and misleading.
(ii) A Pseudo code notation is a sort of dialect obtained by mixing some programming language constructs with natural language descriptions of algorithms. The pseudo-code method of notation is the frequently used one for expressing algorithms. However, there is no uniform/standard pseudo-code notation used for the purpose, though, most pseudo-code notations are quite similar to each other.
(iii) Flowchart is a method of expressing algorithms by a collection of geometric shapes with imbedded descriptions of algorithmic steps. However, the technique is found to be too cumbersome, specially, to express complex algorithms.
1.7.8 Proving Correctness of an Algorithm
Subsection 1.7.2 was concerned with analyzing the problem in order to find out special features of the problem, which may be useful in designing an algorithm that solves the problem. Here, we assume that one or more algorithms are already designed to solve a problem. The purpose of analysis of algorithm is to determine the requirement of computer resources for each algorithm. And then, if there are more than one algorithms that solve a problem, the analysis is also concerned with choosing the better one on the basis of comparison of requirement of resources for different available algorithms. The lesser the requirement of resources, better the algorithm. Generally, the resources that are taken into consideration for analysing algorithms, include
(i) Time expected to be taken in executing the instances of the problem generally as a function of the size of the instance.
(ii) Memory space expected to be required by the computer system, in executing the instances of the problem, generally as a function of the size of the instances.
(iii) Also sometimes, the man-hour or man-month taken by the team developing the program, is also taken as a resource for the purpose.
The concerned issues will be discussed from place to place throughout the course material.
1.7.10 Coding the Algorithm
In a course on Design & Analysis of Algorithm, this step is generally neglected, assuming that once an algorithm is found satisfactory, writing the corresponding program should be a trivial matter. However, choice of appropriate language and choice of appropriate constructs are also very important. As discussed earlier, if the problem is of recoverable type then, a language like PROLOG which has backtracking mechanism built into the language itself, may be more appropriate than any other language. Also, if the problem is of irrecoverable type, then a language having some sort of PLANNER built into it, may be more appropriate
Next, even an efficient algorithm that solves a problem, may be coded into an inefficient program. Even a correct algorithm may be encoded into an incorrect program.
In view of the facts mentioned earlier that the state of art for proving an algorithm/program correct is still far from satisfactory, we have to rely on testing the proposed solutions. However, testing of a proposed solution can be effectively carried out by executing the program on a computer system (an algorithm, which is not a program can not be executed). Also by executing different algorithms if more than one algorithm is available, on reasonably sized instances of the problem under consideration, we may empirically compare their relative efficiencies. Algorithms, which are not programs, can be hand-executed only for toy-sized instances.
In fact, designing an algorithm for a general algorithmic/computable problem is a difficult intellectual exercise. It requires creativity and insight and no general rules can be formulated in this respect. As a consequence, a discipline called algorithmics has emerged that comprises large literature about tools, techniques and discussion of various issues like efficiency etc. related to the design of algorithms. In the rest of the course, we shall be explaining and practicing algorithms. Actually, algorithmics could have been an alternative name of the course. We enumerate below some well-known techniques which have been found useful in designing algorithms:
i) Divide and conquer
ii) Dynamic Programming
iii) The Greedy Approach
iv) Backtracking
v) Branch and Bound
vi) Searches and Traversals.
Most of these techniques will be discussed in detail in the text.
In view of the difficulty of solving algorithmically even the computationally solvable problems, some of the problem types, enumerated below, have been more rigorously studied:
(i) Sorting problems
(ii) Searching problems
(iii) Linear programming problems
(iv) Number-theory problems
(v) String processing problems
(vi) Graph problems
(vii) Geometric problems
(viii) Numerical problems.
Study of these specific types of problems may provide useful help and guidance in
solving new problems, possibly of other problem types.
Next, we enumerate and briefly discuss the sequence of steps, which generally,
one goes through for designing algorithms for solving (algorithmic) problems,
and analyzing these algorithms.
1.7.1 Understanding the Problem
Understanding allows appropriate action. This step forms the basis of the other steps
to the discussed. For understanding the problem, we should read the statement of the
problem, if required, a number of times. We should try to find out
(i) the type of problem, so that if a method of solving problems of the type, is
already known, then the known method may be applied to solve the problem
under consideration.
(ii) the type of inputs and the type of expected/desired outputs, specially, the
illegal inputs, i.e., inputs which are not acceptable, are characterized at this
stage. For example, in a problem of calculating income-tax, the income can not
be non-numeric character strings.
(iii) the range of inputs, for those inputs which are from ordered sets. For example,
in the problem of finding whether a large number is prime or not, we can not
give as input a number greater than the Maximum number (Max, mentioned
above) that the computer system used for the purpose, can store and
arithmetically operate upon. For still larger numbers, some other representation
mechanism has to be adopted.
(iv) special cases of the problem, which may need different treatment for solving
the problem. For example, if for an expected quadratic equation ax2+bx+c=0, a,
the coefficient of x2, happens to be zero then usual method of solving quadratic
equations, discussed earlier in this unit, can not be used for the purpose.
1.7.2 Analyzing the problem
This step is useful in determining the characteristics of the problem under
consideration, which may help in solving the problem. Some of the characteristics in
this regards are discussed below:
(i) Whether the problem is decomposable into independent smaller or easier
subproblems, so that programming facilities like procedure and recursion etc.
may be used for designing a solution of the problem. For example, the
problem of evaluating
..can be do decomposed into smaller and simpler problems viz.,
..(ii) Whether steps in a proposed solution or solution strategy of the problem,
may or may not be ignorable, recoverable or inherently irrecoverable,
i.e., irrecoverable by the (very) nature of the problem. Depending upon the nature of the problem, the solution strategy has to be decided or modified. For example,
a) While proving a theorem, if an unrequired lemma is proved, we may ignore it. The only loss is the loss of efforts in proving the lemma. Such a problem is called ignorable-step problem.
b) Suppose we are interested in solving 8-puzzle problem of reaching from some initial state say
..by sliding, any one of the digits from a cell adjacent to the blank cell, to the blank cell. Then a wrong step cannot be ignored but has to be recovered. By recoverable, we mean that we are allowed to move back to the earlier state from which we came to the current state, if current state seems to be less desirable than the earlier state. The 8-puzzle problem has recoverable steps, or, we may say the problem is a recoverable problem
c) However if, we are playing chess, then a wrong step may not be even recoverable. In other words, we may not be in a position, because of the adversary’s move, to move back to earlier state. Such a problem is called an irrecoverable step problem.
Depending on the nature of the problem as ignorable-step, recoverable-step or irrecoverable-step problem, we have to choose our tools, techniques and strategies for solving the problem.
For example, for ignorable-step problems, simple control structures for sequencing and iteration may be sufficient. However, if the problem additionally has recoverable-step possibilities then facilities like back-tracking, as are available in the programming language PROLOG, may have to be used. Further, if the problem additionally has irrecoverable-step possibilities then planning tools should be available in the computer system, so that entire sequence of steps may be analyzed in advance to find out where the sequence may lead to, before the first step is actually taken.
There are many other characteristics of a problem viz.,
* Whether the problem has certain outcome or uncertain outcome
* Whether a good solution is absolute or relative
* Whether the solution is a state or a path
* Whether the problem essentially requires interaction with the user etc.
which can be known through analyzing the problem under consideration, and the knowledge of which, in turn, may help us in determining or guessing a correct sequence of actions for solving the problem under consideration
1.7.3 Capabilities of the Computer System
We have already discussed the importance of the step in Section 1.5, where we noticed how, because of change in computational capabilities, a totally differentalgorithm has to be designed to solve the same problem (e.g., that of multiplying two natural numbers).
Most of the computer systems used for educational purposes are PCs based on Von-Neumann architecture. Algorithms, that are designed to be executed on such machines are called sequential algorithms.
However, new more powerful machines based on parallel/distributed architectures, are also increasingly becoming available. Algorithms, that exploit such additional facilities, are called parallel/ distributed; such parallel/distributed algorithms, may not have much resemblance to the corresponding sequential algorithms for the same problem.
However, we restrict ourselves to sequential algorithms only.
1.7.4 Approximate vs Exact Solution
For some problems like finding the square root of a given natural number n, it may not be possible to find exact value for all n’s (e.g., n = 3). We have to determine in advance what approximation is acceptable, e.g., in this case, the acceptable error may be, say, less than .01.
Also, there are problems, for which finding the exact solutions may be possible, but the cost (or complexity, to be defined later) may be too much.
In the case of such problems, unless it is absolutely essential, it is better to use an alternative algorithm which gives reasonably approximate solution, which otherwise may not be exact. For example, consider the Travelling Salesperson Problem: A salesperson has a list of, say n cities, each of which he must visit exactly once. There are direct roads between each pair of the given cities. Find the shortest possible route that takes the salesperson on the round trip starting and finishing in any one of the n cities and visiting other cities exactly once.
In order to find the shortest paths, one should find the cost of covering each of the n! different paths covering the n given cities. Even for a problem of visiting 10 cities, n!, the number of possible distinct paths is more than 3 million. In a country like India, a travelling salesperson may be expected to visit even more than 10 cities. To find out exact solution in such cases, though possible, is very time consuming. In such case, a reasonably good approximate solution may be more desirable.
1.7.5 Choice of Appropriate Data Structures
In complex problems particularly, the efficiencies of solutions depend upon choice of appropriate data structures. The importance of the fact has been emphasized long back in 1976 by one of the pioneer computer scientists, Nickolus Wirth, in his book entitled “Algorithms + Data Structures= Programs”.
In a later paradigm of problem-solving viz., object-oriented programming, choice of appropriate data structure continues to be crucially important for design of efficient programs
1.7.6 Choice of Appropriate Design Technology
A design technique is a general approach for solving problem that is applicable to computationally solvable problems from various domains of human experience.
We have already enumerated various design techniques and also various problem domains which have been rigorously pursued for computational solutions. For each problem domain, a particular set of techniques have been found more useful, thoughother techniques also may be gainfully employed. A major part of the material of the course, deals with the study of various techniques and their suitability for various types of problem domains. Such a study can be a useful guide for solving new problems or new problems types.
1.7.7 Specification Methods for Algorithms
In the introduction of the unit , we mentioned that an algorithm is a description or statement of a sequence of activities that constitute a process of getting desired output from the given inputs. Such description or statement needs to be specified in some notation or language. We briefly mentioned about some possible notations for the purpose. Three well-known notations/languages used mostly for the purpose, are enumerated below:
(i) Natural language (NL): An NL is highly expressive in the sense that it can express algorithms of all types of computable problems. However, main problem with an NL is the inherent ambiguity, i.e., a statement or description in NL may have many meanings, all except one, may be unintended and misleading.
(ii) A Pseudo code notation is a sort of dialect obtained by mixing some programming language constructs with natural language descriptions of algorithms. The pseudo-code method of notation is the frequently used one for expressing algorithms. However, there is no uniform/standard pseudo-code notation used for the purpose, though, most pseudo-code notations are quite similar to each other.
(iii) Flowchart is a method of expressing algorithms by a collection of geometric shapes with imbedded descriptions of algorithmic steps. However, the technique is found to be too cumbersome, specially, to express complex algorithms.
1.7.8 Proving Correctness of an Algorithm
Subsection 1.7.2 was concerned with analyzing the problem in order to find out special features of the problem, which may be useful in designing an algorithm that solves the problem. Here, we assume that one or more algorithms are already designed to solve a problem. The purpose of analysis of algorithm is to determine the requirement of computer resources for each algorithm. And then, if there are more than one algorithms that solve a problem, the analysis is also concerned with choosing the better one on the basis of comparison of requirement of resources for different available algorithms. The lesser the requirement of resources, better the algorithm. Generally, the resources that are taken into consideration for analysing algorithms, include
(i) Time expected to be taken in executing the instances of the problem generally as a function of the size of the instance.
(ii) Memory space expected to be required by the computer system, in executing the instances of the problem, generally as a function of the size of the instances.
(iii) Also sometimes, the man-hour or man-month taken by the team developing the program, is also taken as a resource for the purpose.
The concerned issues will be discussed from place to place throughout the course material.
1.7.10 Coding the Algorithm
In a course on Design & Analysis of Algorithm, this step is generally neglected, assuming that once an algorithm is found satisfactory, writing the corresponding program should be a trivial matter. However, choice of appropriate language and choice of appropriate constructs are also very important. As discussed earlier, if the problem is of recoverable type then, a language like PROLOG which has backtracking mechanism built into the language itself, may be more appropriate than any other language. Also, if the problem is of irrecoverable type, then a language having some sort of PLANNER built into it, may be more appropriate
Next, even an efficient algorithm that solves a problem, may be coded into an inefficient program. Even a correct algorithm may be encoded into an incorrect program.
In view of the facts mentioned earlier that the state of art for proving an algorithm/program correct is still far from satisfactory, we have to rely on testing the proposed solutions. However, testing of a proposed solution can be effectively carried out by executing the program on a computer system (an algorithm, which is not a program can not be executed). Also by executing different algorithms if more than one algorithm is available, on reasonably sized instances of the problem under consideration, we may empirically compare their relative efficiencies. Algorithms, which are not programs, can be hand-executed only for toy-sized instances.
No comments:
Post a Comment