What is Algorithms ?
Understanding Algorithm
The sequence of steps to be performed in order to solve a
problem by the computer is known as an algorithm.
ALGORITHMS
Look around you. Computers and networks are everywhere,
enabling an intricate web of complex human activities: education,
commerce, entertainment, research, manufacturing, health
management, communication, even war. Of the two main
technological underpinnings of this amazing proliferation, one is the
breathtaking pace with which advances in microelectronics and chip
design have been bringing us faster and faster hardware. The other is
efficient algorithms that are fueling the computer revolution.
In mathematics, computer science, and related subjects, an
algorithm is a finite sequence of steps expressed for solving a problem.
An algorithm can be defined as “a process that performs some
sequence of operations in order to solve a given problem”. Algorithms
are used for calculation, data processing, and many other fields.
In computing, algorithms are essential because they serve as the
systematic procedures that computers require. A good algorithm is like
using the right tool in the workshop. It does the job with the right
amount of effort. Using the wrong algorithm or one that is not clearly
defined is like trying to cut a piece of plywood with a pair of scissors:
although the job may get done, you have to wonder how effective you
were in completing it.
Let us follow an example to help us understand the concept of
algorithm in a better way. Let’s say that you have a friend arriving at
the railway station, and your friend needs to get from the railway
station to your house. Here are three different ways (algorithms) that
you might give your friend for getting to your home.
Examples of Algorithm
- The taxi/auto-rickshaw algorithm:
- Go to the taxi/auto-rickshaw stand.
- Get in a taxi/auto-rickshaw.
- Give the driver my address.
- The call-me algorithm:
- When your train arrives, call my mobile phone
- Meet me outside the railway station
- Outside the railway station, catch bus number 321.
- Transfer to bus 308 near Kurla station.
- Get off near Kalina University.
- Walk two blocks west to my house.
All these three algorithms accomplish the same goal, but each
algorithm does it in a different way. Each algorithm also has a different
cost and a different travel time. Taking a taxi/auto-rickshaw, for
example, is the fastest way, but also the most expensive. Taking the
bus is definitely less expensive, but a whole lot slower. You choose the
algorithm based on the circumstances.
In computer programming, there are often many different
algorithms to accomplish any given task. Each algorithm has
advantages and disadvantages in different situations. Sorting is one
place where a lot of research has been done, because computers spend
a lot of time sorting lists.
Three reasons for using algorithms are efficiency, abstraction and
reusability.
- Efficiency: Certain types of problems, like sorting, occur oftenin computing. Efficient algorithms must be used to solve suchproblems considering the time and cost factor involved in eachalgorithm.
- Abstraction: Algorithms provide a level of abstraction insolving problems because many seemingly complicatedproblems can be distilled into simpler ones for which wellknownalgorithms exist. Once we see a more complicatedproblem in a simpler light, we can think of the simpler problemas just an abstraction of the more complicated one. Forexample, imagine trying to find the shortest way to route apacket between two gateways in an internet. Once we realizethat this problem is just a variation of the more general shortestpath problem, we can solve it using the generalised approach.
- Reusability: Algorithms are often reusable in many differentsituations. Since many well-known algorithms are thegeneralizations of more complicated ones, and since manycomplicated problems can be distilled into simpler ones, anefficient means of solving certain simpler problems potentiallylets us solve many complicated problems.
Expressing Algorithms:
Algorithms can be expressed in many different notations,
including natural languages, pseudocode, flowcharts and
programming languages. Natural language expressions of algorithms
tend to be verbose and ambiguous, and are rarely used for complex or
technical algorithms. Pseudocode and flowcharts are structured ways
to express algorithms that avoid many ambiguities common in natural
language statements, while remaining independent of a particular
implementation language.
Programming languages are primarilyintended for expressing algorithms in a form that can be executed by a
computer, but are often used to define or document algorithms.
Sometimes it is helpful in the description of an algorithm to
supplement small flowcharts with natural language and/or arithmetic
expressions written inside block diagrams to summarize what the
flowcharts are accomplishing.
Consider an example for finding the largest number in an
unsorted list of numbers.
The solution for this problem requires looking at every number in the
list, but only once at each.
1) Algorithm using natural language statements:
a) Assume the first item is largest.
b) Look at each of the remaining items in the list and if it is larger
than the largest item so far, make a note of it.
c) The last noted item is the largest item in the list when the
process is complete.
2) Algorithm using pseudocode:
largest = L0
for each item in the list (Length(L) 1), do
if the item largest, then
largest = the item
return largest
Benefits of using Algorithms:
The use of algorithms provides a number of benefits. One of
these benefits is in the development of the procedure itself, which
involves identification of the processes, major decision points, and
variables necessary to solve the problem. Developing an algorithm
allows and even forces examination of the solution process in a
rational manner. Identification of the processes and decision points
reduces the task into a series of smaller steps of more manageable size.
Problems that would be difficult or impossible to solve in entirety can
be approached as a series of small, solvable sub-problems.
By using an algorithm, decision making becomes a more
rational process. In addition to making the process more rational, use
of algorithm will make the process more efficient and more consistent.
Efficiency is an inherent result of the analysis and specification
process. Consistency comes from both the use of the same specified
process and increased skill in applying the process. An algorithm
serves as a mnemonic device and helps ensure that variables or parts of
the problem are not ignored. Presenting the solution process as an
algorithm allows more precise communication. Finally, separation of
the procedure steps facilitates division of labour and development of
expertise.
A final benefit of the use of an algorithm comes from the
improvement it makes possible. If the problem solver does not know
what was done, he or she will not know what was done wrong. As time
goes by and results are compared with goals, the existence of a
specified solution process allows identification of weaknesses and
errors in the process. Reduction of a task to a specified set of steps or
algorithm is an important part of analysis, control and evaluation.
General Approaches in Algorithm Design:
In a broad sense, many algorithms approach problems in the
same way. Thus, it is often convenient to classify them based on the
approach they employ. One reason to classify algorithms is to gain an
insight about an algorithm and understand its general approach. This
can also give us ideas about how to look at similar problems for which
we do not know algorithms. Of course, some algorithms defy
classification, whereas others are based on a combination of
approaches. This section presents some common approaches.
Randomized algorithms rely on the statistical properties of
random numbers. One example of a randomized algorithm is quicksort.
Imagine an unsorted pile of cancelled checks by hand. In order
to sort this pile we place the checks numbered less than or equal to
what we may think is the median value in one pile, and in the other pile
we place the checks numbered greater than this. Once we have the two
piles, we divide each of them in the same manner and repeat the
process until we end up with one check in every pile. At this point the
checks are sorted.
Divide-and-conquer Algorithms:
Divide-and-conquer algorithms revolve around 3 steps: divide,
conquer and combine. In the divide step, we divide the data into
smaller, more manageable pieces. In the conquer step, we process each
division by performing some operations on it. In the combine step, we
recombine the processed divisions. An example of the divide-andconquer
algorithm is merge sort.
As before, imagine an unsorted pile of cancelled checks by
hand. We begin by dividing the pile in half. Next, we divide each of
the resulting two piles in half and continue this process until we end up
with one check in every pile. Once all piles contain a single check, we
merge the piles two by two so that each pile is a sorted combination of
the two that were merged. Merging continues until we end up with one
big pile again, at which point the checks are sorted.
Dynamic-programming solutions:
Dynamic-programming solutions are similar to divide-andconquer
methods in that both solve problems by breaking larger
problems into sub-problems whose results are later recombined.
However, the approaches differ in how sub-problems are related. In
divide-and-conquer algorithms, each sub-problem is independent of the
others. Therefore we solve each sub-problem using recursion and
combine its results with the results of other sub-problems. In dynamicprogramming
solutions, sub-problems are not independent of one
another. A dynamic-programming solution is better than a divide-andconquer
approach because the latter approach will do more work than
necessary, as shared sub-problems are solved more than once.
However, if the sub-problems are independent and there is no
repetition, using divide-and-conquer algorithms is much better than
using dynamic-programming.
An example of dynamic-programming is finding the shortest
path to reach a point from a vertex in a weighted graph.
Greedy algorithms make decisions that look best at the
moment. In other words, they make decisions that are locally optimal
in the hope that they will lead to globally optimal solutions. The
greedy method extends the solution with the best possible decision at
an algorithmic stage based on the current local optimum and the best
decision made in a previous stage. It is not exhaustive, and does not
give accurate answer to many problems. But when it works, it will be
the fastest method.
One example of a greedy algorithm is Huffman coding, which
is an algorithm for data compression.
- Approximation Algorithms:
Approximation algorithms are algorithms that do not compute
optimal solutions; instead, they compute solutions that are “good
enough”. Often we use approximation algorithms to solve problems
that are computationally expensive but are too significant to give up
altogether. The travelling salesman problem is one example of a
problem usually solved using an approximation algorithm.
Analysis of Algorithms:
Whether we are designing an algorithm or applying one that is
widely accepted, it is important to understand how the algorithm will
perform. There are a number of ways we can look at an algorithm’s
performance, but usually the aspect of most interest is how fast the
algorithm will run. In some cases, if an algorithm uses significant
storage, we may be interested in its space requirement as well.
Analysis of algorithms is the theoretical study of computer
program performance and resource usage, and is often practised
abstractly without the use of specific programming language or
implementation. The practical goal of algorithm analysis is to predict
the performance of different algorithms in order to guide program
design decisions. There are many reasons to understand the
performance of an algorithm. For example, we often have a choice of
several algorithms when solving problems (like sorting).
Understanding how each performs helps us differentiate between them.
Understanding the burden an algorithm places on an application also
helps us plan how to use the algorithm more effectively. For instance,
garbage collection algorithms, algorithms that collect dynamically
allocated storage to return to the heap, require considerable time to run.
Knowing this we can be careful to run them only at opportune
moments, just as Java does, for example.
Algorithm analysis is important in practice because the
accidental or unintentional use of an inefficient algorithm can
significantly impact system performance. In time-sensitive
applications, an algorithm taking too long to run can render its results
outdated or useless. An inefficient algorithm can also end up requiring
an uneconomical amount of computing power or storage in order to
run, again rendering it practically useless.
Most algorithms do not perform the same in all cases; normally
an algorithm’s performance varies with the data passed to it. Typically,
three cases are recognized: the best case, average case and worst case.
For any algorithm, understanding what constitutes each of these cases
is an important part of analysis because performance can vary
significantly between them.
Consider a simple algorithm such as linear search. Linear
search is a natural but inefficient search technique in which we look for
an element simply by traversing a set from one end to the other. In the
best case, the element we are looking for is the first element we
inspect, so we end up traversing only a single element. In the worst
case, however, the desired element is the last element that we inspect,
in which we end up traversing all the elements. On average, we can
expect to find the element somewhere in the middle.
A basic understanding of how an algorithm performs in all
cases is important, but usually we are most interested in how an
algorithm performs in the worst case. There are four reasons why
algorithms are generally analyzed by their worst case:
- Many algorithms perform to their worst case a large part of thetime. For example, the worst case in searching occurs when wedo not find what we are looking for at all. This frequentlyhappens in database applications.
- The best case is not very informative because many algorithmsperform exactly the same in the best case. For example, nearlyall searching algorithms can locate an element in one inspectionat best, so analyzing this case does not tell us much.
- Determining average-case performance is not always easy.Often it is difficult to determine exactly what the “averagecase” even is; since we can seldom guarantee precisely how analgorithm will be exercised.
- The worst case gives us an upper bound on performance.Analyzing an algorithm’s worst case guarantees that it wil never perform worse than what we determine. Therefore, weknow that the other cases must perform at least better than theworst case
Worst case analysis of algorithms is considered to be crucial to
applications such as games, finance and robotics. Although worst case
analysis is the metric for many algorithms, it is worth noting that there
are exceptions. Sometimes special circumstances let us base
performance on the average case (for example quick-sort algorithm).
O-notation, also known as Big O-notation, is the most common
notation used to express an algorithm’s performance in a formal
manner. Formally, O-notation expresses the upper bound is a function
within a constant factor. Specifically, if g(n) is an upper bound of f(n),
then for some constant c it is possible to find the value of n, call it n0,
for which any value of n n0 will result in f(n) cg(n).
Normally we express an algorithm’s performance as a function
of the size of the data it processes. That is, for some data of size n, we
describe its performance with some function f(n). Primarily we are
interested only in the growth rate of f, which describes how quickly the
algorithm’s performance will degrade as the size of data it processes
becomes arbitrarily large. An algorithm’s growth rate, or order of
growth, is significant because ultimately it describes how efficient the
algorithm is for aritrary inputs. O-notation reflects an algorithm’s order
of growth.
Simple Rules for O-notation:
O-notation lets us focus on the big picture. When faced with a
complicated function like 3n2 + 4n + 5, we just replace it with O(f(n)),
where f(n) is as simple as possible. In this particular example we'd use
O(n2), because the quadratic portion of the sum dominates the rest of
the function. Here are some rules that help simplify functions by
omitting dominated terms:
We can ignore constant terms because as the value of n
becomes larger and larger, eventually constant terms will
become insignificant. For example, if T(n) = n+50 describes the
running time of an algorithm, and n, the size of data it
processes, is only 1024, the constant term in this expression
constitutes less than 5% of the running time.
We can ignore multiplicative constants because they too will
become insignificant as the value of n increases. For example,
We need to consider the highest-order term because as n
increases higher-order terms quickly outweigh the lower-order
terms. That is, na dominates nb if a > b. For instance, n2
We also must note that an exponential term dominates any
polynomial term in the expression. For example, 3n dominates
n5 (it even dominates 2n).
Similarly, a polynomial term dominates any logarithmic term
used in the expression. For example, n dominates (log n)3. This
also means, for example, that n2 dominates n log n.
O-Notation Example:
This section discusses how these rules help us in predicting an
algorithm’s performance. Let’s look at a specific example
demonstrating why they work so well in describing a function’s growth
rate. Suppose we have an algorithm whose running time is described
by the function T(n) = 3n2 + 10n + 10.
Using the rules of O-notation, this function can be simplified to:
O(T(n)) = O(3n2 + 10n + 10) = O(3n2) = O(n2)
This indicates that the term n2 will be the one that accounts for
the most of the running time as n grows arbitrarily large. We can verify
this quantitatively by computing the percentage of the overall running
time that each term accounts for as n increases. For example, when n =
10, we have the following:
Running time for 3n2: 3(10)2 / (3(10)2 + 10(10) + 10) = 73.2%
Running time for 10n: 10(10) / (3(10)2 + 10(10) + 10) = 24.4%
Running time for 10: 10 / (3(10)2 + 10(10) + 10) = 2.4%
Already we see that the n2 term accounts for the majority of the
overall running time. Now consider when n = 100:
Running time for 3n2: 3(100)2 / (3(100)2 + 10(100) + 10) = 96.7%
Running time for 10n: 10(100) / (3(100)2 + 10(100) + 10) = 3.2%
Running time for 10: 10 / (3(100)2 + 10(100) + 10) = 0.1%
Here we see that this term accounts for almost all of the
running time, while the significance of the other terms diminishes
further. Imagine how much of the running time this term would
account for if n was 106!
