Reference : Introduction to The Design & Analysis of Algorithms, Anany Levitin, Villanova University.
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.
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 musics, 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.
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
We can consider algorithms to be procedural solutions to problems. Algorithms can be specified in a natural language or a pseudocode; they can also be implemented as computer programs.
Among several ways to classify algorithms, the two principal alternatives are :
- to group algorithms according to types of problems they solve
- to group algorithms according to underlying design techniques they are based upon
The important problem types are sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, and numerical problems.An algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
Although designing an algorithm is undoubtedly a creative activity, one can identify the sequence of interrelated actions involved in such a process.
A pseudocode is a mixture of a natural language and programming language-like constructs.
A flowchart is a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
There are two kinds of algorithm efficiency :
- Time efficiency indicates how fast the algorithm runs
- Space efficiency indicates how much extra memory the algorithm needs.
A good algorithm is a result of repeated effort and rework.
The same problem can often be solved by several algorithms. For example, three algorithms were given for computing the greatest common divisor of two integers : Euclid’s algorithm, the consecutive integer checking algorithm, and the middle-school algorithm (enhanced by the sieve of Eratosthenes for generating a list of primes).
Algorithms operate on data. This makes the issue of data structuring critical for efficient algorithmic problem solving. The most important elementary data structures are the array and the linked list. They are used for representing more abstract data structures such as the list, the queue, the graph (via its adjacency matrix or adjacency linked lists), the binary tree, and the set.
An abstract collection of objects with several operations that can be performed on them is called an abstract data type (ADT). The list, the stack, the queue, the priority queue, and the dictionary are important examples of abstract data types. Modern object-oriented languages support implementation of ADTs by means of classes.