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.

Â