We do top-down design all the time in real life. For example, when we write a paper in an English writing class, we first identify the major sections of the paper (like introduction, background, and summary). Then, we write the content for each section. Sometimes, we even need to outline each section with subsections first.
Maps are also perfect examples of top-down design. If you visit any mapping website, a map shows different types of details depending on the “zoom” level. A map for the globe, for example, is unlikely to identify streets. Instead, it probably identifies nations and national capitals. A map for a country, on the other hand, may include states (provinces), major cities and state capitals. We may also see major highways, but probably not intrastate roads. A regional map will identify smaller towns and cities, as well as intrastate roads. Even at this level, local streets cannot be displayed.
Most books are also organized in parts, and then chapters within a part. This is especially the case for college-level textbooks.
Documents are usually organized in an office or even at home. A file cabinet contains drawers, a drawer contains hanging folders, a hanging folder contains regular folders, and a regular folder contains stapled documents.
Essentially, the term “top-down” means a hierarchical structure of details. At the top level, very little detail is revealed. At the bottom level, very fine detail is displayed. Between the top and the bottom, however, are levels that display intermediate detail.
Can you find more real-life examples of top-down hierarchies? In the computer context, how files and folders are organized is also a prime example of a top-down hierarchy.
Why do we use top-down design? The answer is quite simple: we cannot manage too many things at the same time.
Imagine you are managing photographs. Due to the “no-cost” nature of digital cameras, many people shoot thousands of pictures per year. If all pictures are thrown into the same folder for a few years, the folder will end up with so many pictures that it is impossible to find a particular one.
That’s why we all have different ways to organize digital pictures.
There are some special considerations that are specific to algorithms. One primary concern is how much can we fit on paper or the computer screen without flipping pages.
Even with correct indentation to help us identify the beginning and ending of blocks, if a construct spans across physical pages, it will still be difficult to match the beginning with the end of a construct. Based on this limitation, an algorithm should have no more than 40 lines or so of code. The 40-line limit is based on what most people feel comfortable with respect to font size and display size.
A 40-line algorithm can be quite complex for beginning programmers or even intermediate programmers. In reality, an algorithm should not have more than 20 lines of code if it is intended for beginning programmers.
Not all algorithms can be specified in 20 lines or less. As a result, we need to “abstract” out chunks of code with “abstract operations”. An “abstract operation” simply means “we don’t know/express how to do this exactly”. An abstract operation is one that is not composed of the basic types of statements (assignment, sequence, conditional statement or loops). This way, we can make algorithms appear shorter by hiding details.
Let us consider an example to find prime factors of an integer. Let us assume that is an integer that we want to factor.
Let’s factor a number by hand first, just so that we understand the process. Let’s say we want to find all the prime factors of 20.
First, we see that , and 2 is a prime number.
Then, we see that , and 2 is a prime number.
Lastly, we see that , and 5 is a prime number.
At this point, the number is reduced to 1, which means there is no more factor.
Let us be “lazy” and make some assumptions. For example, I’ll assume, for now, that there is a way to find a prime factor of . Given this ability, I can write the logic as in algorithm 3.3.2.
As an exercise, assume and trace this algorithm.
As it turns out, most programming languages do not have a method to find a prime factor of a given integer . Oh, well. That means we need to specify an algorithm just to do this. Again, it is best to try to do this by hand first.
Let us assume , and we are to find a prime factor of it.
Although not necessarily the most efficient method, one way is to try out all integer greater than or equal to 2 until we find one that is a factor. This requires the explanation of the “mod” operator. is the remainder of . In other words, , and etc.
Given this operator, we can now explain how we can find a prime factor of 15:
Now we are ready to express the logic of finding a factor in algorithm 3.3.4.
Now that we have separate pieces of the algorithm, we can choose whether to leave algorithms 3.3.2 and 3.3.4 just the way they are. If you want to see the entire algorithm, we can integrate the two. The integration is nothing more than filling in the statement “find a prime factor of ” in algorithm 3.3.2 with the entire algorithm 3.3.4. The result of integration is algorithm 3.3.5.
The integrated version shows all the details of how to factor a number. However, it is more difficult to read because of the distracting detail of finding a factor.
The top-down design starts with my assumption that “someone else has already figured out how to find a factor of an integer ”. This “laziness” actually works in my favor because it permits me to focus on the main logic of factoring a number. In other words, the “top” part of top-down is algorithm 3.3.2.
Once I traced algorithm 3.3.2, and am convinced that it works, I shift my attention to the assumed operation. Only at this time did I consider the logic of finding a prime factor of an integer . Note that when I tried to figure out the logic of finding a prime factor of an integer, I don’t need to worry about the logic of factoring a number anymore.
Although top-down design is taught in every algorithm design class and throughout all computer courses, it is not the only way to write programs. It is nearly impossible to apply the top-down method perfectly in the real world.
In other words, it is nearly impossible to use the correct abstract operations to make the top level algorithm “just right” when you are writing an algorithm (or a program). In real life, programmers rely on a few techniques to keep program code manageable.
Whenever it is possible, convenient and make sense, use the top-down method. “Think in big steps” is one way to think about it.
Seldom mentioned is the technique called bottom-up. This technique is very useful for more experience programmers. This method is the inverse of top-down design, because small building blocks are first created, then larger blocks are created from smaller blocks. The process is repeated until a program accomplishes what it needs to do.
The reason why the bottom-up technique is used only by more experienced programmers is because beginners cannot guess what components are needed first. More experienced programmers can look at the overall objectives of a program, and quickly determine a set of operations that must be implemented and utilized.
More often than not, even with experienced programmers, an algorithm grows and grows until it becomes “messy” and too lengthy. At this point, we can “abstract” portions of the algorithm as an abstract operation, and thus hide the details in the definition of the abstract operation.
The key to abstraction is to identify a block of code (within an algorithm) that is somewhat self contained and related. This process, once again, requires some experience. There are methods to evaluate how self contained is a block of code based on the usage of variables. We will revisit this topic in the module that discusses subroutines.
As an example, sometimes we come up with algorithm 3.3.5 first, then decide that it is too much to read. Then, we see a self contained block of code as algorithm 3.3.4, and extract that out of the main algorithm. Once we extract the self contained block of code, we replace it with a one sentence description “find a prime factor of ”. We also end up with a second algorithm as algorithm 3.3.4. The main algorithm, then, becomes algorithm 3.3.2, which is considerably easier to read than algorithm 3.3.5.