What is an algorithm | novice-vikas

FIG 1.1

Although there is no universally agreed-on wording to describe this notion, there
is general agreement about what the concept means:
           "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."
This definition can be illustrated by a simple diagram (Figure 1.1).
The reference to “instructions” in the definition implies that there is something
or someone capable of understanding and following the instructions given.
We call this a “computer,” keeping in mind that before the electronic computer
was invented, the word “computer” meant a human being involved in performing
numeric calculations. Nowadays, of course, “computers” are those ubiquitous
electronic devices that have become indispensable in almost everything we do.
Note, however, that although the majority of algorithms are indeed intended for
eventual computer implementation, the notion of algorithm does not depend on
such an assumption.
As examples illustrating the notion of the algorithm, we consider in this
section three methods for solving the same problem: computing the greatest
common divisor of two integers. These examples will help us to illustrate several
important points:
The non ambiguity requirement for each step of an algorithm cannot be compromised.

• The range of inputs for which an algorithm works has to be specified carefully.
• The same algorithm can be represented in several different ways.
• There may exist several algorithms for solving the same problem.
• Algorithms for the same problem can be based on very different ideas and can solve the problem with dramatically different speeds.

What is an algorithm?

Algorithm is a set of steps to complete a task.

For example,

Task: to make a cup of tea.

Algorithm:

· add water and milk to the kettle,
· boilit, add tea leaves,
· Add sugar, and then serve it in cup.

What is Computer algorithm?

‘’a set of steps to accomplish or complete a task that is described precisely enough that a computer can run it’’.

Described precisely: very difficult for a machine to know how much water, milk to be added etc. in the above tea making algorithm.

These algorithms run on computers or computational devices.

For example, GPS in our smartphones, Google hangouts.

GPS uses shortest path algorithm. Online shopping uses cryptography which uses RSA algorithm.

Characteristics of an algorithm:-

• Must take an input.
• Must give some output(yes/no,value etc.)
• Definiteness –each instruction is clear and unambiguous.
• Finiteness –algorithm terminates after a finite number of steps.
• Effectiveness –every instruction must be basic i.e. simple instruction.

Expectation from an algorithm :

1. Correctness : 

• Correct: Algorithms must produce correct result.
• Produce an incorrect answer: Even if it fails to give correct results all the time still there is a control on how often it gives wrong result. Eg.Rabin-Miller Primality Test (Used in RSA algorithm): It doesn’t give correct answer all the time.1 out of 250 times it gives incorrect result.
• Approximation algorithm: Exact solution is not found, but near optimal solution can be found out. (Applied to optimization problem.)
• Less resource usage :  Algorithms should use less resources (Time and Space).

Resource usage:

Here, the time is considered to be the primary measure of efficiency .We are also

concerned with how much the respective algorithm involves the computer memory.But mostly time is the resource that is dealt with. And the actual running time depends on a variety of backgrounds: like the speed of the Computer, the language in which the algorithm is implemented, the compiler/interpreter, skill of the programmers etc.

So, mainly the resource usage can be divided into: 

                     1.Memory (space) 

                     2.Time

Time taken by an Algorithm  :

> Performance measurement : Implementing the algorithm

in a machine and then calculating the time taken by the system to execute the program successfully.

>Performance Evaluation or Apriori Analysis. Before implementing the algorithm in a system. 

     This is done as follows -

1. How long the algorithm takes :-will be represented as a function of the size of

the input.

f(n)→how long it takes if ‘n’ is the size of input.

2. How fast the function that characterizes the running time grows with the input

size.

“Rate of growth of running time”.

The algorithm with less rate of growth of running time is considered better.