APS - Word Problem Analysis (Lesson)

Word Problem Analysis

Algorithms & Problem Solving

As we progress through this problem, do the steps yourself and then see if your technique is the same as you compare for the correct answer. Solutions, algorithms, or the methods to arrive at an answer may vary as many times there is more than one solution to arrive at the answer.

Now we have some unanswered questions that must be answered to consider the algorithm correct.

How is an algorithm created?
What are the conditions of the algorithm required to be met?
What kind of testing with different problems meeting the agreed condition must be done to validate that the algorithm may be used to solve problems of this type consistently?

Algorithm Input Conditions (all must be met)

1. Length of the fence is evenly divisible by rail size.
2. Changing fence length does not affect algorithm correctness.
3. Changing rail length does not affect algorithm correctness.

Algorithm Testing Conditions (all must be met)

1. Always test around the solution, either side, the edges.
2. Test extremes (in this case, the smallest fence rail length would be 0 which would mean we have no fence, and the largest is unknown).
3. Controlling input prior to executing the algorithm, the parameters, by checking algorithm conditions for use, allows the algorithm to directly solve the problem without having to check the input data first.

Having defined the conditions for using this algorithm, what tests should we check? Remember, we must set up test cases that meet the input conditions of the algorithm.

Off By One Problems

The above problems are examples of off by one problems, the difference between counting and spanning.

If we are asked to count the number of integer numbers from 1 to 10 our answer would be 10 as there are 10 numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

If we are asked to count the number of stars below, we understand from the . . . that the numbering continues until we reach 45.

There are 45 stars.

Now suppose you are asked to connect 12 stars with pieces of string between them. How many pieces of string will you need? You do not need 12 pieces of string but 11, as there are only 11 spans between them. Spanning is the space between, versus counting is the actual number of items.

Let's look at the spanning problem another way. Suppose you work at a grocery store and are to stock 6 rows of shelves when you work on Monday from 2 p.m. to 6 p.m. How many rows must you stock each hour?

Hmm.... 6 - 2 = 4 hours ? or is it 2, 3, 4, 5, 6 or 5 hours counting as we did above.

Well let's see.

2 p.m. - 3 p.m. is one hour,

3 p.m. - 4 p.m. is two hours,

4 p.m. - 5 p.m. is three hours, and

5 p.m. - 6 p.m. is four hours.

So 6 rows of shelves/4 hours = 3/2 = 1 ½ rows per hour.

There are 4 spans of time and 5 numbers in the range of numbers. Just like the fence post problem, the counting is one more than the difference.

Example: 10 - 1 = 9 spans between the numbers, but 10 -1 + 1 = 10 counting numbers.

Example: 45 - 1 = 44 spans between the numbers, but 45 -1 + 1 = 45 counting numbers.

These spans are also known in math as the distance between a and b: d = b - a

Generically, the number of numbers x inclusive from a to b is b - a + 1. x = b - a + 1, the number of items that spans would touch or the counted parts including ends.

Test Yourself!

Mike works from 9 a.m. to 3 p.m. How many hours does Mike work?
You are building shelves that will be 8 feet tall with shelves every foot. How many shelves are needed if a shelf starts at the bottom position and another is at the top position?

Check your answers here! Links to an external site.

Span	Use of bottom and top shelf	Where shelf is located
8	Span between 7 and 8	7 feet on line below, 8^th shelf , and 9^th shelf above
7	Span between 6 and 7	6 feet on line below, 7^th shelf
6	Span between 5 and 6	5 feet on line below, 6^th shelf
5	Span between 4 and 5	4 feet on line below, 5^th shelf
4	Span between 3 and 4	3 feet on line below, 4^th shelf
3	Span between 2 and 3	2 feet on line below, 3^rd shelf
2	Span between 1 and 2	1 foot on line below, 2^nd shelf
1	Span between 0 and 1	0 feet on line below, shelf at 0 ft, first shelf

Test Yourself!

You are building shelves that will be 8 feet tall with shelves two feet. How many shelves are needed if a shelf starts at the bottom position and another is at the top position?

Check your answer! Links to an external site.

Span	Use of bottom and top shelf	Where shelf is located
4	Span between 6 and 8	6 feet on line below, 4^th shelf and 5^th shelf above
3	Span between 4 and 6	4 feet on line below, 3^rd shelf
2	Span between 2 and 4	2 feet on line below, 2^nd shelf
1	Span between 0 and 2	0 feet on line below, shelf at 0 ft, first shelf

In programming, off by one errors are easily created when the programmer is counting and uses a less than, <, symbol to control a loop rather than a less than and equal sign, <=.

If you wish to count from 1 to 10 you might say

x = 1

while x < 10

print x

x = x + 1

With this pseudocode, the loop would continue and print the numbers

1, 2, 3, 4, 5, 6, 7, 8, 9 but no 10.

Changing the pseudocode to

x = 1

while x <= 10

print x

x = x + 1

would print all numbers between 1 and 10 inclusive: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.