# Introduction to Algorithms

Getting Started with Algorithms (in Python)

### What is an Alogirthm?

• How to systematically perform a task
• Sequence of steps (Varying degrees of detail)

Algorithms can be used to/for:

• Compute numerical functions
• Reorganize data
• Optimization

### How to optimise an algorithm? An example

##### Computing the gcd of two numbers (m,n)

The most obvious solution is to find all factors of the two numbers, see which ones are common and return the greatest one:

``````    def gcd(m,n):
fm=[]
for i in range (1, m+1):
if(m%i)==0:
fm.append(i)
fn=[]
for j in range (1, n+1):
if(n%j)==0:
fn.append(j)
cf=[]
for f in fm:
if f in fn:
cf.append(f)
return (cf[-1])

``````

Optimization 1: Both the factors can be found in the same loop

``````    fm=[]
fn=[]
for i in range (1, max(m,n)+1): #assuming m>n
if(m%i)==0:
fm.append(i)
elif (n%i==0):
fn.append(i)
``````

Optimization 2: We can reduce the loop to min (m,n) as the fcd cannot be greater than that. Also a common list can be used to save only the common divisors

``````    fm=[]
fn=[]
for i in range (1, min(m,n)+1): #assuming m>n
if(m%i)==0 and (n%i==0):
cf.append(i)
``````

Optimization 3: The list can be replaced by a single number and since we want gcd, instead of searching from lowest to highest, we should search from highest to lowest.

``````    i= min(m,n)
while (m%i!=0 and n%i!=0):
i=i-1
return i
``````

For further optimisation, you can read up on Euclids Algorithm

If you are stuck at any point or have any doubts, drop a message here

Published by in algorithms and tagged algorithms, data structures and python using 233 words.