Decomposition in computational thinking

Decomposition

The first pillar is decomposition. Decomposition is the process of taking a complex problem and breaking it into more manageable sub-problems. Although solving the complex problem as a whole may seem very difficult, the solution to each sub-problem maybe much simpler by putting together the solutions to the sub-problems. 

We can then arrive at a solution to the original, complex problem. You have probably experienced this when given the assignment of writing a paper. Rather than just sitting down at your keyboard and writing from start to finish, you probably start by developing an outline of the essay. 

Say, an introduction, a body containing sections developing each of several main ideas, and a conclusion. You then write each section in turn, starting with the main ideas and ending with the introduction and conclusion to create the paper.

As another example and one which we will use to develop the remaining pillars of computational thinking, this past spring I wanted to mulch my garden. Since I live on an acre of land, this seemed like an overwhelming task. Here, I'm showing you just the front of the house with two flower beds on each side of the front door, but there's also a patio and a big backyard. 

However, I soon realized that mulching the yard entailed a small number of sub-problems. Buying the mulch, whether it be in bulk or by the bag, and depositing it somewhere nearby, indicated in brown, here, and mulching each of eight discrete flower beds, three in front, one bed around a tree, one patio bed, two backyard beds, and one peony bed. The problem immediately became much more manageable. 

As another example, suppose you are asked to create a detailed zoomable map of the world. Something like Google Earth or at least to be part of a team to do this. Sounds pretty overwhelming. How would you go about decomposing the problem to make it more manageable? First, you would need to get the images. This would come from a variety of different sources.

For example, 2D images, from satellites shown here, as well as images from multiple 2D cameras aboard planes doing zigzags over locations of interest. This is called aerial photography. From this, you can create a 3D model. Having decided on the data sources, the images must be stitched together. Here, we show how three overlapping images are combined. For example, the aerial photography would use something called photogrammetry, to create a 3D model of the location. 

These images would then be superimposed onto a 3D globe. You would also create the functionality, which to provide over this data. For example, you might create various levels of detailed views to enable zooming in and zooming out over the map. Here, we see a 1X view of a portion of the map followed by a zoomed in image at 10X. You might also annotate the globe and or images with information about various locations. For example, a site name or address. Here, we see the University of Pennsylvania, UPenn, indicated on the map. In this lesson, we discussed the first pillar of computational thinking, decomposition. 

Decomposition takes a complex problem and breaks it into more manageable sub-problems. By solving each potentially simpler sub-problem, we can put the solutions together to arrive at a solution to the original complex problem. You probably already do this in solving everyday problems like writing a paper by breaking it into sections, that can be individually written and put together. 

Planning a trip by breaking it into different segments and planning each segment individually. Or mulching your garden by breaking it into separate components. But it is also important for solving large computational problems like mapping the earth. In decomposition, sometimes even a smaller sub-problems can seem overwhelming. For example, collecting the image data in the Google Earth problem.

 You can therefore consider a sub-problem as another complex problem and further decompose. In the Google Earth example, you could decompose the sub-problem of collecting the image data by first focusing on how to collect the satellite data then focusing on the aerial photography, and then the way in which the 3D model is to be constructed. Furthermore, you could decompose the world into smaller areas and start about understanding how you would do this for your street, your block, your city, state, country, and then to the world. We'll talk more about this in the next pillar, pattern recognition.