What is an algorithm
Objective
[edit | edit source]There are several definitions for the notion of an algorithm. As an introduction to the concept, we shall study some simple applications.
By the end of this lesson, students should:
- Know what an algorithm is.
- Know what pseudocode is.
- Be able to write a simple algorithm in pseudocode.
Intro
[edit | edit source]What is an algorithm? An algorithm is a step-by-step solution to a certain problem. Richard Jeffery and George Boolos gave an informal description of an algorithm, and the powers it grants us, in Computability and logic:
No human being can write fast enough, or long enough, or small enough† ( †"smaller and smaller without limit ...you'd be trying to write on molecules, on atoms, on electrons") to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols.
Restated, this means that while no human could possibly write out an infinite series of things, humans are able to create a specific process to generate the portions of that series which are relevant to solving a particular problem. The specific list of steps thus created constitutes an algorithm, a concept at the very core of computer science.
Assignment 1
[edit | edit source]Algorithms do not only exist within the realm of computer science. Beginners may find it helpful to recognize the algorithmic thinking they already apply for daily life.
On a separate sheet of paper, list all the known possible steps in preparing/performing the following activities, be as descriptive and specific as you can be:
- Cooking/Frying an egg, sunny-side up
- The activities you do and the vehicles you ride in on your way to school
- Walking your dog at the park
These activities above might seem easy, but as you perform the tasks, you will encounter a series of trial-and-error sub-activities. For beginners, this is normal and you may tend to miss a few steps.
Assignment Solution and Discussion
[edit | edit source]As you were able to see in the assignments above, Algorithms are lists of instructions which are followed step by step.
Your solution to the case of egg frying should look like this:
1. Get the frying pan.
2. Get the oil.
a. Do you have oil?
1) If yes, put it in the pan.
2) If no, do you want to buy oil?
a) If yes, then go out and buy.
b) If no, you can terminate.
3. Turn on the stove.
4. Etc...
For the case of Frying an egg sunny side-up, have you forgotten to state that you will heat up the pan? Or maybe put in some oil? Should you put some oil in first before heating the pan, or should you heat the pan and then put some oil in? These are the possible conditions that you may encounter in preparing the algorithms for this task.
Once you have gotten used to writing simple algorithms, you can attempt to write pseudocode. Pseudocode is simply an algorithm which is written in a way that resembles computer code - it does not have to be in any particular programming language. People write algorithms in pseudocode because it is easier to see what a computer program will look like after it is written, and it may also be easier to notice logical problems in the algorithm.
Pseudocode doesn't lend itself well for non computerized tasks, but let's try writing some for the algorithm above:
get(frying_pan)
if you_have(oil)
then get(oil)
else
if you_want(oil)
then buy(oil)
else
terminate
turn_on(stove)
Spend some time reading that pseudocode. If you are acquainted with programming languages then the format above should seem familiar.
Required Assignment 2
[edit | edit source]Try writing pseudocode for the algorithms you wrote in the first assignment.
Get(leash)
Put(leash)on(dog)
If(weather)=(sunny)then
Go_to(park)
If_not
Cancel(dogwalk)
if (vehicle_location is known) {
transport_to(vehicle)
} else {
locate(vehicle)
}
if (destination location is known) {
if { vehicle is turned off) {
turn_on(vehicle)
} else { if (location of smart_phone is known) {
use_GPS(directions_to_location)
} else {
locate(smart_phone)
use_GPS(directions_to_location)
}}}
etc etc etc.
Required Assignment 3
[edit | edit source]Pseudocode (and programs in general) are best suited for mathematical problems. Try to write an algorithm in pseudocode for this math problem:
(x4 + 25y2 + 2z) − 13
(x4 + 25y2 + 2z) − 13
((x^4) + (25 * y^2) + (2 * z)) - 13
Conclusion
[edit | edit source]Algorithms are a series of step by step instructions for solving a problem. Pseudocode is an algorithm written in a way that resembles computer code. To practice writing algorithms in pseudocode, you first think of a complex problem and consider the logical solution before writing it out.