Most of the thought about how a task should be broken down is done in the design stage. Regardless of the complexity of a design, implementation should remain a fairly straightforward translation process.
Abstraction is the omission of detail for the sake of looking at the big picture. For example, an abstract is an overview of a book or paper that summarizes the whole story with very little detail.
Abstraction can have many levels. The highest level of abstraction covers the whole picture, and has the least detail.
When we go to lower levels of abstraction, we generally focus on only part of the picture. For example, we may have a more detailed abstract for each chapter of a book, and even more detailed abstracts for each section.
A table of contents is another form of abstraction, as is a review article, or an outline.
A top-down design is a multilevel view of something showing a highly abstract level, with very little concern for detail, as well as additional levels with increasing detail for smaller portions of the problem.
Stepwise refinement is the process of creating a top-down design, breaking down a large design into layers of increasing detail.
Consider a house as A simple example. At the most abstract level, as house can be viewed as a set of rooms. At the next level, each room consists of walls, a ceiling, and a floor. A floor typically consists of joists, subflooring, and a floor covering such as carpet or tile.
More detailed views of the house focus on smaller portions of the house, omitting more and more other components. This is necessary
This is the approach we use to deal with anything that is too large and complex to comprehend, whether it be a house, a field of study, or an engineering problem. We choose a balance between breadth and detail, taking more of one and less of the other, depending on the needs of the moment.
The most intuitive way to visualize a top-down design is using a Tree structure view:
The problem with such a tree view is that it generally becomes too wide to represent on paper after 2 or three levels of refinement. The same structure can be rotated 90 degrees and represented as text using indentation to denote the level in the tree. This structure is more convenient to represent in documents, since it mostly grows vertically.
Earth Africa Asia Antarctica Australia N. America Canada Mexico USA S. America Europe
Top-down designs can be used to represent anything that can be broken down. A design can reveal the organization of physical objects to as much detail as we want, even down to subatomic particles.
Top-down designs can also show the structure of ideas and processes, which is how they are generally used in computer science. In this case, the tree or text diagram indicates a sequence of steps. On the tree, the sequence goes from left to right, and in the text it goes from the top down.
Example 20.1. Ordering Pizza
Order pizza Decide on toppings Talk to pizza eaters Talk to mom Talk to dad Talk to brother Wave at brother so he takes off headphones Talk to sister Wave at sister so she gets off the phone Write down toppings Decide on a pizza place Talk to pizza eaters Same details as above Decide on pick-up or delivery Talk to pizza eaters Same details as above Get phone number Check Internet Check phone book Call pizza place Dial number Wait for answer Talk to pizza guy
One thing you may notice in the pizza example is that some of the modules we created when breaking down the process are used repeatedly. This is another benefit of breaking down a problem into layers and modules. In addition to simply making the problem manageable, if it turns out that some modules can be reused, the next step of implementing the solution is easier since you only have to implement a module once no matter how many times it is used.
Identifying and separating out modules that can be used in multiple places is called factoring the design (or the code). It is akin to reducing an expression such as xy + xz to x(y + z). It's the same expression, but the latter only represents x once. By factoring a program design, you ensure that each module of code will only be implemented once, which results in a smaller program.
Now let's consider a problem for which we can easily implement a solution on a computer.
Example 20.2. Sorting
Sort list of numbers Get list Get number If not end of list, repeat Sort list Find smallest number in list Assume first is smallest Compare to next number If next is smaller, remember location Repeat compare until end of list Swap with first Copy first to temporary location Copy second to first Copy temporary location to second Repeat for remaining numbers Repeat until only one number remains Output sorted list Output number If not end of list, repeat
First level of refinement:
Sort list of numbers Get list Sort list Output sorted list
Second level of refinement:
Get list Get number Repeat until end of list
Sort list Find smallest Swap with first Repeat previous two steps for remaining numbers Repeat previous three steps until only one number remains
Output list Output a number Repeat until end of list