Send
Close Add comments:
(status displays here)
Got it! This site "robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Divide and conquer: top-down and bottom-up
1. Divide and conquer: top-down and bottom-up
1. Top down
2. Backward chaining
3. Top down - flipped
4. Backward chaining - flipped
There are various names for a top-down backward-chaining divide and conquer problem solving strategy.
Topologically they are all the same since one can rotate and change the length of the branches as desired and it is the same tree.
2. Top down
Often, a top-down problem solving method diagram has the goal at the top. This is the way a tree is often drawn in computer science but is an upside down tree in the real world (root at the top, leaves at the bottom)
3. Flipped top down
The goal could be drawn at the bottom with the splits going upwards. This is still a top-down method.
To go down the river of a river flowing north, one goes south.
To go up the valley of a valley with lowest point in the north , one goes south.
It all depends on your point of view.
4. Backward chaining
A backward chaining method starts with a goal and works backward. Just like a top-down method.
Do you see any difference in what is actually done in using a divide and conquer problem solving method?
5. Flipped backward chaining
A backward chaining method can be flipped with the goal on the right. It is still backward chaining.
People whose languages, such as Arabic and Hebrew, are read right to left, may be more comfortable with a backward chaining method drawn this way.
6. Confusion
How would you learn top-down programming if you are confused at this point?
7. Top-down programming
Question to famous computer scientist
Tony Hoare (British computer scientist) . Why is it so hard to teach (or require) beginning programmers top-down programming?
8. Top-down programming
You cannot teach beginners top-down programming, because they don't know which end is up. Tony Hoare.
Problem-solving methodology:
Identify the problem.
Define the problem.
Design top-down solution (decomposition).
Implement bottom-up implementation (composition).
Evaluate the results.
Compare to Waterfall method,
SDLC (Systems Development Life Cycle), etc.
9. Linear sequences
1. Top down
2. Backward chaining
3. Top down - flipped
4. Backward chaining - flipped
Not all trees have two or more branches. Some problems are best split into just one other part. Such a sequence is called a serial sequence.
This happens when a sequence of events in time need to be accomplished, each before the next one can start.
It is the same idea. Here are some visualizations - topologically all the same.
10. Top-down - root at the top
Remember that top-down has to do with the direction of the arrows from the root, not the physical location based on how the tree is drawn.
The diagrams depict the decomposition. The composition is in the opposite direction.
11. Top-down - root at the bottom
12. Backward-chaining - root at the right
13. Backward-chaining - root at the left
14. Summary
At all times, the goal and method remains the same. It is only how the diagram is drawn that is changed.
There are many ways to depict a divide and conquer problem solving method. These method work from the root down to the leaves and include the following.
top-down
backward-chaining
In a similar manner, a bottom-up or forward-chaining method starts with the leaves and works towards the root - or goal, regardless of how the diagram is drawn.
15. End of page
