Introduction
Why do you need to study algorithms? If you are
going to be a computer professional, there are both practical and theoretical
reasons to study algo-rithms. From a practical standpoint, you have to know a
standard set of important algorithms from different areas of computing; in
addition, you should be able to design new algorithms and analyze their
efficiency. From the theoretical stand-point, the study of algorithms,
sometimes called algorithmics, has come to be recognized as the cornerstone of
computer science. David Harel, in his delightful
book pointedly titled Algorithmics: the Spirit of Computing, put it as follows:
Algorithmics is more than a branch of computer
science. It is the core of computer science, and, in all fairness, can be said
to be relevant to most of science, business, and technology. [Har92, p. 6]
But even if you are not a student in a
computing-related program, there are compelling reasons to study algorithms. To
put it bluntly, computer programs would not exist without algorithms. And with
computer applications becoming indispensable in almost all aspects of our
professional and personal lives, studying algorithms becomes a necessity for
more and more people.
Another reason for studying algorithms is their
usefulness in developing an-alytical skills. After all, algorithms can be seen
as special kinds of solutions to problems—not just answers but precisely
defined procedures for getting answers. Consequently, specific algorithm design
techniques can be interpreted as problem-solving strategies that can be useful
regardless of whether a computer is involved. Of course, the precision
inherently imposed by algorithmic thinking limits the kinds of problems that
can be solved with an algorithm. You will not find, for example, an algorithm
for living a happy life or becoming rich and famous. On the other hand, this
required precision has an important educational advantage. Donald Knuth, one of
the most prominent computer scientists in the history of algorithmics, put it
as follows:
A person well-trained in computer science knows
how to deal with algorithms: how to construct them, manipulate them, understand
them, analyze them. This knowledge is preparation for much more than writing
good computer programs; it is a general-purpose mental tool that will be a
definite aid to the understanding of other subjects, whether they be chemistry,
linguistics, or music, etc. The reason for this may be understood in the
following way: It has often been said that a person does not really understand
something until after teaching it to someone else. Actually, a person does not really understand something until after
teaching it to a computer, i.e.,
expressing it as an algorithm . . . An attempt to formalize things as
algorithms leads to a much deeper understanding than if we simply try to
comprehend things in the traditional way. [Knu96, p. 9]
We take up the notion of algorithm in Section
1.1. As examples, we use three algorithms for the same problem: computing the
greatest common divisor. There are several reasons for this choice. First, it
deals with a problem familiar to ev-erybody from their middle-school days.
Second, it makes the important point that the same problem can often be solved
by several algorithms. Quite typically, these algorithms differ in their idea,
level of sophistication, and efficiency. Third, one of these algorithms deserves
to be introduced first, both because of its age—it ap-peared in Euclid’s famous
treatise more than two thousand years ago—and its enduring power and
importance. Finally, investigation of these three algorithms leads to some
general observations about several important properties of algo-rithms in
general.
Section 1.2 deals with algorithmic problem
solving. There we discuss several important issues related to the design and
analysis of algorithms. The different aspects of algorithmic problem solving
range from analysis of the problem and the means of expressing an algorithm to
establishing its correctness and analyzing its efficiency. The section does not
contain a magic recipe for designing an algorithm for an arbitrary problem. It
is a well-established fact that such a recipe does not exist. Still, the
material of Section 1.2 should be useful for organizing your work on designing
and analyzing algorithms.
Section 1.3 is devoted to a few problem types
that have proven to be partic-ularly important to the study of algorithms and
their application. In fact, there are textbooks (e.g., [Sed11]) organized
around such problem types. I hold the view—shared by many others—that an
organization based on algorithm design techniques is superior. In any case, it
is very important to be aware of the princi-pal problem types. Not only are
they the most commonly encountered problem types in real-life applications,
they are used throughout the book to demonstrate particular algorithm design
techniques.
Section 1.4 contains a review of fundamental
data structures. It is meant to serve as a reference rather than a deliberate
discussion of this topic. If you need a more detailed exposition, there is a
wealth of good books on the subject, most of them tailored to a particular
programming language.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.