Problem decomposition is one of the elementary problem-solving techniques.

**Decomposition**

Problem decomposition is one of
the elementary problem-solving techniques. It involves breaking down a problem
into smaller and more manageable problems, and combining the solutions of the
smaller problems to solve the original problem. Often, problems have structure.
We can exploit the structure of the problem and break it into smaller problems.
Then, the smaller problems can be further broken until they become sufficiently
small to be solved by other simpler means. Their solutions are then combined
together to construct a solution to the original problem.

**1. Refinement**

After decomposing a problem into
smaller subproblems, the next step is either to refine the subproblem or to
abstract the subproblem.

1.
Each
subproblem can be expanded into more detailed steps. Each step can be further
expanded to still finer steps, and so on. This is known as refinement.

2.
We can
also abstract the subproblem. We specify each subproblem by its input property
and the input-output relation. While solving the main problem, we only need to
know the specification of the subproblems. We do not need to know how the
subproblems are solved.

Example 7.6. Consider a school
goer's action in the morning. The action can be written as

1. Get ready for school

We can decompose this action into
smaller, more manageable action steps which she takes in sequence:

1. Eat breakfast

2. Put on clothes

3. Leave home

We have refined one action into a
detailed sequence of actions. However, each of these actions can be expanded
into a sequence of actions at a more detailed level, and this expansion can be
repeated. The action "Eat breakfast" can be expanded as

**1. -- Eat breakfast**

2. Eat idlis

3. Eat eggs

4. Eat bananas

The action "Put on
clothes" can be expanded as

**1. -- Put on clothes**

2. Put on blue dress

3. Put on socks and shoes

4
Wear ID card

and "Leave home"
expanded as

**1.** **-- Leave home**

2. Take the bicycle out

3
Ride the bicycle away

Thus, the entire action of
"Get ready for school" has been refined as

**1-- Eat breakfast**

2Eat idlis

3 Eat eggs

4. Eat bananas

5

**6** **-- Put on
clothes**

7 Put on blue dress

8 Put on socks and shoes

9
Wear ID card

10

**11 -- Leave home**

12 Take the bicycle out

13 Ride the bicycle away

Refinement is not always a
sequence of actions. What the student does may depend upon the environment. How
she eats breakfast depends upon how hungry she is and what is on the table;
what clothes she puts on depends upon the day of the week. We can refine the
behaviour which depends on environment, using conditional and iterative
statements.

1 -- Eat
breakfast

2 if hungry and idlis on the table

3 Eat idlis

4
if hungry and eggs on the table

5 Eat eggs

6
if hungry and bananas on the table

7 Eat bananas

8 -- Put on clothes

10 if Wednesday

11 Put on blue dress

12 else

13 Put on white dress

14 Put on socks and shoes

15 Wear the ID card

16

17 -- Leave home

18 Take the bicycle out

19 Ride the bicycle away

The action "Eat idlis"
can be further refined as an iterative action:

1 -- Eat idlis

2 Put idlis on the plate

3 Add chutney

4 while idlis in plate

5 Eat a bite of idli

How "Get ready for
school" is refined in successive levels is illustrated in Figure 7.8.

Note that the flowchart does not
show the hierarchical structure of refinement.

**2. Functions**

After an algorithmic problem is
decomposed into subproblems, we can abstract the subproblems as functions. A
function is like a sub-algorithm. Similar to an algorithm, a function is
specified by the input property, and the desired input-output relation.

To use a function in the main
algorithm, the user need to know only the specification of the function — the
function name, the input property, and the input-output relation. The user must
ensure that the inputs passed to the function will satisfy the specified
property and can assume that the outputs from the function satisfy the
input-output relation. Thus, users of the function need only to know what the
function does, and not how it is done by the function. The function can be used
a a "black box" in solving other problems.

Ultimately, someone implements the
function using an algorithm. However, users of the function need not know about
the algorithm used to implement the function. It is hidden from the users.
There is no need for the users to know how the function is implemented in order
to use it.

An algorithm used to implement a
function may maintain its own variables. These variables are local to the
function in the sense that they are not visible to the user of the function.
Consequently, the user has fewer variables to maintain in the main algorithm,
reducing the clutter of the main algorithm.

Example 7.7. Consider the problem
of testing whether a triangle is right-angled, given its three sides a, b, c,
where c is the longest side. The triangle is right-angled, if

c^{2} = a^{2} + b^{2}

We can identify a subproblem of
squaring a number. Suppose we have a function square(), specified as

**square(y)**

**--inputs
: y**

**--outputs
: y2**

we can use this function three times
to test whether a triangle is right-angled. square() is a "black box"
— we need not know how the function computes the square. We only need to know
its specification.

**1 right_angled(a, b, c)**

**2 -- inputs: c ≥ a, c ≥
b**

**3 -- outputs: result =
true if c ^{2} = a^{2} + b^{2};**

**4 --** **result = false
, otherwise**

**5 if square (c) = square (a) + square (b)**

**6 result := true**

**7 else**

**8 result := false**

Tags : Computer Science , 11th Computer Science : Chapter 7 : Composition and Decomposition

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

11th Computer Science : Chapter 7 : Composition and Decomposition : Decomposition | Computer Science

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.