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.
Top-down vs. bottom-up
1. Top-down vs. bottom-up
The use of top-down backward-chaining thinking and logic in problem solving is essential to computer science thinking.
C if B if A (top-down backward chaining)
A then B then C (bottom-up, forward chaining)
Most other people use bottom-up forward-chaining thinking and logic and problem solving which is, in most cases, not the best way. The most common problems with this way of thinking is that the goal may not be clear, one may not get to the goal, one may deviate from the goal, and one may do extra work in trying to get to the goal.
2. Aristotle: Top down reasoning
English: It is just as the Pythagoreans say, the whole world and all things in it are summed up in the number three; for end, middle and beginning give the number of the whole, and their number is the triad. (Loeb#338)
Greek: Καθάπερ γάρ φασι καὶ οἱ Πυθαγόρειοι, τὸ πᾶν καὶ τὰ πάντα τοῖς τρισὶν ὥρισται· τελευτὴ γὰρ καὶ μέσον καὶ ἀρχὴ τὸν ἀριθμὸν ἔχει τὸν τοῦ παντός, ταῦτα δὲ τὸν τῆς τριάδος. Aristotle: On the Heavens [268a]
Notice how Aristotle says
"end", "middle" and "beginning" (top-down backward-chaining) rather than
"beginning", "middle" and "end" (bottom-up forward chaining).
Aristotle says the
"everything" while the translation says the
"whole world". Some in modern Greek makes a play on words with
"everything" and a panda (animal) since the words are spelled and pronounced the same.
3. Stair analogy
A stair analogy can be used to help understand
top-down design and
bottom-up implementation.
The goal is the top of the stairs.
The start is the bottom of the stairs.
Implementation:
Do it: 1 to 2 to 3 to 4 to 5 (same either way)
Design: When it works,
top-down tends to be
better.
Think bottom-up: 1 then 2 then 3 then 4 then 5 (start to goal)
Think top-down: 5 if 4 if 3 if 2 if 1 (goal to start)
It is said that problem solving is best done in a top-down method.
4. Top-down vs. bottom-up
A top-down method goes from general to specific. It is goal-oriented.
5. Top-down vs. bottom-up
A
bottom-up method goes from specific to general, working towards the goal.
Question: Why is it difficult for beginning students to understand top-down and bottom-up methods?
6. Top-down programming
You cannot teach beginners top-down programming, because they don't know which end is up (Tony Hoare).
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.
Let us look at solving a simple problem. How would you give instructions for someone in York to get to Elizabethtown via Lancaster? You are in York and want to go to Lancaster.
8. Lancaster and York
The names for Lancaster and York in PA come from England.
The names for Lancaster and York in SC come from PA.
9. Getting from A to C
How would you give instructions for someone in York to get to Elizabethtown via Lancaster?
Note: You are in York and want to go to Elizabethtown.
10. Start to stop way
You start in A:York.
From A:York, go to B:Lancaster.
From B:Lancaster, go to C:Elizabethtown.
You are at your destination, C:Elizabethtown.
That is: (start) A to B to C (destination)
That is: A then B then C (bottom-up, forward chaining)
11. Stop to start way
Your destination is C:Elizabethtown.
You can get to C:Elizabethtown from B:Lancaster.
You can get to B:Lancaster from A:York .
You start in A:York.
That is: (destination) C from B from A (start)
That is: C if B if A. (top-down, backward-chaining)
How do you like this way of giving directions?
12. Comparison
Which way of giving directions is more clear?
A then B then C (bottom-up, forward chaining)
C if B if A. (top-down, backward-chaining)
13. Methods
Both methods provide the same solution.
Bottom-up, forward chaining (link of chains), inductive. synthesis
Top-down, backward chaining (link of chains), deductive, analysis.
Which method is more comfortable to you?
14. Implementation
The methods are ways of thinking about the problem and solution.
In both ways, one travels the exact same route in time and space.
Programming languages example: top-down parsing and bottom-up parsing of input.
15. Abstraction
Bottom-up: (forward chaining, inductive)
A to B to C
A then B then C
Top-down method: (backward chaining, deductive)
C from B from A
C if B if A.
Thinking in a top-down backward-chaining way can be very helpful for solving problems in general and in computer science in particular.
16. Bottom-up trade-offs
The bottom-up, forward chaining method, in general:
It does not insure a correct solution (we may not get there).
It may require extra work.
Example: Getting a college degree.
17. Methods and trade-offs
1 What goal?
2 Wrong goal
3 Give up
4 Distracted
The
top-down,
backward-chaining method, in general, insures a correct solution (we will get there) that is
direct-to-goal. It avoids extra work.
A
bottom-up,
forward-chaining method, in general, is
indirect-to-goal and may involve extra work and may not get to the goal.
Of course, this assumes that you have a goal and are working towards that goal.
18. Goals
You've got to be very careful if you don't know where you are going, because you might not get there. Yogi Berra (American professional baseball player and manager)
19. Induction and deduction
Deduction is a top-down approach.
Induction is a bottom-up approach.
20. Top-down: when it works
21. Induction
A good way to recognize a top-down design in data is to use a bottom-up inductive recognition process and gradually piece together parts. At some point, one sees the pattern and can move to the top-down deductive pattern.
This is what is done with a bottom-up parsing method. It recognizes a language and pieces together the parse tree in a bottoms-up manner. One people recognize the top-down patterns, they may develop rules that actually inhibit learning.
Here are some problems that work better in a bottom-up manner than a top-down manner.
22. Language learning
Which is a better way to learn a language?
Some schools and teachers: Learn the top-down grammar rules and use those rules to learn and work with the language.
Children: Learn patterns and piece those patterns together to learn the language - without a formal grammar.
How well does a normal child learn a language using the bottom-up process by the time they are six years old?
How well does an adult learn a language using the top-down process after, say, six years of study as part of an overall curriculum that includes other subjects?
23. Language translation
Rules-based methods: traditional automatic language translation.
Pattern-based methods: Google translate
24. Alan Kay and teaching children to program
How might one go about writing a program to draw a circle.
Teen-ager using Cartesian coordinates and equation for a circle in a top-down deductive manner.
Teen-ager using polar coordinates and equation for a circle in a top-down deductive manner.
Child using a step and move idea in a bottom-up inductive manner.
25. Problem solution types
There are three "
E" parts to solutions where each step depends on the previous steps.
1. Does a solution "exist"?
2. Can we find an "effective" solution?
3. Can we find an "efficient" solution?
In general problem solving, one searches for a solution or that a solution exists. Once this search establishes the existence of a solution, one may seek an effective solution. Later, one may search for the most efficient solution, according to some set of efficiency criteria. An example is that of prime numbers.
26. Solution examples
Euclid proved that there exist an infinite number of prime numbers but not an effective way to find (a finite number of) them or to determine if a number is prime.
Eratosthenes provided an effective way (algorithm) to determine if a number is prime by finding every prime (to a finite limit) called the Sieve of Eratosthenes.
No one knows of an efficient way to determine the prime factors of a (large enough) composite number (without trying all possibilities).
The world's security of information systems is based on the assumption that there is no efficient way to determine the prime factors of a large composite number.
27. End of page
