This folder contains a set of resources for exploring the "travel" section
problem in a series of steps, building up towards the final backtracking
solution. The file travel.pdf is a handout for the students (travel.doc is
included in case anyone wants to edit the original). The folder also contains
several pictures (png files) to help explore the suggested stages of
development.
I would recommend running the section this way:
Pass out the section handout and discuss the travel problem in general. Talk
about how there is an x-y coordinate plane and you start at (0, 0) and you can
make any of the three moves (N, E, NE). Ask them how to get to (1, 1). There
are 3 solutions:
N E
E N
NE
Ask them if you're trying to get to (x, y), how many moves might it take? It
took up to 2 moves to get to (1, 1). Why 2? They should come up with the idea
that it will take at most (x + y) moves. It might take fewer than that if you
include some NE moves, but don't worry about that for now.
So work with them to write version 1 of the code. In this version, we simply
want to produce all possible combinations of moves that are of a certain
length. For example, for the (1, 1) case, you want to produce all possible
ways to make 2 moves. How many different answers are there? 9. Why 9? It's
important to think about this as a decision tree. Open up travel1.png to show
them a tree representation of what you get with 2 moves. From the starting
position, you can make any of the three choices. And for each of those
possible first moves, there are three possible second moves. This kind of
"explore all choices" problem is nicely converted into recursion. Each
recursive call can generate three more calls for the three choices and you have
to include a base case for the bottom of the tree. So the basic pseudocode is:
if (we've got a set of n choices) {
print the n choices.
} else {
try adding N to the set of choices
try adding E to the set of choices
try adding NE to the set of choices
}
This would be a good thing to do with the group, as in:
Okay, everyone look at the diagram. Each oval in this tree will turn into
a call on the method. Notice that it can be three deep. So I need three
volunteers to pretend to be method invocations. Jane, Fred, and John?
Great. Imagine that I ask Jane to produce all of this, so she's the top of
this tree. What does she do? She wants to make three calls to explore the
three possibilities. So let's say that she's going to call Fred three
different times, once for each of the three choices. So first she calls
him saying that she's chosen N. What does Fred do? Fred will do something
similar. He will call John three different times for his three choices.
He once again starts by picking N and he calls John saying that the current
choices are "N N". Then what does John do? He should notice that we've
picked two moves and that was our goal, so he's going to be our base case
and he just prints it. Then he's done. Which brings us back to Fred. He
has already tried N, so now he moves on to trying E. So he calls John
again saying that the choices are "N E". And John again just prints it and
returns. Can you see that John is going to be our base case every time?
How many times are we going to call him? That's right, 9 times. He prints
everything, but we have to make separate calls each time to make him print.
So after John prints "N E", we're back to Fred and he calls John a third
time telling him to explore "N NE", just like in the diagram. And John
prints it. And then we come back to Fred, but he's done. So now we
finally get all the way back to Mary. She's finished exploring the branch
of the tree that starts with N and she moves on to the middle branch that
starts with E. She does that by once again calling on Fred. How many
times do we call on Fred? Right, three. And how many times do we call on
Mary? Just once because she's the top of the tree. That's how these
recursive methods end up working, with a branching out like this where one
call can generate three, which in turn generate nine, which would then
generate 27, and so on...
Then write the code with them. You could ask questions like, "How are we going
to know when we get to a base case? Aren't we going to need to know how many
more steps we can take? That will need to be a parameter. All of these
recursive backtracking problems involve adding extra parameters. That's why
we're going to need an extra method. We normally define that as a private
method. We call it a "helper method". There's a discussion of that in the
textbook in chapter 12. So let's add that to the code. And it will have a
parameter for the number of steps left. And how does it get an initial value?
What did we say about the most number of steps you might need to get to (x, y)?
It's x + y. And when we get to the base case, we're supposed to print. But
what do we print? We need to keep track of the moves somehow. For this
version, let's keep it simple and just build up a string as we make choices and
then we can print that string...
Anyway, I'd spend a good chunk of time developing version 1. The code is
short, but there's a lot there, so it's worth it to develop it slowly. I can
imagine spending as much as half an hour just to get version 1 if you do it in
the careful way and really get them to think about the parameters and what
their intial values are and how they change from one call to the next. And you
can even point out things like why we use:
stepsLeft - 1
in our three calls instead of saying:
stepsLeft--
on each of the three calls (which would subtract it 3 times and give you the
wrong value on the first call).
Once you get to a good solution to version 1, I'd pass out the travel handout.
It has all of the answers you're about to talk about, but this is confusing
enough that you should give it to them anyway. That way they can write notes
as they go along on what was different from one version to the next.
You could tell them not to cheat by looking ahead, but tell them that you want
to figure out how to have it keep track of where you end up. So you don't want
just the series of moves, you also want to know what x-y position you get to.
You can show them travel2.png to point out what we're after. This requires
adding some parameters to the recursive method and including this information
in the println.
In both version 1 and version 2, you're printing all of the sequences of a
certain length. In version 3, we want to print just solutions. Have them
point out to you in travel2.png which of the ovals are solutions. Then you can
open up travel3.png to show that they are highlighted with red text and blue
ovals. So modify the code to print just those three ovals. It again requires
more parameters. This time you have to pass the target x and y values and
include a test to see if the current x and y are equal to the target x and y.
Version 3 is actually pretty good because it prints all of the answers. But
now you want to think about efficiency. You don't want to explore more than
you need to. So look again at travel3.png and ask them if there are some ovals
in that diagram that shouldn't be explored. The answer is yes. On the
right-hand side of the tree, you'll see it exploring even after it has found a
solution. That's stupid. You'll never come to a second solution because
you're always moving away from it. So modify the code so that it stops
searching after it finds a solution. This is a really trivial change. All I'm
changing from my version 3 to my version 4 is changing two if statements into
an if/else. In fact, when you add the if statement in version 3, they might
recommend that you make it an if/else. I like the idea of doing these two
versions separately even though it's a minor change between them. So for
version 3, I would stick with the two ifs because then it's still exploring a
full tree of a particular depth. If you open up travel4.png, you'll see the
tree you get when you stop searching after a solution is found. Be careful to
open up travel4.png and not travel4-2.png.
In the next version you want to think about what happens when you are dealing
with a bigger tree. For example, what if you were asked to find all paths to
(1, 2). That will work with a tree of depth 3. Open up travel4-2.png and
you'll see a picture of what our version 4 code will explore. The picture is
big enough that you'll have to click on it to make it zoom. So you'll have to
scroll left and right to see the detail, but it's a standard tree of depth 3
that is trying all possibilities but it's stopping once it finds a solution.
We can do even better. There are some dead-ends here. In fact, forget about
the whole idea of keeping track of how many moves to make. You know that the
leftmost oval that leads to (0, 3) is a dead-end. How do you know that?
Because 3 is bigger than the y-coordinate we are looking for. Next to that is
a solution and next to that is an oval that gets to (1, 3). That again is
clearly a dead-end because 3 is bigger than the target y-value of 2. But there
are some other interesting dead-ends. For example, in the middle of the tree
you'll see a node labeled "E E: (2, 0)". This is a dead-end because the
x-coordinate is bigger than the target coordinate of 1. So why explore further
from that point? Why not stop exploring when you get there. Other nodes that
are like this are the node "E NE: (2, 1)" and "NE E: (2, 1)". You shouldn't be
exploring under those nodes. In fact, at this point you could open up
travel5.png to see what we want as our exploration tree. For all of those
dead-end nodes, it doesn't explore underneath them. So writing version 5
involves incorporating this into the recursive method. We can ditch the
parameter that kept track of the number of levels to explore because we aren't
going to use levels to keep track of it. Instead we're going to make sure that
we continue the recursion only if the current x-y coordinates have not gone
beyond the target x-y coordinates.
Version 5 is the complete backtracking solution that stops searching after it
finds a solution and after it reaches a dead-end. But it used a string to keep
track of the sequence of choices. More often, we'd want to have the different
moves stored in some kind of data structure like a list. So that's the point
of the final version. You want to incorporate the idea of adding each choice
to a list. This brings in the classic backtracking paradigm of:
choose
explore
unchoose
For each of the three choices, you have to add the choice to the list, explore
what's left, and then remove that choice from the list. You can point out that
their homework is more like this version where they have to include code to
choose and unchoose. The earlier versions avoided that by building up a
String, but they won't be able to do that for the homework, which is why this
is closer to what they'll need.
I would end by talking about a final variation on backtracking that they'll
want to know about. In this final code, there were three choices and you see
the choose/explore/unchoose code very clearly for all three choices. But that
should somewhat offend them because it's so redundant. What if there were 10
choices? Would you have 30 lines of code? So another variation is that you
often use a for loop that has the choose/explore/unchoose code inside it. In
fact, it's on the cheat sheet as the template to use for backtracking
solutions. Point out that in their homework they'll be doing something that
involves using the for loop approach.
I can imagine doing this section where you project your computer screen and
come up with each of the different versions. I've given you a starter version
of the program called GoNorthEast.java. It has the private method, but it
doesn't do anything. But you could also do this section on overheads or on the
whiteboard.
In terms of timing, one of the nice things about having the handout with the
different versions is that if you find yourself short on time, you can speed it
up a bit and instead of writing all of the code, you can just talk about how
the new version differs from the previous one. So that way you can get through
the whole thing even if you find yourself pressed for time.
The file solution.txt is a text version of the different solutions.