Most algorithms are destined to be ultimately implemented as computer pro-grams. Programming an algorithm presents both a peril and an opportunity.

**Coding an Algorithm**

Most algorithms are destined to be ultimately
implemented as computer pro-grams. Programming an algorithm presents both a
peril and an opportunity. The peril lies in the possibility of making the
transition from an algorithm to a pro-gram either incorrectly or very inefficiently.
Some influential computer scientists strongly believe that unless the
correctness of a computer program is proven with full mathematical rigor, the
program cannot be considered correct. They have developed special techniques
for doing such proofs (see [Gri81]), but the power of these techniques of
formal verification is limited so far to very small programs.

As a practical matter, the validity of programs
is still established by testing. Testing of computer programs is an art rather
than a science, but that does not mean that there is nothing in it to learn.
Look up books devoted to testing and debugging; even more important, test and
debug your program thoroughly whenever you implement an algorithm.

Also note that throughout the book, we assume that
inputs to algorithms belong to the specified sets and hence require no
verification. When implementing algorithms as programs to be used in actual
applications, you should provide such verifications.

Of course, implementing an algorithm correctly
is necessary but not sufficient: you would not like to diminish your
algorithm’s power by an inefficient implemen-tation. Modern compilers do
provide a certain safety net in this regard, especially when they are used in
their code optimization mode. Still, you need to be aware of such standard
tricks as computing a loop’s invariant (an expression that does not change its
value) outside the loop, collecting common subexpressions, replac-ing expensive
operations by cheap ones, and so on. (See [Ker99] and [Ben00] for a good
discussion of code tuning and other issues related to algorithm program-ming.)
Typically, such improvements can speed up a program only by a constant factor,
whereas a better algorithm can make a difference in running time by orders of
magnitude. But once an algorithm is selected, a 10–50% speedup may be worth an
effort.

A working program provides an additional
opportunity in allowing an em-pirical analysis of the underlying algorithm.
Such an analysis is based on timing the program on several inputs and then
analyzing the results obtained. We dis-cuss the advantages and disadvantages of
this approach to analyzing algorithms in Section 2.6.

In conclusion, let us emphasize again the main
lesson of the process depicted in Figure 1.2:

As a rule, a good algorithm is a result of
repeated effort and rework.

Even if you have been fortunate enough to get
an algorithmic idea that seems perfect, you should still try to see whether it
can be improved.

Actually, this is good news since it makes the
ultimate result so much more enjoyable. (Yes, I did think of naming this book *The Joy of Algorithms*.) On the other
hand, how does one know when to stop? In the real world, more often than not a
project’s schedule or the impatience of your boss will stop you. And so it
should be: perfection is expensive and in fact not always called for. Designing
an algorithm is an engineering-like activity that calls for compromises among
competing goals under the constraints of available resources, with the
designer’s time being one of the resources.

In the academic world, the question leads to an
interesting but usually difficult investigation of an algorithm’s ** optimality**.
Actually, this question is not about the efficiency of an algorithm but about
the complexity of the problem it solves: What is the minimum amount of effort

Another important issue of algorithmic problem
solving is the question of whether or not every problem can be solved by an
algorithm. We are not talking here about problems that do not have a solution,
such as finding real roots of a quadratic equation with a negative
discriminant. For such cases, an output indicating that the problem does not
have a solution is all we can and should expect from an algorithm. Nor are we
talking about ambiguously stated problems. Even some unambiguous problems that
must have a simple yes or no answer are “undecidable,” i.e., unsolvable by any
algorithm. An important example of such a problem appears in Section 11.3.
Fortunately, a vast majority of problems in practical computing *can* be solved by an algorithm.

Before leaving this section, let us be sure
that you do not have the misconception—possibly caused by the somewhat
mechanical nature of the diagram of Figure 1.2—that designing an algorithm is a
dull activity. There is nothing further from the truth: inventing (or
discovering?) algorithms is a very creative and rewarding process. This book is
designed to convince you that this is the case.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Coding an Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.