What is an algorithm? What are the properties of an algorithm? How to express an algorithm? And how are algorithms used in real life? These are some of the main questions we explored during the past few weeks in the computer science class. Welcome, to the world of algorithm.
Definition and Properties of Algorithm
Definition of Algorithm
The definition of an algorithm is a set of step-by-step clear instructions to solve a problem in the most efficient way in a reasonable amount of time.
Relating to computational thinking, the core of computer science, algorithms, or algorithmic thinking, is the final step of it. Computational thinking applies to everything; it helps solve all kinds of problems in life. Taking finding a TV show to watch as an example of a problem and apply computational thinking in solving this. Firstly, decomposition. In this case, we can break down all TV show in categories. Secondly, abstraction — grouping similar TV shows into a category and searching only in a particular category at a time. Thirdly, pattern recognition — if the director is famous and genre is romantic then it should be a good one. Finally, algorithm — listing all possible steps in order to find a TV show for anyone to efficiently search the best.
Activity: a Human Robot
This gives us an idea of the importance of algorithms, which we can better understand through the following activity we carried out during the class — a human robot. In this activity, a student was blindfolded to act as a robot while other students gave instructions for directions and actions for the robot student, to reach for an hourglass. Even though this took several minute, eventually, the student successfully got the hourglass. She reached her objective, which was WHAT WENT WELL. Yet it could be EVEN BETTER IF clearer instructions were given, by further quantifying. For example, instead of saying “turn left”, “turn counter-clockwise for 90 degrees” might be a better instruction which can be easier processed.
Through the previous examples we can clearly see how much a good algorithm matters. A clear and well-designed algorithm can directly pump the whole process of problem-solving into a much higher efficiency in obtaining the best result.
Properties of Algorithm
Five crucial properties exist for algorithms — finiteness, definiteness, input, output, and effectiveness.
- Finiteness: “An algorithm must always terminate after a finite number of steps… a very finite number, a reasonable number.” This matters since without finiteness, an algorithm can be really complex, including millions of steps, going on indefinitely.
- Definiteness: “Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.” Only clear, accurate and precise instructions can be carried out successfully and efficiently.
- Input: “… quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects”
- Output: “quantities which have a specified relation to the inputs” Just like all computing systems, an algorithm always has inputs and outputs.
- Effectiveness: “… all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil”
Avtivity: Guided Tour – City Tube Map
Divided into groups of two, we participated in an activity Guided Tour — City Tube Map. The instructions of the activity reads like this: “starting at the hotel, plan a route so that tourists can visit every tourist attraction just once ending up back at the hotel.”
Different groups planned different routes; there are more than one solution to this problem. In fact, everything can be solved in different ways, whether effective or not. Each way has its own advantages and disadvantages. So we need to keep open-minded, to accept different ideas and opinions, which is probably why ‘open-mindedness‘ is included in the IB learner profile.
Video: “The Secret Rules of Modern Living: Algorithms”
After learning the basic concepts of algorithms, we watched a video which introduced us to many algorithms present in our daily life. Among all the algorithms shown in the video, two impressed me the most — the greatest common divisor algorithm and the bubble sort algorithm.
- The Greatest Common Divisor Algorithm
The greatest common divisor (GCD) algorithm was one of the first algorithms ever designed. Euclid, always considered as the greatest mathematician from 3rd to 4th century, developed a series of step-by-step instructions that elegantly solve the common math problem of finding the GCD of any two numbers.
Imagine you’ve got a rectangular-shaped floor, and you want find the most efficient way to tile it with square tiles, in other words, finding the largest square tile that’ll exactly divide the dimensions of the floor with nothing left over. This is, in fact, the geometric version of the greatest common divisor problem — the dimensions of the floor are the two numbers, the size of the tiles which we’re trying to work out is their GCD.
（The link of the video: https://www.youtube.com/watch?v=kiFfp-HAu64)
- 1. Fill the rectangle with square tiles corresponding to the smallest of the two dimensions.
- 2. Then do the same thing to the remaining rectangle: fill it with square tiles corresponding to the smallest of the two dimensions of it.
- 3. Do the same thing again and again until there’s no remaining rectangle, in other words, until the square tiles perfectly fill the leftover space.
- 4. When the entire rectangular floor is filled, we can get the GCD of the initial two dimensions is the size of the smallest square filling the floor.
The amazing thing about this Euclidean algorithm is not only that it is one of the first algorithms ever existed, but also that it is a simple step-by-step method that can successfully find the GCD whatever the two numbers are — it’s an efficient general solution to the greatest common divisor problem.
- Bubble Sort Algorithm
Being considered as one of the most iconic sorting program of all time, the bubble sort algorithm was created in the 20th century. It gets its name because with each round of the algorithm, the largest sorted object ‘bubbles’ to the top/end.
The basic rule of the bubble sort algorithm is to consider the objects, or numbers, in pairs, and swap them over if they are in the wrong order. To see how it works, we’re going to sort 7 numbers, from 1 to 7, in the increasing order.
- Initially, the numbers are arranged as following: 3, 5, 2, 1, 6, 4, 7. First, consider the first pair of numbers — 3 and 5 — and we can see that they are in the right increasing order, so we leave them there.
- Then consider the next pair: 5 and 2. 5 is larger than 2 so they are in the wrong order, then we swap them over. So now the numbers are 3, 2, 5, 1, 6, 4, 7.
- The next pair, 5 and 1, are in the wrong order, so we swap them over as well. Now the numbers are 3, 2, 1, 5, 6, 4, 7.
- Repeat this process pair by pair and we will reach the last number, 7. By now, the numbers should be arranged as 3, 2, 1, 5, 4, 6, 7.
- Then we start from the first pair of numbers, 3 and 2, all over again.
- After the second round, the numbers are 2, 1, 3, 4, 5, 6, 7.
- Then after the third round, we’ll be able to get the numbers in the correct increasing order: 1, 2, 3, 4, 5, 6, 7. Now, the algorithm stops, since there are no pairs to swap around.
From the previous procedures we can see that bubble sorting can be somewhat inefficient when the scale of sorting sample is large, for example, when organizing large numbers of data, yet still, the bubble sorting algorithm is iconic for its elegant simplicity and straight-forwardness.
Project – Algorithm Magic
After the class, we were assigned to prepare a magic and present it to the class. Our group was assigned ‘the intelligence piece of paper’. Basically, the magic was a set of instructions, or an algorithm, to win the game of ‘cross and naught’. The algorithm is shown as follows.
Our group presented the winning algorithm and explained it with the concepts and steps of computational thinking. Through this, we fully realized that everything in life can be explained and solved using computational thinking, and computational thinking is making our life much more organized and understandable.
Designing an Algorithm
There are two main things we need to look at when designing an algorithm. First, the big picture, meaning to consider what is the final goal. Second, the individual stages, the barriers and obstacles need to be overcome on the way.
Before an algorithm can be designed, it is important to check that the problem is completely understood, which can be done be asking yourself the following 5 questions.
- What are the inputs into the problem?
- What will be the outputs of the problem?
- In what order do instructions need to be carried out?
- What decisions need to be made in the problem?
- Are any areas of the problem repeated?
Expressions of Algorithm
There are generally four kinds of expressions of algorithm: natural language, flow chart, pseudocode, and programming language.
- Natural Language
Natural language is written in simple English, and is usually verbose and ambiguous. A natural language can be easily carried out by fetching, decoding, and executing the instructions step by step. A simple example of an algorithm expressed in natural language would be as follows:
Start the program
Display the message “THIS WILL BE PRINTED TWICE” two times
Display the message “THIS WILL BE PRINTED FOUR TIMES” four times
End the program
- Flow Chart: formalized graphic representation
- Programming Language
Programming languages are artificial languages to communicate with computer system, instructing a computer or computing device to perform specific tasks. Common programming language includes BASIC, C, and Java, with each of them having its own unique vocabularies and a set of grammatical rules.
- Pseudocode
A pseudocode is a generic artificial language, consisting of a series of English-like statement that describe a task or algorithm. It is a planning tool that allows us to design the flow of a program prior to writing the code, so it lies between natural language and programming language.
Common pseudocode notations we use even as beginners are listed as follows. “input” indicates a user will be inputting something; “output” indicates that an output will appear on the screen; “while” is a little more complicated, indicating a loop (iteration that has a condition at the beginning); “for” is loop as well, a counting loop (iteration); “repeat–until“, again, is a loop (iteration), but one has a condition at the end; “if–then–else” indicates a decision (selection) in which a choice is made. Besides all the vocabularies above, another crucial rule of pseudocode is that any instructions that occur inside a selection or iteration are usually indented.
Even though the common notations are the same, the rules for pseudocode can be slightly different under different curricula. For instance, in IB (International Baccalaureate) curriculum, there are several approved notations worth noting, as shown in the charts below.
Here’s an example of a simple pseudocode to tell a user that the number they entered is odd or even.
output “enter a number”
input NUM
if NUM % 2 = 0
output “it’s an even number”
else
output “it’s an add number”
end if
A pseudocode that tells a user that the number they entered is odd or even
Through the study of these weeks, we dived into the world of algorithm, a set of step-by-step, clear instructions to solve the problem in the most efficient way in a reasonable amount of time. Algorithm is truly a universal language that makes the world organized and more manageable.
Sophia's Blog for CS 