TOP DOWN ANALYSIS REVIEW

1. OVERVIEW

• Top down analysis is a problem solving mechanism whereby a given problem is successively broken down into smaller and smaller sub-problems or operations until a set of easily solvable (by computer) sub-problems is arrived at.
• Each level is numbered commencing with the top (first) level followed by the second level and so on.
• Each level marks a different level of abstraction (degree of detail) with the top level exhibiting the greatest degree of abstraction.
• Using the top-down approach It is possible to achieve a very detailed breakdown, however, it should be remembered that our aim is to identify easily solvable sub-problems. Our aim is not to use the technique to identify a detailed design or a set of implementation statements.

Note that where a top down approach is used to identify a detailed design this is referred to as top down design. Where the technique is used to identify program statements this is referred to as step wise refinement. The latter was first proposed by Niklaus Wirth (the inventor of the imperative programming language PASCAL) in the early 1970's (Wirth 1971). The disadvantages of using a top down approach for detailed design, or the identification of individual implementation statements, may be listed as follows:

1. The designer ends up with very large tree structures.
2. There is no clear identification of the flow of control.
3. It is difficult to represent constructs such as selection, repetition and routine invocation.

2. WHAT IS AN "EASILY SOLVABLE SUB-PROBLEM"

There is no precise definition as to what constitutes an "easily solvable sub-problem". To a degree this is of course dependent on the experience and background of the designer/programmer. However, a useful guideline is that:

An easily solvable sub-problem is one that can be addressed by a single program procedure or function.

This only gets us part of the way because we now need to have some idea as to the type of problems that can be addressed by a single procedure or function. Again there are no definite rules here, but we should take note of the following guidelines:

1. A procedure (function) should normally only be used to address a single task.
2. A procedure (function) should be such that it can be viewed, in its entirety, in a text editor window without requiring scrolling etc.
3. Some practitioners maintain that a procedure (function) should not be longer than 15 to 20 lines of code.
4. We should bare in mind that we might want to reuse procedures (functions), therefore we might wish to "wrap up" certain tasks in the form of a single procedure/function for this purpose.

Often, to identify a procedure sized problem, it is necessary to go one level further in the top-down analysis. There is nothing wrong with this.

3. REPRESENTATION

The simplest method of describing a top-down analysis is to use a tree structure such as that shown below. In such a structure each branch in the tree originates at a node. The top most node (i.e. the first or top level in the analysis) is sometimes referred to as the root node, and the bottom most nodes are sometimes referred to as the leaf nodes. Each node represents an abstraction in the problem's decomposition with the leaf nodes representing the lowest level of abstraction. There can only be one root node (the highest level of abstraction).

We also talk of nodes as being parents, children or siblings of other nodes:

• A parent node is one that has other nodes descending from it - we say that a node is the parent of some other node.
• In the same way a child node is one that descends from a parent node.
• The root node can only be a parent node.
• Leaf nodes can only be child nodes.
• Intermediate nodes can be both parent or child nodes depending on the desired perspective.
• All nodes in the tree are children of the root node. Conversely the root node is a parent of all other nodes in the tree.
• Sibling nodes are two or more nodes at the same level which are descended from the same parent.
• The depth (or height) of a tree refers to the number of levels in the tree.
• The width of a tree refers to the maximum number of nodes at any one level.

With respect to tree structures used to represent top-down problem analysis the following should be noted:

1. We can have only one root node.
2. Branches need not all be of the same depth.
3. The greatest width need not necessarily occur at the lowest level.

Given a particularly complicated problem it may be appropriate to describe the analysis using a number of tree structures using connectors to indicate where parts of the overall tree structure "meet up".

4. REFINEMENT

There is nothing wrong with doing a number of top-down analyses, where each new break down is a more refined version of the previous analysis. A typical situation where we might wish to redefine our hierarchy is where we discover that some component of a problem's decomposition appears more than once (i.e. in separate branches) in the tree. In this case we should move the component higher up the tree so that it becomes a parent node of all the sub-problem nodes where it is required (although we cannot move a node so far up the tree that it becomes a second root node). The reason for this is that the top down break down should also reflect:

1. The intended implementation sequence of our eventual design.
2. And consequently, at least in the case of Ada, the nature of the required nesting.

Note: a problem may be so large that, to become manageable, its solution may require several programs. For example each of the level 2 components in a top down decomposition might be addressed by individual programs with one acting as the "main" program (more on this later).

5. TOP DOWN ANALYSIS AND IMPLEMENTATION

