Wikijunior:Programming for Kids/Designing Your Solution

From Wikibooks, open books for an open world
Jump to navigation Jump to search
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[edit | edit source]

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:

size=200px

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?

size=200px

Note that this problem involves division into smaller subproblems.

The Modular Approach[edit | edit source]

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...[edit | edit source]

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!