Programming Basics: Algorithms
What’s this thing we call “Algorithm”?
We do tasks in life without giving much thought about it. We subconsciously understand the tasks we do. For a person who hasn’t had any contact with computers, and no contact with computer programming or mathematics in particular, it is the most important thing to note: The tasks we do in our lives are not thought on, but are done subconsciously, we do not think about each action we need to do to complete a task, but we generally “just do it”. Computers can’t “just do” things. We need to tell the computer, instruction by instruction, without any ambiguity, what needs to be done in order to perform a task. This is what we call an “Algorithm”. The term algorithm is usually overlooked in introductions to programming basics but I believe it is the single most important term that needs to be grasped. Individuals who have not spent their lives solving problems that require algorithmic thinking (those problems generally belonging to branches of mathematics, including computer science) have a hard time understanding why programming is the way it is. They have a hard time understanding why we need variables, if statements, boolean expressions, for loops, functions etc. You might be thinking the same. Don’t worry, we will thoroughly explore what the term “Algorithm” is all about, why we need it, some examples of algorithms and how they correlate to our everyday lives, and how we can translate these to computers.
Algorithms in our everyday lives
When you go to a coffee shop and you want to order a caramel latte, you don’t think much about the whole action, do you? It is simple and natural. You’ve done it a thousand times and there is no conscious thinking involved in the action. But, if you stop and think about it, if you break it down into smaller subtasks that need to be done for you to get your coffee from the moment you are in front of the cafe to the moment you sit down at one of the tables, you will be surprised to find out how complex this action can become. Let’s do it. So first of all, you need to decide on the drink, it might be caramel latte today, but you might want an americano another day, it varies depending on your mood or other factors, it’s variable. After you’ve decided your drink, you tell the cashier, and they will ask you about the cup size. You have three options: Tall, Grande and Venti. After you’ve made your choice (which by the way, is also variable, as you may not always choose the same size) the cashier will ask you which type of payment you would like to use: cash or card. After you’ve made your choice, and the payment has gone through, you finally get your coffee. Now as we can see, you need to make a series of actions, which may include decisions, in order to perform this action. If we sum up the action, before you want to order your coffee, you need to: decide which coffee you want, what size you want it in and what type of payment method you are going to pay with. These three variables are also known as inputs. At the end, you get your desired coffee, this is the output. Now if we try to algorithmically represent our action, we may do so by writing each step we identified (this time even more detailed as this is what an “algorithm” is all about):
Starting Position: A coffee shop
- Come up to the cashier
- Choose your drink and tell the cashier
- Cashier asks which cup size you would like
- Choose your cup size and tell cashier
- Cashier asks for payment method
- Choose your payment method and tell cashier
- Cashier asks for the payment itself
- Give cashier the payment (either with cash or card)
- Payment Accepted
- Cashier tells the barista to prepare your coffee
- You get your coffee
Now once broken down into steps, we can know which actions we need to do to actually complete the whole action.
A simple algorithm (the max element function)
Now, because real-life scenarios such as buying a coffee from a coffee shop have too many parameters, are abstract and are not uniform across all coffee shops/countries etc. it is easier to understand algorithms through simpler examples, and more concrete ones. For example, let’s analyze the maxElement function we use to find a maximum element in a list. Suppose you see the list below:
[4, 6, 2, 1, 441, 31, 12, 42, 155, 27, 99, 13, 9, 6, 1500, 12, 1]
If I asked you what the maximum element in the given list is, you can immediately tell it is 1500.
I want to ask you though, how did you do that? How did you find the maximum element?
Many people would just say “well I just saw it, and it’s the maximum”. The “just do it” phenomenon. As I said, such a phenomenon cannot occur in computer programming. We need to know what we are doing and exactly how we are doing it. Suppose instead of the list above, I gave you the following list and asked you what the maximum element is:
[91, 682, 308, 233, 79, 76, 850, 707, 857, 16, 368, 562, 858, 852, 618, 152, 881, 535, 170, 359, 990, 693, 3, 698, 274, 265, 792, 253, 687, 893, 156, 470, 405, 261, 219, 659, 890, 140, 599, 129, 11, 294, 136, 964, 926, 382, 765, 288, 273, 979, 203, 530, 632, 525, 930, 517, 716, 589, 440, 994, 480, 95, 320, 507, 844, 876, 961, 106, 797, 326, 623, 194, 137, 938, 357, 528, 942, 812, 422, 131, 112, 652, 445, 93, 936, 660, 193, 143, 370, 238, 105, 395, 275, 748, 109, 955, 73, 453, 478, 767, 434, 832, 303, 814, 768, 299, 281, 680, 267, 199, 449, 271, 581, 489, 854, 70, 758, 663, 622, 863, 763, 595, 154, 508, 717, 841, 608, 406, 256, 640, 671, 183, 394, 615, 918, 337, 380, 537, 684, 676, 285, 466, 549, 903, 760, 561, 352, 800, 444, 825, 114, 710, 322, 353, 338, 712, 498, 695, 54, 196, 145, 176, 226, 44, 108, 67, 862, 662, 849, 610, 500, 884, 908, 62, 524, 982, 726, 872, 743, 86, 389, 916, 567, 946, 490, 487, 408, 619, 927, 513, 473, 476, 692, 871, 471, 612, 799, 678, 32, 975]
Not so easy anymore, eh?
The absence of knowledge of how we found the maximum in the short list actually means we cannot find the maximum in the big list. An algorithm is basically a way to describe, step by step, instruction by instruction, without any ambiguity, what needs to be done in order to find the element. And anyone who reads the algorithm, and does the described steps one by one, can solve the problem. An algorithm is basically a precise description of how a solution can be found to a problem. Now, generally (and justifiably) algorithms are expressed as pseudocode. Pseudocode is basically a piece of code that does not adhere to rules of any programming language, but is only used for the purpose of easily writing down the algorithm without worrying about any rules of the programming language. It is more of a logical representation of an algorithm. There are other representations too, but pseudocode is largely adapted. But, we will not try to express the maxElement algorithm with pseudocode just yet. We will actually do it just with words. Yes, algorithms can be explained with words too. As I said, an algorithm is only a set of instructions that have to be completed in order to solve a problem. So here goes:
Given a list L, if we want to find the greatest element in the list, we need to do the following: We always need to record the greatest element encountered so far (let’s call this element G). So at the beginning, the greatest element encountered so far will be the first element of the list. We start from the second element of the list, and we move through the list, element by element, from left to right, until the end of the list: For each element we encounter (let’s call it x) we compare it with G, if our element is greater than G (x > G), we now say G is equal to the currently encountered element (G = x). If the expression x > G is not true, meaning if our element is not greater than G, we just skip to the next element. When we reach the end of the list G will be the greatest element in the list.
Expressed as pseudocode, this chunky paragraph boils down to a few lines:
L: list
G = first element of L (aka L[0])
i = 1
while i < L.size()
x = L[i]
if(x > G):
G = x
i = i + 1We will analyze this pseudocode later when we have learned more.
The sorting problem
I want to challenge you with another problem, and how do you think you can solve it. Suppose I’ve given you the below list:
L = [1, 7, 4, 2, 15, 9, 3, 6, 5]
and asked you to sort it, what would your answer be? Quite obviously:
L = [1, 2, 3, 4, 5, 6, 7, 9, 15]
but how did you do it? Did you “just do it”, or do you know exactly what type of logical path you followed to come to that conclusion?
Get Muhamed Cicak’s stories in your inbox
Join Medium for free to get updates from this writer.
Well, I cannot possibly know which algorithm you chose to sort the list, but I know that we need to find one to express our thoughts and be able to write down how to sort a list. One such algorithm is called the Bubble Sort algorithm. Explained with words, the bubble sort algorithm is as follows:
We move through the list, starting from the first element up until the element before the last element, and we compare the current element with the next element (lets call them x and y, respectively). If x is greater than y, we swap x and y, thus “bubbling” up the larger element to the right side of the list. If x is NOT greater than y, we just skip the current element, and x becomes y and y becomes y + 1. We do this until we have bubbled up the largest element to the end of the list (right-most side of the list). We then take the sublist that goes from the beginning of the list until the end of the elements that have not yet been bubbled up, (as we consider the bubbled up elements already sorted) and we keep applying the same algorithm until we have reached a point where all elements have been bubbled up at which point the list is sorted.
Let’s remember the previous example:
L = [1, 7, 4, 2, 15, 9, 3, 6, 5]
Now, we will trace the bubble sort algorithm. After each swap, I will show you the new state of the list.
(1, 7), is 1 > 7? No, do nothing.
(7, 4), is 7 > 4? Yes, swap.
New state of the list: [1, 4, 7, 2, 15, 9, 3, 6, 5]
(7, 2), is 7 > 2? Yes, swap.
New state of the list: [1, 4, 2, 7, 15, 9, 3, 6, 5]
(7, 15), is 7 > 15? No, do nothing.
(15, 9), is 15 > 9? Yes, swap.
New state of the list: [1, 4, 2, 7, 9, 15, 3, 6, 5]
(15, 3), is 15 > 3? Yes, swap.
New state of the list: [1, 4, 2, 7, 9, 3, 15, 6, 5]
(15, 6), is 15 > 6? Yes, swap.
New state of the list: [1, 4, 2, 7, 9, 3, 6, 15, 5]
(15, 5), is 15 > 5? Yes, swap.
New state of the list: [1, 4, 2, 7, 9, 3, 6, 5, 15]
Now, we have “bubbled up” 15 to the end of the list. We repeat the process for all other pairs (we now exclude 15 from our sort as it is already sorted). I will do for one more number and you can get the hang of the rest.
(1, 4), is 1 > 4? No, do nothing.
(4, 2), is 4 > 2? Yes, swap.
New state of the list: [1, 2, 4, 7, 9, 3, 6, 5, 15]
(4, 7), is 4 > 7? No, do nothing.
(7, 9), is 7 > 9? No, do nothing.
(9, 3), is 9 > 3? Yes, swap.
New state of the list: [1, 2, 4, 7, 3, 9, 6, 5, 15]
(9, 6), is 9 > 6? Yes, swap.
New state of the list: [1, 2, 4, 7, 3, 6, 9, 5, 15]
(9, 5), is 9 > 5? Yes, swap.
New state of the list: [1, 2, 4, 7, 3, 6, 5, 9, 15]
Now, 9 and 15 have been “bubbled up” or “sorted”. We do the same process for the remaining part of the list until when we have a single element left, at which point we have sorted the list.
Now you know an algorithm for sorting a list!
The following is the pseudocode for bubble sort:
L = [1, 7, 4, 2, 15, 9, 3, 6, 5]
i = 0
j = 0
while i < L.size() - 1:
while j < L.size() - 1 - i:
x = L[j]
y = L[j + 1]
if(x > y):
swap(L, j, j + 1)If you’re following the Programming Basics series of articles I am posting, the two pseudocodes mentioned in this article will be covered in the upcoming articles, when we have learned the basic concepts we need to understand them.
For now, try to identify things in life using “algorithmic thinking”, try to identify which things you have been “just do”ing so far, which problems you have been solving without knowing how, and try to consciously understand how you have been doing/solving these things. In the next article, we cover variables and how to deal with them. This introduction has been a little lengthy but you should know that knowledge in programming snowballs. The more you know, the easier it gets!
If you prefer learning through a video, I recommend you to checkout my video tutorial on Algorithms: https://www.youtube.com/watch?v=naUTM1sux-U