• Each node in a top-down analysis tree represents an operation which can be addressed by a procedure or function, even if it is only a calling procedure that is used to integrate a number of lower level procedures (functions).
• In some cases the identified operations may be sufficiently simple that a number of operations can be combined in a single procedure/function.
• The analysis/high level design is translated into a detailed design (Using Nassi-Schneiderman charts in our case) and then implemented in a similar manner to which it is derived, i.e. commencing with the top-level.
• During implementation, where necessary, operations immediately below the current level may be represented by "stubs" (rudimentary implementations).
• On completion of a level the program in its present state should be tested using appropriate test cases, before we proceed to encode the next level..IP \(bu To support this testing include in the partial implementation:
  • Output statements indicating when a procedure/function has been accessed.
  • "Echo" inputs back to the screen.
  • Output values of parameters for procedures/functions from "within" the procedure/function.
  • Output constants where they are required
  • Use dummy values as the temporary return values for partially encoded functions.
  • Output dummy values returned from partially encoded functions.

F = (9/5 x C) + 32

C = (F - 32) x 5/9

Note also that we have written a similar program to convert Centigrade temperatures to Fahrenheit. We can reuse this code (code reuse is an important economic issue in software engineering).

6.2 Design

A top-down analysis of the proposed problem is given below.

With respect to the above we can identify three procedures:

1. TEMP_CONVERT (top level procedure): Output menu, input and check menu selection, and calls to appropriate procedure (CENT_2_FAHR or FAHR_2_CENT).

   NAME	DESCRIPTION	TYPE	RANGE
   MENU_ITEM	Global input variable	CHARACTER	Default

2. CENT_2_FAHR (level 2 procedure): Convert from Centigrade to Fahrenheit.

   NAME	DESCRIPTION	TYPE	RANGE
   CENT_TEMP	Local input variable	CENTIGRADE	-50.0..100.0 TEMPERATURE	Local output variable	FLOAT	Default

3. FAHR_2_CENT (level 2 procedure): Convert from Fahrenheit to Centigrade.

   NAME	DESCRIPTION	TYPE	RANGE
   FAHR_TEMP	Local input variable	FAHRENHEIT	-58.0..212.0 TEMPERATURE	Local output variable	FLOAT	Default

The above includes the programmer defined types CENTIGRADE and FAHRENHEIT which will be expressed as subtypes of the type FLOAT. A complete Nassi-Schneiderman design for the above is given below, followed by a flow chart.

6.3. Implementation

Commence the implementation at the top-level of the analysis using stubs for lower level procedures:

-- TEMPERATURE CONVERSION
-- 15 August 1997
-- Frans Coenen
-- Dept Computer Science, University of Liverpool

with TEXT_IO;
use TEXT_IO;

procedure TEMP_CONVERT is
        package FLOAT_INOUT is new FLOAT_IO(FLOAT);
        use FLOAT_INOUT;
        MENU_ITEM: CHARACTER;

        ------------------------------------------------------------
          -- CENTIGRADE TO FAHRENHEIT CONVERSION
        procedure CENT_2_FAHR is
        begin
                PUT_LINE("CENT_2_FAHR procedure");
        end CENT_2_FAHR;
        ------------------------------------------------------------
        -- FAHRENHEIT TO CENTIGRADE CONVERSION
        procedure FAHR_2_CENT is
        begin
                PUT_LINE("FAHR_2_CENT procedure");
        end FAHR_2_CENT;
        ------------------------------------------------------------

-- TOP LEVEL
begin
-- Output Menu
        PUT_LINE("MENU OPTIONS");
        PUT_LINE("C - Centigrade to Fahrenheit conversion");
        PUT_LINE("F - Fahrenheit to Centigrade conversion");
        GET(MENU_ITEM);
-- Check menu input
        if (MENU_ITEM = 'C' OR MENU_ITEM = 'c') then
                CENT_2_FAHR;
        else
                if (MENU_ITEM = 'F' OR MENU_ITEM = 'f') then
                        FAHR_2_CENT;
                else
                        PUT("Invalid menu selection: ");
                        PUT(MENU_ITEM);
                        NEW_LINE;
                end if;
        end if;
end TEMP_CONVERT;

Notes:

1. The code includes a nested "if-else". An alternative encoding might make use if an if-elsif-else format. For example:

   -- Check menu input
           if (MENU_ITEM = 'C' OR MENU_ITEM = 'c') then
                   CENT_2_FAHR;
           elsif (MENU_ITEM = 'F' OR MENU_ITEM = 'f') then
                   FAHR_2_CENT;
           else
                   PUT("Invalid menu selection: ");
                   PUT(MENU_ITEM);
                   NEW_LINE;
           end if;
   

2. The conditional part of the "if-else" statements includes a logical or.
3. A menu is a simple interface which reduces the risk of input error on behalf of the user. A menu system should include an error recovery mechanism in the event of an inaccurate menu selection. In the above case an appropriate error message is produced.

On completion of this top level implementation we should test its operation. In this case we should run test cases for each of the possible menu inputs including an invalid input. A suitable set of test cases is given in the table below.

Once testing of this level is complete we can go on to implement the following level:

-- TEMPERATURE CONVERSION
-- 15 August 1997
-- Frans Coenen
-- Dept Computer Science, University of Liverpool

with TEXT_IO;
use TEXT_IO;

procedure TEMP_CONVERT is
        package FLOAT_INOUT is new FLOAT_IO(FLOAT);
        use FLOAT_INOUT;
        MENU_ITEM: CHARACTER;

        ------------------------------------------------------------
        -- CENTIGRADE TO FAHRENHEIT CONVERSION
        procedure CENT_2_FAHR is
                subtype CENTIGRADE is FLOAT range -50.0..100.0;
                CENT_TEMP   : CENTIGRADE;
                TEMPERATURE : FLOAT;
        begin
        -- Input Centigrade value
                PUT_LINE("Input temperature in degrees Centigrade (float): ");
                GET(CENT_TEMP);
        -- Conversion
                TEMPERATURE := CENT_TEMP * (9.0/5.0) + 32.0;
        -- Output Fahrenheit value
                PUT("The equivalent in degrees Fahrenheit is: ");
                PUT(TEMPERATURE, FORE=>3, AFT=>1, EXP=>0);
                NEW_LINE;
        end CENT_2_FAHR;
        ------------------------------------------------------------
        -- FAHRENHEIT TO CENTIGRADE CONVERSION
        procedure FAHR_2_CENT is
                subtype FAHRENHEIT is FLOAT range -58.0..212.0;
                FAHR_TEMP   : FAHRENHEIT;
                TEMPERATURE : FLOAT;

        begin
        -- Input Fahrenheit value
                PUT_LINE("Input temperature in degrees Fahrenheit (float): ");
                GET(FAHR_TEMP);
        -- Conversion
                TEMPERATURE := (FAHR_TEMP-32.0) * (5.0/9.0);
        -- Output Fahrenheit value
                PUT("The equivalent in degrees Centigrade is: ");
                PUT(TEMPERATURE, FORE=>3, AFT=>1, EXP=>0);
                NEW_LINE;
        end FAHR_2_CENT;
        ------------------------------------------------------------

-- TOP LEVEL
begin
-- Output Menu
        PUT_LINE("MENU OPTIONS");
        PUT_LINE("C - Centigrade to Fahrenheit conversion");
        PUT_LINE("F - Fahrenheit to Centigrade conversion");
        GET(MENU_ITEM);
-- Check menu input
        if (MENU_ITEM = 'C' OR MENU_ITEM = 'c') then
                CENT_2_FAHR;
        else
                if (MENU_ITEM = 'F' OR MENU_ITEM = 'f') then
                        FAHR_2_CENT;
                else
                        PUT("Invalid menu selection: ");
                        PUT(MENU_ITEM);
                        NEW_LINE;
                end if;
        end if;
end TEMP_CONVERT;

6.4. Testing

6.4.1. Black box testing

BVA testing: Do a BVA analysis for ranged values in two conversion procedures. A suitable set of BVA test cases is presented in the table to the right.

Limit testing: We should also derive a suitable set of test cases to exercise the limits of the input ^ values. A suitable set of test cases for this purpose is given in the table presented to the right.

Arithmetic testing: Arithmetic testing requires negative, zero and positive sample values. We have already defined test cases with negative and positive values at the limits, however a "mid range" positive and negative sample value would also be appropriate (as well as zero sample values). A suitable set of test cases is given in the table to the right.

6.4.2. White box testing

Path testing We should test each path through the program as indicated by the flow chart presented above. From this diagram we can identify three paths. Note that where a path is dictated by a compound condition represented by a "logical or" we should test both possible conditions associated with the "or" operator. A suitable set of test cases is presented in the table to the right. Note that the first four test cases are copies of black box cases defined earlier and thus need not be run again.

6.4.3. Data validation testing

This should also be done.

Example Problem Temperature Conversion Report.

7. REFERENCES

1. Wirth, N. (1971). Program Development by Stepwise Refinement. CACM. Vol. 14, No 2. pp221-227.

Created and maintained by Frans Coenen. Last updated 11 October 1999