Logical Problem Solving

by Robert Lamey, Prentice Hall 2002,  0-13-061882-9

(Paraphrased; examples added for clarification)

Rule 1The Clarity Rule

a.   Be clear about what information you have to work with.

b.   Be clear about what information you are trying to discover.

Example: determine pieces per dollar, given date and time, cost per weight, age of the vendor, and pieces per weight.

Rule 2The Units Rule

Pay attention to units. If the unit of measurement is kept with each number, the mathematical operation to be performed will be apparent without the knowledge of any formula. Correct operations will lead to units that cancel. Incorrect operations will lead to units that compound and confound.

Example: obtain distance from speed and time, where speed is in kilometres per hour and time is in hours. Speed multiplied by time yields distance (km/hr * hr č km)

Rule 3The Picture Rule

Whenever possible draw a picture.

Example: pipe the output of the grep to more:

grep …

č

|

č

more

display

source

stdout

pipe

stdin

destination

stdout

 


Rule 4The Working Backwards Rule

Instead of working from the beginning of a problem asking what is the first step toward the end, start at the end and ask what is needed to perform the last step. From there examine what is necessary for the second to last step and work toward the beginning.

Example: write a command that has some "dash" options followed by the input filename followed by the output filename, as in:

command –1 –2 –3 infile outfile

The outfile is always at argv[argc – 1] and infile is always at argv[argc – 2]. Everything between argv[1] and argv[argc – 3] inclusive (if there is anything there at all) must all be dash options.

Rule 5The Repetition Rule

When approaching a problem look for repeated operations. The number of times the operation is repeated is usually irrelevant.

Example: convert a decimal integer to binary for display (and consider also Rule 4):

BEGIN

   GET a positive integer to convert

   WHILE the number is not zero

       right-bit = remainder mod 2

       IF right-bit is zero

          SET next rightmost char = '0'

       ELSE

          SET next rightmost char = '1'

       number = number / 2

   END WHILE

   DISPLAY result

END


Rule 6The Clarity in Loops Rule

When a problem involves repeated operations, be clear about which operations are repeated and belong inside the looping structure and which operations occur only once and should be outside of the loop.

Example: sum the integers from 1 to some ceiling:

BEGIN

   FOR 1 to ceiling

       GET ceiling         Oops

       SET total to zero   Oops again

       ADD 1 to total

       PRINT total

   END FOR

END

Rule 7The Limit the Problem Rule

When a problem is too difficult to solve consider limiting the problem to find a special case solution.

Example: calculate the height of a building by dropping an object from the roof and timing its fall until you hear it hit the ground. Ignore variations in local gravity, air resistance while falling, wind forces, and the speed of sound of the impact.

Rule 8The Concrete Example Rule

When examining a general problem it is often more illuminating to work with a specific instance. An example with numeric values is always easier to understand than the general case.

Example: calculate the factorial of a number (1 x 2 x … n). Test your solution (the PDL at first) with several numbers, like 3, 5, 10, and 20. Test the boundary cases – how small and how large can n be?


Rule 9The Successive Approximation
                                                                 Rule

When an exact solution is too difficult to calculate, an approximate answer of arbitrary accuracy can often be found by adding terms that make a partial solution come ever closer to the true solution.

Example: calculate p (pi) to as many digits of precision as possible. A solution is to find that the formula below (among others) gets closer and closer to the value of p as more terms are added to the sum:

p = 4 * ( 1 – 1/3 + 1/5 – 1/7 + … )

See also Rule 5, since a loop will work quite nicely here (and check Rule 15, too).

Rule 10    The Strategic Guessing Rule

a.   Make a reasonable initial guess.

b.   Check the accuracy of the guess.

c.   Repeatedly refine the guess until the desired accuracy is achieved.

Example: compute the square root of a number by making a guess, squaring the guess and measuring its error, then adjusting the guess and repeating until the result is "close enough" to the correct value.

This technique was first described to me in 1961 as "the way computers calculate square roots" by a programmer on an ancient (now) IBM 650 computer at the University of Ottawa.


Rule 11    The Functions Rule

As problems become more complex it becomes increasingly important to divide the logic into smaller units that solve individual parts of the problem. These units correspond to programming functions.

Example: no segment of code should be much larger than one or perhaps 2 screens. Select self-contained pieces that return one or a few results from a small number of arguments such that each piece (function) can be tested on its own and understood entirely with relative ease.

Rule 12    The Brute Force Rule

When all else fails try examining all possible solutions in a systematic manner.

Example: many sort algorithms rely on comparing each and every pair of elements in order to re-arrange them in the desired order.

Rule 13    The Self-Consistency Rule

If a statement is assumed to be true and then leads to a conclusion contrary to some known fact, the original assumption must be false. If a statement is assumed to be false and leads to a conclusion contrary to some known fact, the original assumption must be true. All real-world scenarios must be self-consistent.

Example: an application that calculates the floor area of a residential home to be thousands of square metres is probably over-calculating, but if it's a commercial office tower and only hundreds of square metres then it's quite likely to be under-calculating.


Rule 14    The Probability Rule

When probabilities or odds need to be calculated, brute force can usually be applied by simulation the scenario and counting how many times the event of interest occurs.

Example: if you flip a coin a billion times (1,000,000,000) how many times does it come up heads? A for loop and a random number generator do well for this.

Rule 15    The Approximation Rule

Look for approximations that simplify a problem but do not appreciably affect the accuracy of the solution.

Example: The value of p is something near but greater than 3.141592653589793239462643… but 3.14159265 is probably close enough for most purposes much of the time.

Rule 16    The Expanding the Scope Rule

When generalizing a solution to encompass a greater range, greater complexity, broader conditions, or greater utility, focus on the differences between the conditions when the solution works and the new conditions.

Example: a working solution does not have to be rewritten to add another feature. In fact, it's very practical to write a solution in a series of steps, starting with a very limited implementation and adding more features (and complexity) in well-planned stages, testing (and making backups!) at every stage.


Rule 17    The Recursion Rule

A problem can be solved recursively if :

a.   The final step or the base condition is known.

b.   The first step of the problem leads to exactly the same problem but one step closer to the solution.

Example: recursion (having a function call itself over and over again) is a well-known method for calculating factorials or other mathematical values, for walking binary trees, and for many other programming problems.

Rule Zero     Start!
                                 Write something down!
                                            Try something!

This rule has been left to the last because without the other rules there is no starting point, nothing to write down, nothing to try.

What should be tried when facing a new problem?

·        Rewrite the problem.

·        List the information available.

·        Draw a picture.

·        Think of a concrete example.

·        Limit the problem.

·        Look for repeated operations.

·        Examine the units.

·        Try working the problem backward.

·        Try to guess at the answer.

·        Try to brute force your way to an answer.

·        Try a simulation.

·        Create an object [or a structure].

·        Try recursion.

But do something!