Algorithms can be described as solving a problem using a series of steps. It is a set of rules or steps you follow to solve a specific problem or complete a task. In the popular TV show Friends Monica was a chef and she wanted to recreate her friends’ Phoebe grandma’s lost recipe for cookies. Monica spent hours trying to figure out the recipe for the cookies. The joke was that Phoebe’s grandma lied about it being a secret family recipe and the recipe happened to be Nestle Toll House recipe ( a recipe you can find anywhere). This simplified example describes what an algorithm is in essence. A series of steps used to solve a problem or complete a task. Monica couldn’t recreate the “famous” cookie recipe until she figured out that it was just a recipe she had in her cupboard.
Algorithms are synonymous with the field of computer science, but they existed long before computers even existed. In nature for example, all human beings are “designed” using four base pairs known as A, T, C, G. Your DNA helps to determine your looks and features and how you are designed as a person. It is the blueprint used to create you and the rest of the human population. The steps or instructions needed to create you are in your DNA.
Historical Context
Algorithms are attributed to a Persian Mathematician (modern day Uzbekistan) known as Muhammad Ibn Musa Al-Khwarizmi. He was one of the first directors of the House of Wisdom in Baghdad during the early part of the 9th Century. The House of Wisdom was an institute known for collecting scientific and mathematical works from different cultures. This included western and eastern cultures, it can be thought of as a library that houses many scientific and mathematical works. Muhammad Al-Khwarizmi oversaw the translation of major Indian and Greek mathematical and astronomical works into Arabic. He also produced his own works which spread throughout Europe after it was translated into Latin during the 12th Century.
Muhammad Al-Khwarizmi (c.780–850 CE)
The word “algorithm” is derived from the Latinization of his name, the word Algebra is derived from the Latinization of “al-jabr”. This was a book he wrote that introduced algebraic methods for solving equations (aka solving for x). He was also a strong proponent of the Hindu numerical system which he recognized as having the ability to change mathematics in the Western and Islamic world. The Hindu numbers 1–9 and 0 became known as the Hindu-Arabic numbers which the Islamic word soon adopted. In the Roman Numerical System there was no concept of the number 0. The number 0 existed in different cultures such as the Babylonian, Mayans and Indian Subcontinent. The introduction of the number 0 was controversial originally in the Western world due to religious reasons (the concept of nothing when it comes to divine creation). It was even banned in cities like Florence in 1299 due to fears that it can encourage fraud and fear of Arabic ideas due to Christian crusades against Islam. The Hindu-Arabic numerals eventually evolved to what we use in modern times known as a base-ten (ten symbols (0,1,2,3,4,5,6,7,8,9) decimal system since the place values of the numbers increase by powers of ten. The concept of 0 is important when it comes to understand how computers work using a binary system.
As mentioned previously Muhammad Al-Khwarizmi’s other major contribution was algebra which is derived from the title of a mathematical text published by him in 830 called “Al-Kitab al-mukhtasar fi hisab al-jabr wa’l-muqabala” (“The Compendious Book on Calculations by Completion and Balancing”). This book is considered a pivotal text as it laid the foundation for modern algebra. The book provided ways in which to solve polynomial equations and introduced the algebraic notion of reduction, completion and balancing. This included solving quadratic equation (equations which involve unknown numbers to the power of 2, or x^2 ). He also developed lattice multiplication method which is a method for multiplying large numbers. This method was introduced into the European world by Fibonacci an Italian Mathematician. He also contributed to the field of Astronomy which were largely based on methods from India and developed the first quadrant (an instrument used to determine time based on the observations of the stars and sun).
Algorithm Examples
Let’s dive into some real-life examples of algorithms that range from purely mathematical calculations, origins of tech giant Google and matching partners. The first one we will look at is the Euclidean Algorithm invented by Greek Mathematician Euclid in his mathematical work Elements (c. 300BC). This algorithm is designed to find the greatest common divisor (GCD) of two positive integers, a and b. The formal description of the Euclidean Algorithm is listed below.
Formal description of the Euclidean algorithm
Input Two positive integers, a and b.
Output The greatest common divisor, g, of a and b.
Internal computation
1. If a < b, exchange a and b.
2. Divide a by b and get the remainder, r. If r = 0, report b as the GCD of a and b.
3. Replace a by b and replace b by r. Return to the previous step.
Let’s break this explanation down further so it is easier to understand. Let’s say we have two numbers 210 and 45 . We will say a = 210 and b = 45 and we want to find the biggest number that can divide into both these numbers. What number is the biggest number that go evenly into both the number 210 and 45. This is what is meant by the greatest common denominator (GCD). We can take guesses like the number 2 maybe or the number 10 maybe or maybe some other number bigger than 10. Euclid’s Algorithm provides the steps necessary to find the greatest common denominator for any set of two positive numbers (numbers not negative like -10). Let’s apply Euclid’s Algorithm to solve the example of 210 and 45.
First, we will divide the bigger number (a) by (b): 210/45 = 4 but there are numbers still left over (remainder) because 45 doesn’t divide into 210 evenly (no remainder aka 0 remainders). We calculate the remainder by saying if 45 only goes into 210 4 times we will multiple 4 x 45 =180. If we now subtract 210 by 180, we get 30 which is the remainder. We take that remainder now and divide that into 45 aka 45 divided by 30. We get 1 as 30 can only be divided into 45 one time. However, it doesn’t divide into 45 evenly as there are remainders. The remainder is 15. Now we will repeat the process and divide 30 this time by 15. 30 can be divided by 15 evenly as 30 divided by 15 is 2 with no remainders (0 remainders). We stop now as we reached a point where we don’t have to divide anymore since the remainder is 0 now.
The solution for the Greatest Common Denominator for a = 210 and b = 45 is 15. 15 is the biggest number that can divide into both 210 and 45. Remember that Algorithms can be classified as a set of instructions or steps used to solve a specific problem or produce an output. If we follow Euclid’s algorithm step by step for any two positive numbers, we will always be able to find the GCD for those two numbers. This algorithm is used in programs and computer science to this day. Below is a simplified step by step look at the above problem.
1. Divide 210 by 45 with a result of 4 and a remainder of 30 (repeat process)
2. Divide 45 by 30 with a result of 1 and a remainder of 15 (repeat process)
3. Divide 30 by 15 with a result of 2 and a remainder of 0 (stop process as remainder is 0)
4. Solution: The greatest common denominator for 210 and 45 is 15.
PageRank Algorithm
Google’s PageRank algorithm was the backbone for Google’s search engine. It helped Google to become the world’s most popular search engine with trillions of searches per year. Larry Page and Sergey Brin developed PageRank as part of a research project to design a new type of search engine. Sergey Brin came up with the idea of ranking webpages based on “link popularity”. Below is a summary of how PageRank works to rank webpages.
Step by Step Description of PageRank Algorithm
1. PageRank assigns a score or rank to a webpage based on a search result. The higher ranked webpages will appear at the top of the search results. Most people usually click on the first few links in a search results so those websites will get higher clicks.
2. The scores for the webpages are partially determined by how many other websites link to them. It is based on the assumption that better websites will have more links to them than less mediocre websites.
3. Links from other websites or votes from the websites don’t have equal ranking. A higher ranked website linking to another website has a higher vote or power than a lower ranked one.
4. If a website links out to too many websites than its voting power is lowered. For example, if a website links out to thousands of other websites. Each individual link or vote won’t count as much if it only had a handful of links.
5. There are other factors that might affect the score such as the age of the website, where the keyword appears on the website and even the age of the links.
This is a very generalized overview on how the PageRank Algorithm works. It is a very complicated algorithm that also includes things like the probability of a web surfer clicking on a link. If you want to read the original paper written by the founders of Google you can follow this link.
PageRank Visual Description
Each letter represents a website and the rank of the website is the number listed below the letter. The higher the number the higher the rank. The arrows represent the websites linking out to other websites (votes). The higher ranked websites have more voting powers so their links are given more value. In this diagram B will be the highest rank website because it has the most votes or links to it.
Another interesting fact about the Google PageRank Algorithm is that the ranks of websites have to be updated daily as website rankings change all the time. Google has to continuously update the PageRank daily in order to keep the search results relevant. Initially this was a slow process at Google as it would take months to “crawl” (look through) the websites and rank them.
Gale and Shapley (Stable Marriage) Algorithm
The final algorithm we will discuss is called the Gale and Shapley Algorithm. It is a matching algorithm that can be used for different purpose such as matching students with their ideal classes, matching couples online or even matching patients with organ donors. Both Gale and Shapley were mathematicians who published a paper on this algorithm in 1962. They were not the creators of this algorithm (also known as the stable marriage algorithm) as hospitals used this algorithm twenty years prior to their publication to match residents with hospitals. They both received credit for it due to them being the first to publish it and the Noble Prize was awarded to them in 2012 in Economic Sciences for their publication. The link to their original paper can be found here.
Breakdown of the Gale-Shapley Algorithm (Stable Marriage)
Visual Representation of Gale-Shapley Algorithm
This visual example is a simplified version of the Gale-Shapley Algorithm. Each node (circle) represents either a male (m) or woman (w). The ranking is the person they would get married to from highest to lowest rank. For example, M1 chooses W1 as his first choice, W2 as his second choice, W3 as his third choice and W4 as his last choice ( determined by his rank 1234). W1 does the same thing but with the opposite sex which is M1,M2, M3, M4. The matching algorithm will match use the following set of rules.
1. The engagement or matching will be determined by either the men or the women based on their rankings. We can start matching based on the rankings with all the men first or all the women first. The final matches will be different based on which sex goes first. In this example, we will let the men determine the matches based on their rankings.
2. Each engagement or match is provisional as if two males choose one female for example, she can reject the first male she is engaged to if the second male that chooses her is her better choice. If the first male is rejected, he is sent back to his next choice as long as that choice isn’t already taken. If that woman is taken, then he would go down the list to his next choice until he is finally matched.
3. In this matching algorithm not everyone will get their top choice, but everyone will be matched with the best possible choice. Once a stable match is made between two couples, they are eliminated from being selected by other candidates.
In the diagram the men are choosing the matches based on their rankings so M1 will be engaged to his first choice of W1. Since W1 first choice is M1 they are in a stable engagement as they both chose each other as their first choice. M2 chooses W3 and they both are each other’s top choices as well, so they are in a stable engagement now. M3 is up next and his top choice of W1 will not work as she is already taken. His next choice is W2. He is provisionally engaged to her but W2 has him as her last choice. If for example another candidate chooses W2 and she had him as her higher choice she can break off her engagement with M3 and choose her better candidate. M4 is the last male and he can’t have his first choice of W3 or second choice of W2 as they are already taken. He is matched with W4 his third choice. W4 wanted M1 as her first choice but he is already taken so she will be matched with M4 which is her second choice. All the couples are engaged now even if they did not get their first choice. Given the choices they had and the fact that the men chose first they are matched with their best possible candidate.
The three algorithms we described Euclidean Algorithm, PageRank Algorithm and Gale-Shapley algorithm follow the informal definition of an algorithm. An algorithm is a series of steps used to solve a particular task or problem. As long as you follow those steps you will solve a particular task or problem even if it does not solve it in the most ideal way. The Gale-Shapley algorithm solved the matching problem based on rankings, but it didn’t match all the suitors with their ideal choice as in the real world it would be impossible to. Algorithms are everywhere from programs, mathematics and the natural world. They give an insight into how the natural world works and how our technology works to help make our lives easier. Hopefully this article gave you a better understanding of algorithms and how they work.
