In some sense, an algorithm is a little bit like a recipe. Let's say that you wanted to makes some chocolate chip cookies from scratch -- the recipe is the step by step system that will take you from raw ingredients to a batch of cookies. In a sense, the recipe is your solution to the problem of how to make a cookie given a bunch of flour, butter, sugar, chocolate chips, pans and an oven. A recipe might be defined as "good" for a wide variety of reasons: if it uses the cheapest ingredients, it makes the best cookies, or it takes the least amount of time. And a good recipe is also one that we can use to make any amount of cookies we want, not just a pre-set number.
The study of algorithms, however, is not the study of how to FOLLOW the recipe. It is the study of how to WRITE the recipe given a type of problem, and the ingredients and constraints to solve the problem. To be able to solve the problem I posed in the post about Induction from Patterns, you would have needed to develop an algorithm to deal with the cases where the number of diamonds grew too large.
If you ever interview with a software company, they are likely to ask you questions that test your ability to develop algorithms. At a place like Google or Microsoft, they often ask less sophisticated algorithm questions to non-technical applicants to test their ability to think logically. These problems are often in the forms of puzzles or games.
One of my co-workers Mr. Ankamah recently showed me a Flash rendition of one such problem, known as the Missionaries and Cannibals. This is an excellent game since it requires somewhat non-linear and non-obvious techniques to accomplish the task. Also, it is analagous to techniques that are used in computer algorithms that perform very complicated tasks as efficiently as possible.
It is interesting that one of my students, of Mexican heritage, actually pointed out that a particular version of this game that I found (but can't anymore) is really racist, and he refused to play. In this rendition, the cannibals are depicted as dark black people, and the missionaries are white. This game, he remarked, made it seem like black people are savages and white people are helpless spiritual victims. I was very impressed with his insight, and didn't make him play that version.
But I found THIS version, which makes the cannibals look like alien monsters. He told me that this version was racist against monsters but since, I argued, there are no such things as monsters, I did not deem this argument as persuasive, and made him play anyway.
To begin, try the game at the link above, and answer these questions:
We will consider in this section three examples of river crossing problems, including the Missionary and Cannibals problems mentioned above.
An often overlooked part of solving problems like these is developing a system to write down the various steps that you are trying to solve the problem, and to begin to find a pattern in the way the steps are executed. In the case of finding the triangles in the Latin American bracelets in Induction from Patterns, we called this process of extending our solution to a single case to the general case, induction. To see how this works, let's start with a different type of river crossing problem, namely the jumping frogs.
http://www.cut-the-knot.org/SimpleGames/FrogsAndToads.shtml
One of my co-workers Mr. Ankamah recently showed me a Flash rendition of one such problem, known as the Missionaries and Cannibals. This is an excellent game since it requires somewhat non-linear and non-obvious techniques to accomplish the task. Also, it is analagous to techniques that are used in computer algorithms that perform very complicated tasks as efficiently as possible.
It is interesting that one of my students, of Mexican heritage, actually pointed out that a particular version of this game that I found (but can't anymore) is really racist, and he refused to play. In this rendition, the cannibals are depicted as dark black people, and the missionaries are white. This game, he remarked, made it seem like black people are savages and white people are helpless spiritual victims. I was very impressed with his insight, and didn't make him play that version.
But I found THIS version, which makes the cannibals look like alien monsters. He told me that this version was racist against monsters but since, I argued, there are no such things as monsters, I did not deem this argument as persuasive, and made him play anyway.
To begin, try the game at the link above, and answer these questions:
RIVER CROSSING PROBLEMS
We will consider in this section three examples of river crossing problems, including the Missionary and Cannibals problems mentioned above.
An often overlooked part of solving problems like these is developing a system to write down the various steps that you are trying to solve the problem, and to begin to find a pattern in the way the steps are executed. In the case of finding the triangles in the Latin American bracelets in Induction from Patterns, we called this process of extending our solution to a single case to the general case, induction. To see how this works, let's start with a different type of river crossing problem, namely the jumping frogs.
http://www.cut-the-knot.org/SimpleGames/FrogsAndToads.shtml
<
QUICKSORT
...tbc
No comments:
Post a Comment