Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.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
2. Divide and conquer: Top-down and bottom-up
1 Start design at goal
2 Break design goal into parts
3 Break design parts into subparts
4 Break design subparts into more parts
5 Implement the parts with unit tests
6 Combine the parts up the tree - unit tests
7 Combine the parts up the tree - unit tests
8 To original goal is achieved - unit tests
A divide and conquer problem solving method starts with a goal.
The problem is broken down in a top-down or backward-chaining manner as part of the solution design.
The solution is implemented in a bottom-up or forward-chaining manner as part of the solution implementation.
At each point in the implementation, unit testing is added for each part and abstractions made as needed.
3. Problem solving: divide and conquer
A
divide and conquer problem solving method is a top-down method that breaks a problem into smaller parts, solves each smaller part, and combines the solution (in a bottom-up manner) to solve the original problem.
Identify
Define
Design top-down, backward-chaining
Implement bottom-up forward-chaining
Evaluate
4. Divide and conquer
Divide each difficulty into as many parts as is feasible and necessary to resolve it René Descartes (French philosopher, mathematician and statistician)
5. Computer science
Fallacy:
You should require beginning programming students to use top-down programming.
Problem solving in computer science is best done using
top-down programming.
top-down programming
goal-driven programming
backward-chaining logic
Why do many computer science programs require beginning students to do "
top-down programming"?
6. 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?
7. 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.
8. Top-down programming
Fallacy:
One should implement a computer program in a top-down manner.
The phrase "
top-down programming" is deceptive. Have you ever tried to write a program "
top-down"?
Do it once and you will see that it does not work very well.
The phrase "
top down programming" refers to a "
top-down program design" and then a "
bottom-up program implementation".
Many people try to do "
top down programming" by doing "
top-down coding".
Some teachers who have never really used the method will teach this fallacy to their students. How would you define a "
programmer"?
9. Top-down vs. bottom-up
1 What goal?
2 Wrong goal
3 Give up
4 Distracted
A top-down design insures one will get to the goal.
A bottom-up design may require extra work and may not get to the goal.
10. Fix-it decision tree
1 First decision
2 Second decision
3 True positive
4 True negative
5 False positive
6 False negative
7 Decision tree
11. Maze generation
1 Maze 1
2 Maze 2
3 Maze 3
4 Maze 4
5 Maze 5
6 Maze 6
7 Maze 7
8 Maze 8
9 Maze 9
10 Maze 10
11 Maze 11
12 Maze 12
13 Maze 13
14 Maze 14
15 Maze 15
Web site:
In-line SVG (formatter Lua)
Lua to SVG
JavaScript and SVG
JavaScript and SVG and D3
R
Julia
Python
Java
C#
12. Goal
A divide and conquer problem solving method starts with a goal, here labeled "
1". Assume that this problem is too complicated to be easily solved and is therefore broken into parts. Here, division by two is used.
A not-so-easy-to-read gray with red outline is used for the top-down design phase as designs often change and are not always as clear as one would like.
13. Split
The problem "
1" is split into two parts "
2" and "
3".
14. Split again
The problems "
2" and "
3" need split.
Problem "2" is split into problems "4" and "5".
Problem "3" is split into problems "5" and "7".
15. Split again and solve
Each of problems "
4", "
5", "
6" and "
7" are split into parts.
16. Design
During the top-down design, code is not written unless some prototype is needed to verify architecturally significant parts of the design.
Something is architecturally significant if not being able to do that part will cause the entire project to fail.
17. UML
18. Solve the leaves of the problem
The leaves of the problem are then solved.
In software engineering, unit tests are created for each leaf.
Those solutions will be worked back up the tree until the original goal is solved.
19. Continue up the tree
Continue composing the solutions bottom-up to solve nodes up the tree.
In software engineering, unit tests are created for each node.
20. Continue up the tree.
Continue composing the solutions bottom-up to solve nodes up the tree.
In software engineering, unit tests are created for each node.
21. Composition
The solutions to each of the problems at the leaves are then passed back up the tree and combined. This is called composition.
In software engineering, unit tests are created for each node.
If anything goes wrong during the process, adjustments need to be made.
22. Pattern
The pattern is as follows.
Design a solution, decomposing parts top-down into smaller subproblems (down the tree).
Implement the solution, composing parts bottom-up into solving subproblems (up the tree).
23. Top-down programming
Many teachers without real world experience will often teach top-down programming to students as if one should actually do programming that way - literally.
A better way is to first design (in the head, on paper, etc.) the solution top-down and then implement that solution bottom-up. Each part of the bottom-up process has associated unit test code to test that part of the implemented solution.
The entire process is called top-down programming but the actual coding process is best done bottom-up after the top-down design.
Whenever something does not work as expected during the bottom-up implementation, the design is revisited, top-down, and modified. Hopefully not too much work from the bottom needs to be changed or lost due to the changed design.
24. Phone tree
A traditional phone tree is based in this idea, though with, say, a split of more than two.
25. Tree structures
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.
26. 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)
27. 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.
28. 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?
29. 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.
30. 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. A tree-structure is needed by many problems in computer science. Most people will only need to understand the linear sequence.
And that top-down or bottom-up sequence can be viewed in any direction.
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.
31. 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.
32. Top-down - root at the bottom
33. Backward-chaining - root at the right
34. Backward-chaining - root at the left
35. 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.
36. End of page