Decomposition
The late Stanford University Professor George Pólya once said, "If you can't solve a problem,
then there is an easier problem you can solve: find it." This advice can be applied to any
problem by identifying easier to solve smaller problems within larger ones--decomposition.
For example, consider this ridiculous problem--how would you go about eating an elephant? The
answer? One mouthful at a time! This goofy analogy actually provides great insight into
the first step of problem solving through Computational Thinking. Big, complex problems
are comprised of smaller, and more easily solved subproblems or tasks. The process/strategy
of logically identifying these smaller problems and determining how to use the combined solutions
to solve the bigger problem is called decomposition.
The process of focusing on how a problem breaks into parts is called analysis. In contrast,
rebuilding or focus on how the parts come back together is called synthesis.
When a problem is broken down into smaller parts, these parts may be addressed simultaneously,
or in parallel. Organizing and multitasking to work on several smaller problems is called
parallelization. Parallelization is something you practice when you are cooking multiple
dishes at the same time Depending on the problem, these smaller parts
may need to be addressed in a certain order, or sequentially.
Let’s start out with a visual example of decomposition. Here is a necklace made of
red beads, blue beads and thread, each with a different cost. The problem: determine the
total cost to construct this 24-inch necklace. Think for a minute. How do you set up this
problem? What information do you need?
Without even thinking much you have likely already decomposed the problem into subproblems.
Since the materials all have different costs and are used in different amounts, an analysis
of this problem leads us to the conclusion that calculating the cost for each type of
material and then adding those answers together is the logical way to approach the problem.
Solving each of those subproblems is an example of parallelization.
We will return to this necklace example throughout the course to learn about each step in the
Computational Thinking process.
The process of decomposition in the previous example is reminiscent of solving word problems
from math classes in our past. It involves thinking about how to solve the problem, translating
from the language of words into the language of math and numbers, breaking it down logically
and eventually solving it.
Math problems often utilize decomposition. Here is an example of a 6th grade Common Core
Math standard that incorporates decomposition.
The following examples show how decomposition might work for other kinds of practical, everyday
problems that aren’t represented by numbers. For example:
• How does a bicycle work? By breaking down the bicycle into components and their functions
(such as gears, chain, pedals and brakes) and learning about how each works independently
first, and then together, one can understand how the more complex machine operates.
• The same is true for a car, plane or boat. • How does the human body work? A very complicated
question, but when we learn about the human body we focus on one system at a time - respiratory,
circulatory, digestive, skeletal and muscular - and then think about how they interact with
each other. • What happened at a crime scene? Police
and detectives are careful to observe an entire crime scene, but they have procedures for
in-depth examination of all the details (blood spatter, position of bodies, fingerprints,
fibers and other clues) to piece together the most likely scenario for what occurred.
• Composing a song--musicians think in terms of parts as they are writing music. There
are different roles for different instruments. Some play the bass beat, while others provide
the melody or harmony. All the parts work together to create a whole.
• Creating an app. The idea of building an app may be a daunting challenge if you
aren’t a computer programmer. However, anyone can work through the process of decomposition
for creating an app by thinking about what your app will do, what it will look like,
how you want the user to move through the screens and how much it will cost.
• Writing for an English class—the process of writing a paper involves outlining, or
breaking the idea for your paper into logical parts. When asked to analyze a poem you focus
on the poem as a whole, but also meter, rhyme, imagery, structure, tone, diction and meaning
individually.
As you can see, decomposition is a critical skill for solving complicated problems. Decomposition
is a relatively simple concept, but each problem will have different variables and decomposition
will need to be approached in different ways. It is critical to understand that to effectively
use Computational Thinking students must be able to logically break down a problem on
their own. It’s not enough to show some examples and assume your students understand,
students must practice breaking down increasingly complex problems to learn how to apply this
skill on their own and incorporate it into their process of thinking. Students need to
be responsible for their own learning, individually or in small groups, rather than just shown
examples of decomposition.
In introducing students to the idea of decomposing a problem, start with something very simple,
for example, how to clean your teeth. The goal is not to list the steps in brushing
teeth, but the components involved in solving the problem, for example:
• What tools and materials will you use to clean your teeth?
• What methods and actions will you use to clean your teeth, and for how long?
Links to several excellent existing activities that can be done in the classroom to reinforce
decomposition, analysis, synthesis and parallelization skills are provided along with this video.
A few are introduced here. These activities are meant to be challenging. When you finish
watching the video, please take the time to explore these links and choose some to try
out with your students, either individually or in small groups. Because every problem
is different, the more exposure to different ways of thinking about decomposition the better
students will become at putting the skill into practice. Also, remember that in many
cases there is no one right answer about how to decompose a problem. Be open and discuss
students’ train of thought.
Bee-Bot is a simple game for very young children to start to understand programming. Although
geared toward children younger than Middle and High School, Bee-Bot can be used as a
visual example to explain and practice decomposition. The goal in the Bee-Bot game is to move the
bee from its starting point to the flower by inputting instructions using the arrow
keys. The Bee-Bot only performs one instruction at a time, but can remember and perform a
series of many. As the student adds steps, they are listed across the top of the screen--a
decomposition of their larger set of instructions. When they click “go” the steps are highlighted
as they are performed, allowing students to see where they may have made a mistake. At
this point in the course this allow students to play with this game through trial and error.
Point out how it keeps track of steps and how this is an example of decomposition of
the problem. Students will likely find the first few levels easy and learn how the program
works and then, since the complexity of the route increases by level, they will be challenged
and likely find the decomposed steps to be very useful. We will return to Bee-Bot again
later in the training.
The activity Colour by Number: Image Representation provides opportunity for both synthesis and
analysis in decomposition. Students follow basic instructions to fill in squares on graph
paper that collectively form a recognizable image, an example of synthesis. Then, students
analyze a recognizable image into squares and create instructions for their classmates.
The process here is similar how pixels on a computer work.
Google: Divide and Conquer—Searching for the Token
Dividing and conquering is a different method of decomposition that can make a complex problem
much simpler. Strategic yes/no questions allow for up to half of the complexity of the problem
to be removed through process of elimination. In Searching for the Token students hide a
token of some sort in one of their pockets or desks. The instructor then asks yes/no
questions to determine who has the token. Instead of questions such as “does Alice
have the token?” or “is the person with the token wearing a blue shirt?” a much
more efficient decomposition method is to divide the room in half and ask if the token
is on the right side. In one question you will determine in which half of the room the
token is hiding. Your second question can divide the appropriate side of the room in
half again, and so on, until you find the token--it won’t take long! Students should
take turns practicing finding the token to get a good handle on the concept of divide
and conquer.
Another method to encourage efficient, strategic thinking in decomposition is to have students
“buy” a question using candy--the goal is to keep (and eat) as much candy as possible.
This is demonstrated in the activity Searching Algorithms and could be used during Searching
for the Token.
To reinforce the concept of divide and conquer decomposition students can explore the silly
“Santa’s Dirty Socks” eBook where savvy elves use divide and conquer to efficiently
locate Santa’s dirty socks amid a sea of packages on Christmas Eve.
When you have finished watching this video, don’t forget to complete the quick self-evaluation
to check your understanding.