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.

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?

Question to famous computer scientist Tony Hoare: Why is it so hard to teach beginning programmers top-down design methods?

You cannot teach beginners top-down programming, because they don't know which end is up. 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.

With which method are you more comfortable?

• 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:

• Does not insure a correct solution (we may not get there).
• Might require extra work.

The top-down, backward chaining method, in general:

• Insures a correct solution (we will get there).
• Avoids extra work.

You have to be very careful if you don't know where you're going, because you might not get there. Yogi Berra

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

12 questions omitted (login required)