Look around you. Anywhere. Chances are, you are in an algorithm right now or are surrounded by hundreds or even thousands of them at any given point of time. In fact, probably you are playing one out even while you read this! Algorithms have existed since the inception of human reasoning or probably even before that. In fact, if you observe carefully, you will notice that algorithms are the defining set of instructions in an order of execution that defines how a task can be performed.
We believe that there is an algorithm for every task. Some may be well-defined and well-documented, while the others remain to be discovered or defined by some bright young soul. Algorithms are not just limited to mathematics or computers alone. Do you like to cook? Pick up that recipe book, it is a fine example of an entire book with nothing but algorithms. Do you need to take a bath? Apply soap-lather well-rinse-repeat. Got mail? Clear the mailbox-open the envelope-read-reply if necessary-move on to the next one. An algorithm must contain a specific set of instructions in a very well defined manner that will give the same output every single time.
And indeed, such algorithms are the building blocks of computer programming and many mathematical computations. It is only by the use of such algorithms that humankind has been able to make technology and machinery reach the current levels of fault tolerance and error-free operations. Algorithms help solve a vast range of problems. They help us to solve a Rubik’s cube as well as deliver advanced medicines to a critical patient. Algorithms help in enabling a robot to play football, or to use your biometric information like facial recognition, retinal scan or fingerprint based authentication to authorize a transaction. Well documented algorithms existed as far back as in the times of the Vedas in India, ranging on a vast number of topics like mathematics, astronomy, medicine and even black-magic! However, Euclid’s algorithm to find the Greatest Common Divisor or Highest Common Factor is widely accepted as one of the earlier forefathers of algorithms.
Another area which has been vastly affected, or rather has existed due to algorithms is cryptography and cryptanalysis. And these algorithms have made nations and kings rise and fall. They have been able to start wars and stop them as well. The Caesar’s cipher that was supposedly designed and used by Julius Caesar to send messages to his generals, Al-Kindi’s manuscript on deciphering cryptographic messages, Alan Turing’s machine to decrypt German secret messages during the Second World War, modern-day Hashing Algorithms like MD5 and SHA, and public-key cryptosystems like RSA are just a few of the vast number of cryptography related algorithms. These algorithms created the basis of modern day computers and computations and also go a long way back in establishing the roots of data security and integrity as well as the Internet and network communications in general.
Write your Own
Enough with the theory! Now let’s write some real algorithms. There are different ways to approach algorithms and write them down. There are many ways to express them as well, for e.g. you could write an algorithm in plain language or write it as pseudo code ( i.e. logical representation in code-like blocks) or even as a specific piece of code in some programming language. Another popular way of expressing algorithms is via a set of simple shapes and diagrams known as flow charts.
The first step of writing algorithms is understanding your problem statement and jotting down the approach to solve it. Once you have the solution try to prove that all negative cases and positive cases are sufficed. So, if you want to write an algorithm that proves that you are the King of Mars, then your algorithm must always prove that you are the king of Mars and for any other person it must say that he/she is not the King of Mars. In fact, let’s try and draw a flow chart for the same, as shown in the image here.
Now, here is an algorithm showing how to approach writing algorithms in a systematic way. It is expressed in natural language to demonstrate writing algorithms in that fashion, as follows:
Algorithm to write an algorithm
- Find out what data you will have as input i.e. possible data inputs which you will process upon. In our King of Mars case, it was the name of anyone as text.2. Store these different variables with easy to read names. For example, in our
- Store these different variables with easy to read names. For example, in our case, we could have stored our input name’s text in a variable as “claimant_to_the_throne_of_mars”
- Define the steps of operations, i.e. decide what and how your data is to be operated upon. Take the decisions based upon the possible outcomes. In our case, the name variable “claimant_to_the_throne_of_mars” had to be checked for equality against “Your Name”. The possible outcomes were Yes, it matches or No it doesn’t match. Accordingly, we were to decide whether to declare the claimant to the throne of Mars as the legitimate King of Mars or not.
- Show the results as Output. Your algorithm is of no use if it doesn’t ultimately arrive at a conclusion and lets the end user know the outcome. So, it MUST pronounce to the world that the claimant is the king of Mars or not!
Signs and secrets!
Now that we have become the King of Mars let’s do a bit of time travel and rule Rome as well! We need to send out a secret message in cryptographic form to Anthony who is just about to invade Egypt. The message is “DO NOT KILL THE QUEEN”. For simplicity (and because our Roman is a bit unpolished) we are going to use the English alphabet to encrypt and send this message. Don’t worry, Anthony has been taking English lessons as well and so he will be able to decipher it with the knowledge of the exact number of shifts (3 in this case). The process that we are going to use is known Caesar’s Cipher and involves a simple shifting of letters by a fixed number of positions either to the left or right. To visualize this, we will shift the letters of the alphabet by 3 spaces as shown above.
Now referring to the above chart, we can encrypt our message as:
D – G,
O – R and so on…
Our Message thus becomes: GR QRW NLOO WKH TXHHQ. Now summon the messenger and send him to Anthony as fast as possible with this encrypted message. Godspeed!
Now let’s try to write down the algorithm for the cipher that we
shift = input shift ; /* 3 in our case */
input_sentence= input the sentence to be converted; /* DO NOT KILL THE QUEEN */
for each(character in input_sentence)
if (character is in alphabet)
if(character is in [A-W|a-w] )
character = character + 3;
else /* character is in [X-Z|x-z] */
character = character – 23;
Pseudocode for encrypting using Caesar’s Cipher
And voila! You have now already learnt 3 ways to write algorithms (Natural Language, Flow Charts, and Pseudocode). These are some of the most commonly used methods, but there are quite a few other ways of representing an algorithm as well, like drakon-charts or control tables.
Time complexity and the dreaded Big O!
NO. We are not going to explain the mathematical model. We’ll give a brief and hopefully understandable explanation. A function or an operations Big-O notation is determined by how much slower is it if it the size of inputs is varied.
For example, if you are the messenger sent by Caesar to deliver our cipher message to Anthony and you do not know him by face or his ranks, then instead of looking at one particular tent at the army camp, you may have to visit and search every tent in the camp. Therefore the time required for you to find Mark Anthony, when represented via a mathematical function is commonly denoted by the Big-O notation. Different algorithms try to reduce this time so that even for large inputs (like the size of the Roman army!) the required time of the operation is optimal. If you look for Anthony by visiting one tent after the other, the best case is that you find him in the 1st one and the worst case is that you don’t find him at all (mathematically known as the lower and upper bounds respectively).
While programming in most languages, in general you will observe that the time complexity of a function/method increases n times every time you have nested iterations. So if you have one ‘for’ loop iterating over a size of n inputs then the time complexity is of the order ‘n’ while adding another outer loop with the same no of inputs will raise it to the order of ‘n’ * ‘n’. So in short if the first loop was taking 5 seconds to complete,then adding an outer loop will increase it to somewhere around 25 second roughly. A simpler explanation of the same can be found here.
And finally, a funny Sort Algorithm that takes a lot of time!
The last algorithm that we are going to see today is called BOGOSORT. Note, this algorithm is meant as a programming example and is used mostly as a joke. So, do not implement this in real life programs unless you want your programs to become really, really slow as the Bogosort algorithm has a general time complexity of O(n!.n).
Bogo sort is a highly ineffective algorithm that takes an input array and sorts the array by generating random permutations until the array is sorted. After every iteration, the algorithm reshuffles the entire array and generates a new and completely random sequence and checks if the array is sorted. If not, it repeats itself. The pseudo code for Bogosort (also known as slow-sort, permutation sort, stupid sort, monkey sort etc) is as follows:
while not InOrder(list)
We have removed the implementation details for the shuffle part of this algorithm for simplicity.
Now, go and have fun with algorithms. Find some new ones or play with the old ones. An interesting exercise that you can undertake is to look at existing algorithms and try to figure out their time complexity using the Big-O notation. And once you master that, maybe go looking for a better way to encrypt Caesar’s messages or, if you’re ambitious, better Google’s search algorithm so that it can find a time machine for you!
This article was first published in the June 2017 issue of Digit magazine. To read Digit’s articles first, subscribe here or download the Digit app for Android and iOS. You could also buy Digit’s previous issues here.