A Quick Introduction to Algorithms
What happens when you search for something on any search engine like Google Chrome, Mozilla Firefox? What happens when you ask a virtual assistant like Alexa, Google Assistant, Siri? Like, how does it know the answer? How does it display accurate results? All thanks to Algorithms.
Every time you use your phone, computer, laptop, or a calculator you are using Algorithms.
But, what is an Algorithm ?
If you want to do any math operation lets say multiplication of two numbers(without using any electronic device), you multiply it using a paper. You follow some instructions to get the correct value. You also do it in a process that takes less time to calculate. This is called an Algorithm.
An Algorithm is a set of instructions designed to perform a specific task.
Algorithms can be simple and complex depending on what you want to achieve.
History of Algorithm
Knowing the history of something you learn, will always be an added advantage, as you can understand the topic better than anyone and know exactly where to use what and many more.
The term “Algorithm” is derived from a 9th century Persian mathematician named Muhammad Ibn Musa Al-Khwarizmi(Father of Algebra), Latinized as Algoritmi. At first algorithm was called as Algorismus. Later in 15th century Algorisums was altered to Algorithmus(derived from Greek word Arithmetic). The modern sense English term “Algorithm” was introduced in the 19th century.
Before 1842, algorithms were written on papers and were used to perform mathematical calculations. The first algorithm developed was by Egyptians for multiplying 2 numbers in 1700–2000 BC.
For the first time in 1842, an algorithm for computing engine was written, by Ada Lovelace, which is why she is often cited as the first computer programmer. She wrote an algorithm for Analytical Engine(a mechanical computer that automated computations), developed by our Father of Computer, Charles Babbage to compute Bernoulli numbers.
The first modern notion algorithm in electronic(non-mechanical) computers were seen in Alan Turing’s Turing Machine in 1936.
How are the algorithms expressed?
Algorithms can be expressed in many ways like natural languages, pseudocode, flow charts, programming languages, drakon-charts, control tables.
Natural language expression of algorithms is ambiguous so they are rarely used for complex or technical algorithms. Pseudocode, flow charts, drakon-charts, and control tables are structured ways to express algorithms so they avoid many of the ambiguities compared to natural language. Programming languages are intended for expressing algorithms in a form that can be executed by a computer.
In computer systems, an algorithm is a logic written by software developers in any programming language of their choice. But, there are a few set of rules that we need to remember while designing an algorithm. They are,
Input: There should be one or more values to be applied in the algorithm. If there is no input given what output will the algorithm produce?
Output: At least one output should be produced. There is no use of designing an algorithm if it does not produce any result.
Efficiency: It should be efficient in terms of compute and memory. The output produced should be correct & fast.
Simplicity: The algorithm should not be overly complex.
Scalability: The algorithm must be able to scale without changing the core logic.
Finiteness: The algorithm must terminate after a finite number of steps. Assume you have given wrong input, if the algorithm terminates at the first step, we would never know what’s wrong with our algorithm. Also, it should not end up in infinite loops.
Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.
Lets now build a simple algorithm which adds two numbers fulfilling the above pre-requisites.
Step-1: Start
Step-2: Declare variables num1, num2, and sum
Step-3: Read values num1 and num2
Step-4: Add num1 and num2 and assign the value to sum.
Step-5: Display sum
Step-6: Stop
Now, to test the algorithm, we are going to implement it in one of the programming language,
I choose to implement it in Java language, you can implement it any programming language of your choice.
public class Addition
{
public static void main(String[] args) {
int num1, num2, sum;
Scanner sc = new Scanner(System.in);
System.out.println(“Enter First Number: “);
num1 = sc.nextInt();
System.out.println(“Enter Second Number: “);
num2 = sc.nextInt();
sc.close();
sum = num1 + num2;
System.out.println(“Sum of two numbers: “+sum);
}
}
The output is as below,
Enter First Number:
121
Enter Second Number:
19
Sum of two numbers: 140Our algorithm is working perfectly, fulfilling the above mentioned prerequisites.
An algorithm developed must be efficient. An algorithm’s efficiency is defined by time and space. A good algorithm is the one that takes less time and less space, both are not possible all the time. If you want to reduce the time, then space might increase and vice versa. So, we have to compromise with either of them. The space complexity of an algorithm denotes the total space used or needed by the algorithm for its working. Time complexity is the number of operations an algorithm performs to complete its task. The algorithm that performs the task in the smallest number of operations is considered as the most efficient algorithm. The time taken by an algorithm also depends on the computing speed of your machine, but this external factor is not often considered while calculating the efficiency of an algorithm. One way to measure the efficiency of an algorithm is to count how many operations it needs to find the answer across different input sizes.
Recursive Algorithm solves the problem by repeatedly breaking down the problem into sub-problems.
Divide & Conquer Algorithm solves the problem by breaking down the problem into smaller sub-problems, solves them recursively, and combines them to form a solution.
Dynamic Programming Algorithm(also known as Dynamic Optimization Algorithm) remembers the past results for future use. Similar to Divide & Conquer Algorithm, it breaks down complex problems into simple sub-problems, then solve each of these sub-problems only once by storing solution for future use without having to recompute their solutions again.
Greedy Algorithm solves the problem by taking the optimal solution at the local level. This algorithm does not guarantee an optimal solution at the end.
Brute Force Algorithm is simple & straight-forward, it simply tries all the possibilities until a satisfactory solution is found.
Backtracking Algorithm solves the problem recursively in an incremental approach. It tries to get the solution by solving one piece at a time. If one of the solution fail, it backtracks and starts finding the solution.
Algorithms are now being used in almost every field like data science, machine learning, agriculture, science, transport, etc. Algorithms are the reason which differs every application from each other like Google Chrome from Mozilla Firefox, Uber from Ola, etc. For example, Google Chrome and Mozilla Firefox are both search engine applications and provide the same results but the order of results varies, this is because of different sorting algorithms being used. Google has its sorting algorithm which is different from that of Firefox’s.
We know algorithms are making our lives easier as algorithms are everywhere and will continue to spread, but there are also things that we need to worry about like,
Humanity & human judgment are lost when data & predictive modeling becomes paramount.
Unemployment will rise, as smarter and more efficient algorithms displace many human activities.
In this 21st century, algorithms are like magic, as we can explain their principles and how the network was created, etc but why the particular output has resulted is beyond a mechanical explanation. This is just the beginning.
“If every algorithm suddenly stopped working, it would be the end of the world as we know it.” (The Master of Algorithm by Pedro Domingos)
I hope you understood, in case of any queries feel free to ask in the comment section. Open for feedback & suggestions.
THANK YOU!!
