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.