| Design
& Analysis Of Algorithms |
An
algorithm is just the outline or idea behind a program. We express algorithms
in pseudo-code: something resembling C or Pascal, but with some statements in
English rather than within the programming language. It is expected that one could
translate each pseudo-code statement to a small number of lines of actual code,
easily and mechanically.
This class covers the design of algorithms for various
types of problems, as well as a mathematical analysis of those algorithms done
independently of any actual computational experiments. The purpose of design of
algorithms is obvious: one needs an algorithm in order to write a program. Analysis
of algorithms is less obviously necessary, but has several purposes:
a) Analysis
can be more reliable than experimentation. If we experiment, we only know the
behavior of a program on certain specific test cases, while analysis can give
us guarantees about the performance on all inputs.
b) It helps one choose
among different solutions to problems. As we will see, there can be many different
solutions to the same problem. A careful analysis and comparison can help us decide
which one would be the best for our purpose, without requiring that all be implemented
and tested.
c) We can predict the performance of a program before we take
the time to write code. In a large project, if we waited until after all the code
was written to discover that something runs very slowly, it could be a major disaster,
but if we do the analysis first we have time to discover speed problems and work
around them.
d) By analyzing an algorithm, we gain a better understanding
of where the fast and slow parts are, and what to work on or work around in order
to speed it up.
<<back |
