Skip to Content

Computational Thinking: Decompostion

Posted on 5 mins read

This page builds on our introduction to computational thinking.

Recall our five foundations of computational thinking:

  1. Abstraction
  2. Decomposition
  3. Pattern Recognition
  4. Data Representation
  5. Algorithms

Decomposition

In computer science decomposition is the act of breaking down a large, complex thing into smaller, more manageable, and understandable parts. Wikipedia:Decomposition says “In computer science, decomposition is the process of identifying and organising a complex system into smaller components or layers of abstraction.”

The Wikipedia definition says system, and it is true that when designing our software we need to use decomposition, but it also applies to problems and concepts. When we are faced with anything that is overwhelming to think about, we must use decomposition to deal with sub-parts of that thing.

Decomposition Creates A Lexicon

Why does it often seem that experts of some subject are speaking a foreign language? Because in some sense, they are. Medical doctors have their own terminology, lawyers have there own, and so on. Here’s a list of over 1000 accounting terms, and a UPenn college course has a topic called The Basic Language of Accounting.

Every knowledge domain has its own terminology, or lexicon. One definition in Merriam-Webster of lexicon is 2a: “the vocabulary of … a subject” (MW:lexicon).

When we think about a complex concept (problem, system), we need words to organize our thoughts. So we create, or choose, a lexicon.

So, as with abstraction, decomposition is another place where naming is critical. When we break a complex thing into subparts, now we need names for those subparts. Decomposition and abstraction often work together, because when we decompose something now we need to think about those subparts, often using abstractions. And then we need to name that part. When people started imagining the modern computer GUI, they decomposed the interaction and came up with many new words: window, icon, mouse, pointer (those four are known as WIMP), drag, drop, selection, cut, paste, etc.

Naming decomposed subparts, and abstractions, creates a lexicon for our concepts.

Top Down and Bottom Up, but Probably Both!

There are two ways to apply decomposition: top down and bottom up. Usually we end up doing some of both. In top down thinking, we start with the whole, break it into parts, and then if needed break those down further, until we have pieces that we can tackle. In bottom up thinking, we don’t yet have a good idea of how all the parts will fit together, but we start thinking about the smallest pieces that we know will be part of the whole thing.

In top-down decomposition, for an online food-ordering app, we can think of some subparts such as: menu management and presentation; order creation and checkout (shopping cart?); and customer management. There is not a lot of new language here, but shopping cart has become a term and concept that is used heavily in customer-facing online systems.

In bottom-up thinking, we may want to build a platformer game but have never programmed anything but text programs. We may not be able to think about all the parts from the top-down perspective, but we know there is some capabilities we’ll need to learn, such as recognizing key presses and releases separately, rather than just the character that the key represents.

Decomposition by Layering

The Wikipedia definition above said that decomposition is “organising a complex system into smaller components or layers of abstraction.” Up until now we ignored that last part. But layers of abstraction is a wonderful and proven method for dealing with complexity! In fact, I often say “if you don’t know where to start in designing your system, try to layer it!”

This is different than the generalization and specialization ideas of abstraction, which might in some way also look like “layers”.

Layered decomposition involves organizing the various parts of your system into layers, where each layer uses the layer below it and then adds its own capability. So if it is decomposition, why do we call it layers of abstraction? Because if we did it well, each layer can be named and then understood as a coherent abstraction of part of our system.

One famous place where layers of abstraction was applied is in our design and creation of the Internet. The lowest layer represents the fundamental data transmission technology, and then each layer builds upon the layers below to create a new, more capabable, data transmission concept, until at the top we have software applications talking to each other over the global Internet.

Layer Capabilities Technology
Application formatted data app-to-app HTTP, SSH, NFS
Transport reliable data socket-to-socket TCP
Network unreliable data device-to-device IP
Data Link unreliable data locally (1 hop) Ethernet, WiFi
Physical information signal send & receive twisted pair, fiber, radio

Layers are usually drawn (stacked) vertically, but sometimes there are drawn as concentric circles, with the innermost being the bottom layer; this is sometimes called an onion architecture (example).

Exercise Questions

To work on using using decomposition, consider the following exercise questions. You can do these over and over with many different ideas.

  1. Select either a) a problem you want to solve with computers; or b) a software system you want to build. You may have trouble separating these two, so stay aware of the language you use. For (a), say something like “I want to support people in activity A, B, C”; for (b), say something like “I want to create software that does X, Y, and Z.” But X, Y, and Z will probably sound a lot like A, B, and C – but the perspective should be different (people vs. system).

  2. Top-Down: Try to think about how that whole problem or system can be broken into sub-parts. The key here is that in a top-down, nothing should be missing at the next level – the entire system should somehow fit into those sub-parts that you chose.

  3. Bottom-Up: Try to think about fundamental (or basic) parts that your problem or system has. Unlike top-down, you do not have to capture every aspect of your system; in bottom-up thinking, you start by just thinking about basic pieces one at a time.

  4. Layering: Try to think about whether or not you can separate your problem or system into conceptual layers, where the lowest or core layer is fundamental components and operations, and more complex layers build on top of that, layer by layer.