Algorithm

Last few weeks we learnt a lot about algorithm. We defined it, leant its properties and studied how to design an algorithm. Some interesting activities were done, too: role playing, magic show, route planning and robot game. I found algorithm so common and important, but it is a little bit difficult for me to memorizing so much things.

Some Basic Information

The first question is obvious: what is an algorithm? After some discussion, we got a perfect definition of it: a set of step-by-step clear instructions to solve a problem in a definite amount of time with the best effeiciency possible.

Then, by sharing some examples, we found out that algorithm has five properties. First, finiteness is important. That means an algorithm must end in a finite number of steps, because we can’t wait for years. Second, definiteness: each step of an algorithm must be precisely defined, so the computer can operate the same way as you expect. What’s more, an algorithm must has input and output. Finally, all of the operations in the algorithm need to be basic enough, so the computer can understand it. Also, people want to save time and space, so algorithms are always very “clever”, that it use the best way to solve a problem. That property is called effectiveness.

ALgorithem is also a critical part of computational thinking, which include decomposition, abstraction, pattern recognition and algorithm.

Algorithem Magic

We were divided into four groups to conduct four magic shows about algorithm. I was with Tiger, Lucy, Elizabeth and Adam, doing Australian Magician’s Dream. Unfortunately, we did the same show as group two. It really gave us a lesson: we should check before we start. Also, I found that gourp two’s presentation involved computational thinking, which I didn’t think about. They related decomposition and abstraction with the magic. I thought we both did a great job.

This trick is about finding the 16th card, and all we did is divide them into two piles and repeat the process. When group two was explaining, one of them said the total number of the cards chosen should be less than thiry-two. I didn’t think so, because if a magic show has so many uncertainties, it can not be called a magic show. Smart magician can handle situations, for example, if it is more than thirty-two, we can change the card we pick, that’s all.

My part was to expain the link to computer science. The magic show is the exact algorithm for computers to find data. I used sixteen cards which all have binary numbers written at the top, and some holes indicating their numbers. If we want to find sixteen, which is 10000 in binary, we can just use a toothpick respectively pass through the last four zeroes. After the first round, all the odd number cards go, because I shake out all the cards that have one as last number in binary. We keep that and finally only number sixteen remain.

Other groups showed us The Intelligent Piece Of Paper and The Red Black Mind Meld. When Jerry was explaining different situations of the game, I thought he was wrong so I interupped him. But after his explaination, I realized I was wrong. At that moment I was a little embarrased, for I thought I’m not very polite and I’m stupid. I should think deeper before asking. But I also think I gain more by asking this question, for I realized a blind point of my logical deduction.

Other Interesting Activities

Video

We watched an really beneficial video-“The Secret Rules of Modern Living: Algorithms“. I’m very surprised that algorithm is everywhere. It is not just a term in computer science, it hinds quietly behind all things and rules our lives. An intersting example of it is a mathematical game, in which there are thirty cards in a box and two players who can only take away 1-3 cards at once. In order to win the game, the beginning person can just take away two cards, and then every round make sure the sum of the card took away is equal to four, so after seven rounds the person will win. Another example is a mathcing algorithm which can apply to marriage assigning, college admission, roomates choosing and so on. As for college admission, the first step is that all students propose their dream school and then the school reject extra students whom they like least according to their principles. After enough rounds there will be a stable outcome.

Role Play

In order to understand algorithm more clearly, we did a human robot role palying. Lucy, acting as a robot, used her coat to cover her eyes so that she can only listen the instructions. Another student give instruction for directions and actions for Lucy to guide her touch a thing. Finally we succeeded but spent a lot of time. That reminds us the property of an algorithm-effectiveness. Next time we can use specific degree like”forty-five degree to your left” to better instruct robots.

Route Planning

Lisa and I worked out a route that starts form the hotel and visits every tourist site exactly once. After we finished, we shared our route with another group, suprisingly found that there is another design with equal efficiency. I found some moral through this activity: most times there are more than one way to achive a goal, and people can’t label them with ‘bad’ or ‘good’. So the one that suits you is the best and we should always be willing to listen to others, because sometimes when we think we are right, they are not wrong, too.

Robot Game

We did a homework about designing the route for a robot to light the squares. The game is on lightbot.com/flash.html. At first, it is pretty easy. Decomposition is really impoortant in designing the route, for we need to light the square one by one so we need to split the problem into small pieces. Then, in order to be more efficient, we are asked to repeat some procudures.

I think smart repetition can also save our time and energy in daily life. For instance, I want to improve my English. Instead of read a short paragraph one day and listen to English songs another day, which require me to think what to do everyday, I can just read an English book. Everyday I can read one chapter and then read it aloud to practice my speaking, so I can get used to it and thus can follow this perfect plan everyday.

Design An Algorithm

We also leant how to design an algorithm. There are two main areas to look at: the big picture (what is the final goal?) and the individual stages (what barriers need to be overcome on the way?)

Understanding the problem is important. We can ask ourselves some questions to help check if we understand the problem thoroughly. For instance: What are the inputs(what do I alrealy have) and outputs(what result do I want) of this problem? What do I need more? What decisions need to be made in the problem? Are any areas of the problem repeated? In what order do instructions need to be carried out? Take brushing teeth as an example. If you do not conduct it in the right order, which means you brush your teeth before putting toothpast on your toothbrush, the effect will not be as good as that of a right order.

Then, we learn four expressions of algorithm. First, it is Natural Language. It means simple english and is always too verbose and ambiguous. Flow Chart, a formalized graphic representation, is another expression of algorithm. Pseudocode is another form. It is a generic artificial language, and has some naming conventions. For example, while means a loop, variable names are all capital, and == means compare. Finally, programming language is also useful. It is an artificial language to communicate with computer system.

The magic and wisdom behind algorithm really fancinates me, and I’m a little overwhelmed with so many things: definition, properties, examples, designing and expressions. Really looking forward to new cs knowledge and intriguing class activities!