Kodeclik Blog
What are Algorithms?
What is an algorithm?
An algorithm is simply an unambiguous sequence of instructions to accomplish a given task. Merriam-Webster defines an algorithm as “a step-by-step procedure for solving a problem or accomplishing some end.” Although the word algorithm is frequently associated with computer science and mathematics, all humans use algorithms in real life.
What are everyday examples of algorithms?
The most common example of an algorithm is a recipe such as what you might find on the back of a cereal box. The recipe "algorithm" clearly lists the ingredients involved, the amount of each ingredient needed, and a sequence of steps to be followed to make the final product. The algorithm must be written such that it can be followed by a non-expert who mechanically and mindlessly follows the instructions faithfully and achieves the same final product. Algorithms are often the “secret sauce” for many things in life - which is why there are so many recipe books, “how to” books, and other cookbooks.
A second example of an algorithm can be seen when you goto a bank location. Suppose you enter during a busy time (say 4pm on a Friday before the bank closes for the weekend) and you see 20 people waiting in line to be serviced by 4 tellers. How do the tellers decide which person to service next? Most banks follow the FCFS (First Come First Served) algorithm so that people enter through a queue and the people are serviced in the order in which they enter. A different policy would be where the tellers are divided into functional areas, e.g., one teller is in charge of cash withdrawals, another teller is in charge of wire transfers, and yet another teller is in charge of opening new accounts, and customers are assigned to the tellers based on their banking needs. This is a different algorithm. Which algorithm is used in a given bank depends on that bank’s manager.
A third example of an algorithm is if you use a service like Google Maps to find directions from say, the White House (1600 Pennsylvania Avenue) to the US Capitol building (First Street Southeast) both in Washington DC. Google Maps gives you a sequence of steps to follow such as below. In this case, the algorithm is a “path finding” algorithm between two locations on a map.
The Google Maps path finding algorithm is very elaborate and rich in the options it provides. For instance, the results of the algorithm will likely change depending on whether you are driving or walking, the time of day and the day of the week you are routing, (e.g., whether it is a holiday) and in general can change if streets are closed or restricted to be one-ways.
As you can see, algorithms are everywhere! If you consciously think about what you did today from the moment you woke up, you will likely find more examples of algorithms.
What is not an algorithm?
Remember the word “unambiguous” in our definition above. Something is not an algorithm if it does not give clear, followable, instructions. For instance, if your cooking instructions say something like: “take some all-purpose flour, add some corn flour, then a little bit of vanilla extract, a few chocolate chips, and bake for some time to make your loaf of bread” - this would not be an algorithm. How much is “some”? What does “little bit” mean? How do I know how long to bake it? People following these instructions will end up with different results and thus this would not be considered an algorithm. In contrast, look at the back of your cereal box and notice how carefully the quantities, times, and measurements are noted.
Can there be more than one algorithm for a given task?
Of course! Algorithms are a creative pursuit so there will be multiple algorithms for a given task. Sometimes it will be clear when one algorithm is superior to another. Suppose I give you two numbers and ask you if their sum is even.
Here is Algorithm 1 for this task:
1. X = First number; Y = Second number
2. Z = X+Y
3. If Z is even, say “True”, else say “False”Here is Algorithm 2 for this task:
1. X = First number; Y = Second number
2. If (X is even & Y is odd) OR (X is odd & Y is even)
say “False”
else
say “True”Note that these two algorithms work in different ways. Also note that both algorithms are correct and will yield the same answers for the same inputs. One algorithm is adding the numbers and then inspecting the result to see if it is even. This algorithm is thus following the “letter of the law”. The second algorithm is not doing any addition at all. It uses mathematics to reason that adding numbers of the same parity (odd and odd; or even and even) will give even numbers whereas adding numbers of different parity (odd and even; or even and odd) will yield odd numbers. Therefore this algorithm is “smarter” in the types of calculations it does and could be faster if the numbers given are very large numbers.
Sometimes there could be different algorithms for a given problem because there are so many different criteria to optimize. When you are baking a cake, do you want the cake to be tastier or the baking to be done faster? Ideally we would like both but in reality trying to optimize one objective will negatively impact the other objective. Similarly, routing using Google Maps gives multiple results depending on whether the distance traveled is shorter or whether the time taken is smaller. The former will likely take local, more direct, roads (but take longer because traffic is higher) and the latter will take highways (but might be longer even though it gets you there sooner).
Why is it important to understand algorithms?
Algorithms are the essence of many fields. A good understanding of algorithms will serve you well not just in computer science but in many domains because algorithms are everywhere! Algorithmic thinking also encourages you to be precise in your problem specification and understanding and improves your logical reasoning skills. It is easy to “hand wave” and convince oneself that you understand a concept. But by consciously thinking about how to specify an algorithm, you are ironing out all the imperfections in your understanding and determining how best to communicate a clear set of instructions. Good algorithmic thinking will also make you a better programmer. It will force you to think carefully about how best to structure your code, where you should pay the most attention to, and the most efficient way to achieve your objectives.
How do you describe an algorithm?
An algorithm can be described in any unambiguous textual or graphical notation. A cooking recipe can be described in just English. But computers are not adept at understanding natural language (yet). So to communicate with computers, you need to come up with more formal ways to describe algorithms. In the early days, an algorithm was described in terms of flow charts. A flow chart has different elements, e.g, boxes (which describe computational steps), and diamonds (which describe decision points that might yield different outcomes in different situations). The below is a flowchart algorithm for finding the greatest number from three given numbers.
Software such as Lucidchart, Microsoft Powerpoint give you all the elements for making flowcharts. However, the flowchart notation gets cumbersome when we try to think of larger algorithms.
What is the world’s oldest algorithm?
The ancient Babylonians (300 BC) were considered to have developed algorithms for multiplication, codified in the form of clay tablets. Ancient Egyptians, Persians, and Greeks are also well known for contributions to algorithms. For instance, of the oldest algorithms known to mankind is Euclid’s algorithm (300 BC) for finding the greatest common divisor of two numbers (still taught in schools - so it has withstood the test of time). Another very old algorithm taught in elementary school is the Sieve of Eratosthenes (around 200 BC) which is a “mark and find” algorithm for finding prime numbers (it is however, very inefficient). In the modern computer era, Ada Lovelace is considered to have written the first computer program. Her programs were meant to be run on Charles Babbage’s analytical engine, which was never built, but this work formed the foundation of computer programming for decades.
What are some of the world’s famous algorithms?
Today there are thousands of algorithms for very specific tasks and problems. Just like there are books of cooking recipes, there are books of “numerical recipes” which contain instructions for many algorithms.
When somebody comes up with an algorithm, the algorithm is considered to be “discovered” rather than “invented” and named in honor of the person who discovered it. For instance, there is Dijkstra’s shortest path algorithm named after Edsger W. Dijkstra who came up with it in 1959. There is the RSA algorithm, named after Ron Rivest, Adi Shamir, and Leonard Adleman, which is the first asymmetric public key cryptography algorithm (discovered in 1977). Google's ranking algorithm for webpages is called PageRank. (Some people say it is named after Larry Page, one of Google's founders while others say that the Page in PageRank refers to webpages.)
There are often problems that defy a practical algorithm and when such an algorithm is indeed discovered it creates a splash in computer science. One such example is the AKS algorithm, named after Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, who developed the first practical algorithm for determining if a number is prime (in 2002) - a problem unsolved for centuries. This news made the cover of the New York Times! Most recently, in 2020, Professor Po-Shen Loh of Carnegie Mellon University rediscovered an algorithm to solve quadratic equations used by the Babylonians.
What are the different types of algorithms?
There are many types of algorithms reflecting either the style of problem solving or the type of problem they are geared to address. Here are some common types (and these are by no means exhaustive):
Divide-and-Conquer Algorithms: A Divide-and-Conquer Algorithm breaks down the given problem into two subproblems and solves each of them in parallel and then "joins" the solutions. For instance, if you are trying to find a route from Washington DC to San Francisco and you know that the path must go through Chicago, then you can break down this routing problem into two smaller routing problems, namely first find a path from Washington DC to Chicago and then find a path from Chicago to San Francisco. As you can guess this works only if Chicago is indeed the right intermediate waypoint for this route. So you should use Divide-and-Conquer algorithms only if you are sure you are breaking down the problem correctly.
Dynamic Programming Algorithms: A Dynamic Programming algorithm can be viewed as trying out lots of ways to breakdown a problem into subproblems, carefully book-keeping the subproblems and their solutions, and then conjoining the solutions to find the best overall solution. For instance, in the above routing problem you might try different choices of intermediate cities and find the optimal solution. “Programming” in the name of “Dynamic Programming” predates computing - here, programming means book-keeping in the form of a table.
Search Algorithms: A Search Algorithm systematically enumerates and explores possibilities, retracing decisions if necessary, in order to find the overall solution. Some search algorithms are looking for an optimal solution while others are looking for just (any) solution. Recall that the algorithm Deep Blue beat chess grandmaster Gary Kasparov in 1997; Deep Blue is a very clever search algorithm that looks multiple steps ahead.
Sorting Algorithms: A sorting algorithm is one that takes an array of numbers and sorts them in order. You might be surprised to learn that there are literally hundreds of sorting algorithms and some are more efficient than others. Some common sorting algorithms are “insertion sort”, “bubble sort”, and “quick sort”.
Graph Algorithms: A graph algorithm is an algorithm that works with graphs, i.e., data that can be represented as graphs like maps or organizational structures or the web (web pages linking to each other).
Randomized Algorithms: A randomized algorithm is one that makes random choices in its functioning. Now you might wonder - that might make it unpredictable but in fact some of the most efficient algorithms known today for many problems are actually randomized algorithms.
