Algorithm Design
If you have ever baked brownies, you know that you first have to gather the ingredients,
then measure them, mix them together, prepare the pan, heat the oven and cook them.
If you forget the sugar they don’t taste good and you have to start over.
If the oven is too hot you may burn them.
Determining the right steps, following them correctly and completely and learning from
mistakes are all part of the process of algorithm design.
Algorithms are step by step instructions to get something done or the set of rules describing
how something works.
A recipe, or a set of dance steps, or the storyboard for an animation are all algorithms.
Throughout the three previous steps in the Computational Thinking process—decomposition,
pattern recognition and abstraction you have been working toward the design of an algorithm,
or “a set of instructions for completing a task.”
Algorithmic design moves the problem from the modelling phase, to the operation stage.
Algorithms take the form of a recipe or list of instructions that utilize efficiency and
are written in such a way that they could allow for automation, or use of computers
to execute tasks, or they could simply be followed by a human.
This set of instructions should be sequential, complete, accurate and have a clear end point.
If written for a computer the algorithm must be comprised of a series of tasks written
in a way that a computer is able to perform.
In this video we will focus first on algorithms that don’t necessarily involve computers,
and secondly on some of the key understandings necessary to prepare an algorithm so that
it could be executed by a computer.
Although the term “algorithm” might strike fear into the hearts of some who last encountered
it in high school or college math classes, the definition of this term is simply “a
set of rules for solving a problem in a finite number of steps.”
An algorithm is a set of instructions and may or may not involve mathematics.
For example, a simple, digestible algorithm that we all use is a recipe.
The sequence of steps in a recipe must be followed in a certain order for the final
product to taste good.
You wouldn’t bake brownies before you mix the ingredients together.
Or grease the pan after the batter has been poured in.
Another simple example is getting dressed in the morning.
If you put your jeans on before your underwear you might draw some funny looks!
We have been working with this necklace example problem throughout the course, one step at
a time:
A necklace is constructed from 20 blue beads and 14 red beads.
Each blue bead costs $0.22 while the red beads cost $0.33 each.
The cost of the thread is $0.14 per inch, and 24 inches are required.
What is the total cost of materials for the necklace?
To create an algorithm, let's write down all the steps it takes to solve this problem:
1.
Break the problem down into its components—blue beads, red beads, thread, their costs and
amounts 2.
Identify subproblems that need to be solved.
Determine the cost of each quantity of material (cost of blue beads, cost of red beads, cost
of thread.), then add the costs of all three materials together.
3.
Recognize patterns between subproblems--in this case, the first three subproblems can
be solved in parallel, they don’t have to be solved in a particular order.
The second subproblem is sequential--meaning the costs for each material must be calculated
before they are added together.
4.
Set up an operation that can be used for the first subproblems.
(material quantity x material cost) 5.
Calculate the cost for each type of material using the appropriate variables
6.
Add the costs for each of the three materials together to determine the total cost of the
necklace Let’s return to and review the Make a Monster
example.
We first decomposed the monsters into parts (eyes, nose, mouth, etc.) and then found similarities
between the features of the three monsters.
We then used abstraction to replace the specific types of body parts with blanks so that any
type of feature could be inserted.
We have now created a recipe to use for our algorithm.
We can use it to instruct other students to recreate the same or design new monsters based
on the feature types.
For example, if you provide this algorithm, you come up with this new monster.
When we were discussing decomposition we took some time to explore Bee-bot, the bee that
moves a step at a time towards its destination.
We looked at how its overall path was broken down into steps.
Now we will focus on Bee-bot in terms of algorithms.
Can you give Bee-bot the correct set of instructions to move from the start to the flower for Level
3?
How about for Level 5?
Level 6?
Similar to Bee-bot, write out a set of instructions and have someone else follow your instructions
exactly to complete a task.
You can emulate Bee-bot by finding a tiled floor or using chalk on pavement to draw a
grid.
Take turns writing out instructions for each other to follow to move from square A to square
B. Students must enact instructions exactly as they are written to see if all steps are
correct.
The person who wrote the instructions may need to revise them if they don’t work.
Here is another similar activity, but in this one the instructions are for building a structure
rather than moving around.
Students work in groups to develop algorithms to recreate models made from plastic bricks.
Algorithmic design is critical in the Computational Thinking process.
If a computer is not involved, algorithmic design provides a recipe or instructions to
solve the problem.
If a computer is involved, a human has to be able to tell it, in a language it can understand,
how to solve the problem.
For a computer to be able to aid in the efficiency of solving your problem, the algorithm must
be comprised of a series of tasks written in a way that a computer is able to understand
and perform.
This involves a translation between the language of humans and the high level language of computers.
Humans speak languages like English, Spanish, or Arabic.
Computers speak in bits, the basic unit of information in computing.
You may have heard of the binary system, where the numbers 0 and 1 are used to communicate
information.
These are bits.
Without getting too deep into Computer Science, suffice it to say that computers speak many
different kinds of high level languages---such as HTML or Javascript which are comprised
of bits.
Computer programmers work to create instructions through coding that are born from human ideas
but translated for a computer to understand.
WISIWYG (What You See Is What You Get) interfaces can help you understand this concept--these
are designed so that non-computer science savvy people can use computers to build what
they need in their human language, but see how that translates to computer code.
Here are a few necessary understandings when thinking about designing algorithms for computing
(or otherwise).
Your instructions need to be unambiguous.
For example, when baking it is more clear to say bake until a toothpick comes out clean
rather than just bake until done.
An example for a computer could be “choose a number between 1000 and 2000” instead
of just “choose a large number.”
You need defined inputs and outputs.
The input for the Make a Monster example is one name for each feature.
The output of the algorithm is a new monster’s face.
For the Bee-bot it is a series of directional steps using forward, backward, left turn and
right turn.
The output is the motion performed by the Bee-bot.
You need to have a defined end point.
Your algorithm should answer a question or produce a result and be clear when it has
finished.
Your instructions must be sequenced in the correct order to complete
the task at hand.
Flowcharts can help identify actions and the order in which they need to
occur.
You may find you have sets or pieces of the instructions that need to happen over and
over again.
This is called a loop or iteration.
You may have conditional statements that affect the variables (if/then, yes/no, true/false).
In these cases, the first condition dictates the second.
You need to be able to interpret the computer’s results.
When designing an algorithm, it may be difficult to know if it is working and the outputs are
correct.
Different algorithms are developed to solve the same problems and they can produce different
results.
This is why testing and revising algorithms is important.
You can’t depend on the computer or machine to do all the work--you have to interpret
the results you get, think critically and determine whether or not they make sense.
You have now experienced all the steps involved in Computational Thinking--you have decomposed
problems, identified patterns, abstracted information and designed algorithms or instructions
to solve a problem--using a computer...or not.
But how do you know when the process is finished?
How do you know when you are done?
It can be difficult to know if you have accounted for all the important factors and if you are
truly solving the problem.
Steps and skills involved in Computational Thinking can and should be iterated (repeated).
Testing is the way to determine if it works or needs refinement.
More often than not a model that arises through Computational Thinking that is put into operation
through algorithmic design must be reevaluated and refined through testing.
If your solution doesn’t quite work or make sense, you have to return to the earlier steps
in the process and try to identify where a mistake may have occurred.
This process of testing and identifying and learning from mistakes is the key to solving
big problems.
Just because you haven’t learned how to write computer code doesn’t mean you can’t
try creating algorithms for computers and programming!
Several free online platforms allow you and your students to manipulate pre-written blocks
of code that represent different tasks or actions.
By sequencing, grouping, copying, repeating code, disguised as colorful blocks, you are
capable of creating and playing your own unique computer animations and games!
So you don’t have to know how to program (write code) but you do have to understand
algorithms (creating a logical set of instructions).
In fact, doing this is a fun way to introduce algorithms to your students.
Creating a game or animation in this way is an excellent method for learning how algorithms
work.
We’ll use Scratch as an example of one of these programs.
You can play with Scratch without creating an account (via the Create tab), or, if you
set up a free account on the Scratch website you will be able to save your projects.
You are immediately able to start to experiment with creating algorithms.
You can choose a “sprite” (character) and and create and/or control its motion,
looks, sounds, and other variables by dragging and stacking coded boxes.
Concepts such as loops or iteration can be explored using the boxes in the “control”
section.
You can access operators to create conditional clauses within your algorithms in both the
“control” and “operators” sections (operators are the conditional terms we talked
about earlier).
As you or your student’s understanding advances, you can create and add in your own coded blocks
for any functionality you can dream up!
Scratch is open source which means you can see and share your creations and also explore,
try out and remix the creations of others.
In fact, the Bee-bot online program we have been using during this PD was created in Scratch!
The ultimate goal for using computational power in solving problems is to solve seemingly
unsolvable problems, and to solve them as efficiently as possible.
Figuring out what instructions to give a computer for it to solve a problem efficiently means
thinking creatively.
Computational Thinking has led to many of the incredible tools that have become indispensable
in our everyday lives.
Without Computational Thinking today’s cars wouldn’t run and today’s planes wouldn’t
fly as they are controlled by computers.
Computational Thinking has and continues to streamline and optimize efficiency in manufacturing
processes to provide you with the products you buy.
Computational Thinking has led to such useful inventions as Google Maps and virtual reality.
We as humans can learn from our mistakes and advance our understanding and knowledge to
solve bigger and more difficult problems.
We can work together and it helps to have a systematic method like the steps of Computational
Thinking to help us tackle seemingly impossible problems.
Now especially, when solving problems can be greatly advanced by taking advantage of
the efficiency of machines and computers it is increasingly important to plan our problem
solving methods to address their incorporation.
Today’s students are tomorrow’s problem solvers!
Thank you for participating in this online professional development course.