Algorithms: An Introduction

Algorithms: An Introduction

Algorithms are something which we both consciously and subconsciously use to do our daily tasks all the time.

You want to tie your shoe lace? Follow the steps to create the complex knots.

How about going to your friends house? Take the shortest path to save time.

Want to hand out change using minimum number of coins?

You will be surprised to know how many task you do everyday that are fairly complex to code in a programming language.

 

An algorithm is defined as a set of unambigious instructions to perform any given task.

Unambigious, in the sense, you must be able to carry out each step with just the fundamental knowledge of things.

 

For ex- Algorithm to test for primality of N

1)      For each number K between 2 and SQRT(N)

2)      do

3)      If N is divisible by K then N is not prime, Terminate algorithm.

4)      end for

5)      If the control reaches here, then N is prime

6)      End of algorithm

 

Each of above steps can be understood at the fundamental level.

Whereas, consider following example-

 

Algorithm for to factorize N into its prime factors.

Step 1- Generate all prime number between 2 and SQRT(N)

step 2-Test for divisibility of N with each prime number and construct the set.

End of algorithm

 

Here, the step 1 and 2 are ambigious because it doesnt explain the method to generate primes and construct the set.

 

Hence, the fundamental property of any algorithm is

1)      It should accept some input and produce a set of outputs.

2)      The algorithm must be correct to solve the given problem.

3)      The algorithm must terminate.

4)      It should be easy to read and understand.

 

An algorithm is written in english statements. It can be implemented in any language of choice.

Before tackling any problem, it is wise to design carefully an algorithm that will perform the task.

We must set the proper constraints, the values with which the algorithm is going to work.

We must prove that the algorithm is correct. Otherwise we may spend a lot of time debugging our program for logical errors.

 

This was a basic introduction to the world of algorithms.

In the next article, we will discuss different types of algorithms.

[This article has been written by Manohar Prabhu, our Consulting Editor