0:02
In this video, we will develop an algorithm for
a particular pattern of blue and red squares on a grid.
We're going to start with step one,
doing an instance of the problem.
And in this instance, I picked N equals three.
So the first thing I'm going to do is work the problem by
hand without really thinking through exactly what I'm doing.
That is, I'm going to do it right,
but I'm not going to try to write down what I did.
Once I've done that, I'm going to do step two where I
write down exactly what I did in a step-by-step fashion.
The first thing I did was put a blue square at zero, zero.
Then I put a red square at zero, one,
another red square at zero,
two, a blue square at zero,
three, a red square at one,
one, blue at one,
two, red at one, three,
red at two, two, red at two,
three, and finally a blue at three, three.
Now I'd like to generalize these steps,
step three of the programming process.
And if we look at the steps,
we can see there's some repetition and counting behavior,
which is going to help us generalize these steps into an algorithm.
These first four steps have x equals zero,
then we have a group of three steps for x equals one,
a group of two steps for x equals two,
and finally a single step for x equals three.
So we're repeating somewhat similar steps as we count x going from zero to three.
But exactly what we do varies.
We color the squares blue, red, red,
blue for x equals zero or red, blue,
red for x equals one,
so the color pattern is something we still have to figure out.
Also, how many steps in the y coordinate of each varies.
Let's look at the y coordinates first,
coming back to the colors in a minute.
If we look at this first group of steps,
we see that the y coordinates go from zero to three.
If we look at the second group of steps,
we see that the y coordinates go from one to three,
and in this third group, two to three.
So it looks like, in general,
we're counting from x to three.
If we ignore the colors for a moment,
we can take this group of steps and say,
we count from zero to three,
calling the number that we count y,
then put a square of some color we'll figure out later at zero, y.
And we can write similar steps for each of these other groups.
And now we can use patterns in these steps to generalize our algorithm further.
Each set of steps is the same except for the x coordinate shown in bold,
and these vary in a nice counting pattern.
That is, we can say count from zero to three,
call each number that we count x,
and for each of those numbers,
we'll count from x to three and call that y,
and we'll put some color square at x, y.
But this is only true for N equals three.
A clue that we have not finished generalizing
is that the steps do not depend on N at all.
We know that the pattern will be different for different N,
but this is not reflected in the algorithm we wrote.
We need to make it more general.
How could we do this?
We might just realize it,
but if we don't, we can go back and repeat steps one and two.
If the pattern is hard to figure out,
we may have to do steps one and two many times.
So for example, if we went back and performed step one for N equals one,
we end up with this pattern.
And when we do step two,
we write down these steps.
If we go through the generalization process again,
we see that we come up with these steps.
Count from zero to one,
call it x; count from x to one, call it y;
then put a square of some color at x, y,
which is very similar to N equals three except this number has changed.
For any N, we count from zero to N based on the pattern from our examples.
Now we have a more generalized algorithm.
Of course, we need to figure out what the question marks are for the colors.
To do that, we can go back to the colors from our N equals three example.
We had mostly red squares with some blue squares,
so we should figure out the pattern for when a square is blue.
I've thrown away the red ones so we can just look at blue for a pattern.
This pattern may be a bit subtle to see with only four pieces of information.
You may have figured it out,
but if not, what could you do?
Well, it might be easier to see with more information.
Looking at N equals five,
we have more blue squares to consider.
Now, you look at the pattern and see what you come up with,
and this is mostly your ability to look at numbers and find patterns.
If we add the x and y coordinates together,
we see that they are zero, three,
three, six, six, six, and nine.
So the pattern here, is we draw a blue square if
and only if x plus y is a multiple of three.
Now we can go back to our algorithm and specify if x plus y is a multiple of three,
we put a blue square at x, y.
Otherwise, we put a red square at x, y.
This algorithm looks pretty good,
but we will want to do step four and test it,
as shown in the next video.
Andrew D. HiltonAssociate Professor of the Practice
Genevieve M. LippAdjunct Professor
Anne BracySenior Lecturer
