Introduction
What sup guys, this is Wayne and I am about to start this week’s blog, please remember to subscribe my channel to see the new updates. Last week we spent most of the time understanding one of the most important term in computer science, the Algorithm. This blog will contain the following parts:
- 1. The basic introduction on Algorithm.
- 2. Design an Algorithm.
- 3. Different ways to express Algorithm.
- 4. Explanation on some Algorithms introduced in “The Secret Rules of Modern Living: Algorithms”.
- 5. In-class-activities that relates to Algorithm.
- 6. Conclusion and Reflection.
Basic introduction on Algorithm
The definition of Algorithm
Algorithm is a series of step-by-step clear instructions to solve a problem within a specific amount of time in the most effective way.
—Mr. Pete
To carry out a specific task, some computer programs have to contain algorithms that show specific instructions in a specific order. The order of instructions in an algorithm is very important, because it indicates which step of processing or output the computer should preform in specific occasion. For example, if we design an algorithm that can preform simple addition of two number, the process of calculation has to be after the user input the numbers.
Another thing is that there are maybe tons of different algorithm which can solve one individual problem, but there by exploring the different approaches existing, we can find the algorithm that is most suitable for that issue. For example, if we want to watch the NBA game on TV, there are many algorithms that can address this problem. Like, algorithm A: Go through the TV channel one by one until we find the sports channel which is displaying the basketball match. Algorithm B: Choosing the category “Sport” and search for the channel that has the game on. Both algorithms can actually work, but if the time is limited, or if you do not want to miss the 3-pointer from Harden, then it maybe more reasonable to use the second algorithm which is more efficient than the first one.
Some properties and characteristics of Algorithm
Finiteness: “An algorithm must always terminate after a finite number of steps… a very finite number, a reasonable number” This means that as an algorithm, the number of instructions contained by it should be limited, and an algorithm with infinity steps is both impossible and inefficient.
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” This means that the instructions included by an algorithm should be clear and precise, because even in a simple step, an un-defined instruction can cause an error that may effect the whole system and cause it not-functioning appropriately.
Input: “… quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects” This is because an algorithm is designed for the user to address a specific problem but without an input an algorithm can not provide specific solution in the situation, which makes it less intelligent.
Output:“quantities which have a specified relation to the inputs” the output is usually the result or the solution to the issue.
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” It is very crucial that the algorithm should be efficient and effective, because it has to be preformed in some way, and the when it is operating, the time matters a lot.
Design an Algorithm
Computational Thinkings
To design an algorithm, we first need to understand the whole process of solving a problem, so in class, Mr. Pete introduced us the Computational Thinkings, which contain the following parts:
- 1. Decomposition
- 2. Abstraction
- 3. Pattern Recognition
- 4. Algorithm
For example, if we want to select a film to watch at Saturday night, viewing all those fantastic films on the Internet we can first break down those films online into individual ones, which can help us in further steps and this is called “Decomposition.” Next, we group different films into different categories, like action movies, super-hero movies and e.t.c. We called this “Abstraction.” Then, we start to recognize a pattern, like most of the Marvel Film has a relatively high quality, films directed by Mr.Nolan have attracting plot… which is obviously a “Pattern Recognition.” Finally, we can list all the necessary ways to look for a film to watch in an logical way and produce an “Algorithm.”
Designing an Algorithm
There are two main areas to look at: The first thing is the big picture-what is the final goal? Because with considering the final goal, we understand the purpose of the whole algorithm, and may explore the most efficient way to the purpose much easier and faster.
The second thing is individual stages – What barriers/obstacles need to be overcome on the way? While realizing the challenge standing in our way, we can come up with specific solution to address those obstacles. For example, if we are writing an algorithm for choosing a film to watch in China, then one barrier is that many films rating R and PG-13 in America didn’t pass the Chinese film Censorship System which means they are not available. To overcome this obstacle we have to add one instruction into the algorithm “turn on the VPN.”
Understanding the Problem
Having a full understanding on the problem before design the algorithm can clarify the purpose of the algorithm and provide a more well-organized vision of the algorithm we need to design. Here are some questions that need to be clarify:
- 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?
Different ways to express Algorithm
Natural Language
While using natural language as an algorithm to a person, it is just basic different orders arranged in a correct order. However, when expressing an algorithm to a robot, the robot will preform: Fetch the Instruction, the robot receive the instruction or input from the user; Decode the Instruction, the robot decode the input from English sentence into computer language; Execute the Instruction, the machine just preform the instruction according to the algorithm it decoded.
Pseudocode
Pseudocode is a planning tool that allows us to design the flow of a program prior to writing the code, which consists of a series of English-like statement that describe a task or algorithm
–Mr. Pete
The Pseudocode is a Programming-language-like language, which used similar grammar as Java and C++, that mainly focus on the flow of the instructions. Expressing the Algorithm through Pseudocode can help us understand the order of instructions computer will preform when running the program, it also helps us to have a deeper understanding on the computational thinking, because it provide a language similar to the programming language.
Some Common Pseudocode Notations are:
- input – indicates a user will be inputting something: input NUM
- output – indicates that an output will appear on the screen: output “please input a number”
- while – a loop (iteration that has a condition at the beginning): while NUM<=1
- for – a counting loop (iteration)
- repeat–until – a loop (iteration) that has a condition at the end
- if–then–else – a decision (selection) in which a choice is made: if A<=4 then output “wrong answer” else then output “You are correct”
Other ways to express Algorithm
There are many other ways to express an specific algorithm, like the Flow Chart, or Programming language like Java and C++. Those will be covered in the future blogs.
Explanation on some Algorithms introduced in “The Secret Rules of Modern Living: Algorithms”
Face Detection Algorithm
Face Detection Algorithm help to keep the human face in the photograph in focus. To achieve this goal (To solve this problem), the output it preform is finding a human face and produce a box around the person’s face. The algorithm works by scanning the image, looking for four abstract patterns associated with a face. When these are detected one after the other, then the algorithm indicates it finds a human face.
Page Rank Algorithm
Page Rank is the heart of google search engine. When you search for something on Google, there will appear thousands of pages related to the word. What Page Rank do is to rank those pages so the one at the top is the one you are most likely to be interested in to increase the quality of web-search. In this algorithm the input is the web’s link, and it will rank the website which is linked by a lot of other website higher, and the website which is linked by another website with lots of links higher. And when the input changes the ranking will be updated, because the importance of a page is related to the importance of the page that link to it.
In class Activities that related to Algorithm
The Algorithm Magic Show
Our magic show is called “Red and Black Mind Meld.” I will not talk about the details related to this magic show. The first step is to create a model of the trick. That involves abstraction. Abstraction just means focus only on the information about the trick that matters, while hiding all the detail that doesn’t. A model is just an abstraction of a part of the word we are interested in. To generalize the mechanism behind this magic show is if there are 52 cards (26 black and 26 red) and we got R1, R3, R4, B1, B3, B4, 6 pile of cards in total, then we have a serious of equations:
After modeling this trick we can see it is a lot more easy to understand why the red pile3 will have a same number as the black pile 4. And behind this magic show, it is all algorithm that provide step to step instructions for the magician to preform on the stage, which contain logical reasoning and mathematical calculation that brings the show to address the problem: getting the same number of cards in the two piles.
Role-Play Activity
In this activity, one student will give detail algorithm to another student who got his or her eyes covered. The task is to get a bottle on the desk without stepping on the pen which is placed on the ground. And I discovered that the more clearly the instruction is the more efficient the whole process will be. For example “Turn to your left for 30degrees” is much more better than “Turn Left.” And this taught me that when writing an algorithm, one of the most crucial thing is to write down the most precise instruction as I can.
LIGHTBOT Homework
Then we did a homework related to algorithm which name is LIGHTBOT. The game is mainly controlling a robot by giving a set of step by step instructions to light up all the blue square in the game. In this homework, I have a better understanding in the loop system, which means a cycling system that repeat itself again and again, until the work is done.
Conclusion and Reflection
In this week I learnt a lot about algorithm.
The one thing that I thought is the most important thing that I learnt within this week is that, the most crucial thing for an successful algorithm is its flow. Because it is the flow that determine the order of instructions and how will the program process with the input data. So, in the future while writing Pseudocode or actual programming language, I will pay more attention on what is actually going on behind the instructions and how does the computer preform those instructions one by one and finally lead to an end. I think this will benefit me a lot in the learning of Pseudocode and Flow Chart in the future.
Wayne's Blog 