Wikijunior:Programming for Kids/Designing Your Solution

Wikijunior:Programming for Kids
Knowing Your Problem	Designing Your Solution	Top-Down or Bottom-Up?

Once we've figured out our problem, we need to design a way to solve our problem. At this stage, we do not write any code yet. We are only drawing up a framework which we will follow during the algorithm design stage.

Divide and Conquer

Divide and conquer (D&C) comes from the Latin saying divide et impera. It refers to the breaking up of a large problem into smaller subproblems. The subproblems can be further divided into smaller subsubproblems, which become subsubsubproblems and, well, you get the idea. Divide and conquer is a systematic way to obtain a blueprint for your solution. After each subproblem has been tackled, we merge them together to form the 'big picture'.

Divide and conquer can be applied to both real-life problems and programming problems. We will look at one notable application, array sorting, in the next section. For now, let's try something simpler. Let's say you want to measure the area of a stadium. There is no formula for calculating the stadium's size directly, so let's try doing it this way:

This diagram is a structure diagram. A structured diagram is a way of mapping the structure of our solution. (Surprise, surprise!)

Let's try a more difficult problem. Suppose you have a squared flower bed and a path around it. You need to pave the path, and want to calculate the total cost of this project. How will you do that?

Note that this problem involves division into smaller subproblems.

The Modular Approach

By using D&C with our problem, we are taking the modular approach to programming. In the diagrams above, each block represents a module. In the second diagram, the subsubproblems can be said to be submodules. Dividing a problem into different modules is a common programming practice.

Data and information flow in the structured diagram in some way. For example, in the flowerbed example, the 'Find the difference between the two areas' module needs to know the data in the 'Find the area of the flowerbed' and the 'Find the area of the path plus the flowerbed' modules. To represent this clearly, each module has a module specification which clearly documents the inputs, outputs and processes of the module. We can also use an I-P-O chart for this purpose. Let's look at the module specifications for our flowerbed project. (Don't worry if you don't understand everything completely; we'll look at them soon.)

Module: 'Find the total cost of the project'
Inputs	Processes	Outputs
Width of the flowerbed Length of the flowerbed Width of the whole area Length of the whole area Cost per unit	Prompt the user to input the dimensions of the flowerbed, the dimensions of the whole area and the cost per unit Get the dimensions of the flowerbed, the dimensions of the cost per unit Validate the input data Find the area of the path Multiply the area and the per-unit path Output the total cost of the project to the screen	The total cost of the project

Module: 'Find the area of the path'
Inputs	Processes	Outputs
Width of the flowerbed Length of the flowerbed Width of the whole area Length of the whole area	Read the dimensions of the flowerbed, the dimensions of the whole area Find the area of the flowerbed Find the area of the path plus the area of the flowerbed Find the difference between the two areas Output the area of the path	The area of the flowerbed

Module: 'Multiply the area with the per-unit cost'
Inputs	Processes	Outputs
Area of the path Per-unit cost	Read the area of the path and the per-unit cost Convert the units of the path and the cost if needed Multiply the area of the path with the per-unit cost Output the cost of the project	The total cost of the project

Module: 'Find the area of the flowerbed'
Inputs	Processes	Outputs
Length of the flowerbed Width of the flowerbed	Read the dimensions of the flowerbed Multiply the length and width of the path together Output the area of the flowerbed	The area of the flowerbed

Module: 'Find the area of the path plus the flowerbed'
Inputs	Processes	Outputs
Length of the whole area Width of the flowerbed	Read the dimensions of the whole area Multiply the length and width of the path together Output the whole area	The area of the flowerbed

Module: 'Find the difference between the two areas'
Inputs	Processes	Outputs
Area of the flowerbed The whole area	Read the two areas Find the difference between the two areas Output the area of the path	The area of the path

The modular approach has many advantages.

The modular approach allows us to reuse modules.

It allows more flexibility in programming. The modular approach facilitates code reuse. Sometimes, one module may be used more than once in a program. For example, in a geometry program, it would be desirable to have one single module for Pythagoras' theorem which can be used anytime in a program. This saves us from having to copy-and-paste (and probably make a mistake in the process). Moreover, a change in one module may not have significant changes on the whole program.

The modular approach encourages teamwork.

It is easier to tackle one small problem at a time. It is easier to see the structure of a program if we divide it into various modules. A very large piece of code would be hard to read and debug. Dividing it into smaller parts helps identify and rectify mistakes.
It encourages collaboration between programmers. A team of programmers can divide up the work by assigning certain modules to each person. It also facilitates specialisation: for example, one programmer who is familiar with the XML DOM may choose to work on XML, while another who is familiar with SQL may choose to work on the databases and PHP. It also facilitates management and control.

The modular approach also has disadvantages. For example, it may not be clear to each team member how the program works as a whole. As such, they may be ignorant of the full picture. This may cause problems with the linkage between different modules. It also requires extensive and in-depth documentation for other programmers, which increases the time-frame and costs.

Hang on...

We've designed the framework of the program with the modular approach, but how should we start? Should we work on the smallest programs first, then work our way to the top? or should we deal with the top parts first, then work our way to the bottom? Read the next chapter to find out!