Top-down vs. bottom-up

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.

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.

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.

More: Everything and all things: But wait, there's more

More: Aristotle

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.

Identifying the goal is most important! You do not want to climb the wrong stairs to get to the wrong goal.
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 forward to goal)
Think top-down: 5 if 4 if 3 if 2 if 1 (goal backward to start)

Gospels:

Bottom-up: Matthew, Mark, Luke (goal not clear, a lot of extra material)
Top-down: John (goal clear, no extra material)

It is said that problem solving is best done in a top-down method.

A top-down method goes from general to specific. It is goal-oriented.

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?

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?

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.

More: Tony Hoare

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.

The names for Lancaster and York in PA come from England.
The names for Lancaster and York in SC come from PA.

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.

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)

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?

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)

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?

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.

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.

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.

▶

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.

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)

More: Yogi Berra

Deduction is a top-down approach.
Induction is a bottom-up approach.

When it works, top down avoids extra work and gets you to where you want to be.

Top-down vs. bottom-up (this page)
Divide and conquer: Top-down and bottom-up

When does the top-down method not work well?

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.

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?

Rules-based methods: traditional automatic language translation.
Pattern-based methods: Google translate

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.

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.

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.