0:00:00.000,0:00:09.000


0:00:09.000,0:00:11.000


0:00:11.000,0:00:14.000
This presentation is delivered by the Stanford Center for Professional Development.

0:00:14.000,0:00:23.000


0:00:23.000,0:00:25.000
Hi there. Good afternoon.

0:00:25.000,0:00:27.000
Welcome to Monday.

0:00:27.000,0:00:28.000
Today's a big day.

0:00:28.000,0:00:31.000
A big day, right? We've got a couple of recursive backtracking examples that we

0:00:31.000,0:00:35.000
didn't get to on Friday that I'm gonna

0:00:35.000,0:00:36.000
talk you through today,

0:00:36.000,0:00:40.000
and then we're gonna talk a little bit about pointers, the long anticipated introduction to

0:00:40.000,0:00:42.000
one of the scarier parts of the C++ language

0:00:42.000,0:00:47.000
as kind of a step toward building linked lists and the recursive data idea

0:00:47.000,0:00:49.000
that we will study today and

0:00:49.000,0:00:51.000
continue into Wednesday.

0:00:51.000,0:00:54.000
So the two samples I want to do are both based on the same backtracking pseudocode that we

0:00:54.000,0:00:56.000
were using on Friday. I

0:00:56.000,0:00:59.000
just want to go through them. I'm gonna do a little bit less attention to the code and

0:00:59.000,0:01:03.000
a little bit more attention to the problem solving because at some point I think the problem

0:01:03.000,0:01:03.000
solving

0:01:03.000,0:01:05.000
is really where the tricky stuff comes on.

0:01:05.000,0:01:08.000
And then the kind of - turning it into code, there's some details there but

0:01:08.000,0:01:11.000
they're not actually as important, so I'm gonna de-emphasize that just a little bit here and

0:01:11.000,0:01:13.000
think more about solving it.

0:01:13.000,0:01:16.000
So this is the pseudocode for any form of a backtracker, right, that has

0:01:16.000,0:01:17.000
some sort of,

0:01:17.000,0:01:20.000
you know, failure and success cases, like when we run out of choices, we've hit a

0:01:20.000,0:01:24.000
dead end, or we've hit a goal state, we've - you know, there's no more decisions to make,

0:01:24.000,0:01:26.000
right, is this want to be, yes or no,

0:01:26.000,0:01:28.000
and then otherwise there are some decisions to make.

0:01:28.000,0:01:33.000
And for all the possible decisions we could make, we're gonna try one, be optimistic

0:01:33.000,0:01:37.000
about it working out, make that recursive call that says that choice was where I

0:01:37.000,0:01:42.000
wanted to be. If it returns true, or whatever the success return value is,

0:01:42.000,0:01:44.000
then we return true,

0:01:44.000,0:01:47.000
right? No need to look any further. That choice was good enough.

0:01:47.000,0:01:51.000
If it didn't work then we gotta unmake - try some other choices. If we try all the

0:01:51.000,0:01:55.000
things available to us and no case, right, did solve ever return true,

0:01:55.000,0:01:59.000
then we can only conclude that the configuration as given to this call was

0:01:59.000,0:02:00.000
unsolvable,

0:02:00.000,0:02:02.000
which is where that return false

0:02:02.000,0:02:06.000
causes it to back up to some earlier call and start unmaking

0:02:06.000,0:02:08.000
that next layer of decisions,

0:02:08.000,0:02:11.000
and then recur further down, eventually either

0:02:11.000,0:02:15.000
unwinding the entire recursive [inaudible] all the way back to the beginning and saying it

0:02:15.000,0:02:18.000
was totally unsolvable no matter what, or eventually finding

0:02:18.000,0:02:21.000
some sequence of decisions that will lead to one that will get us to a success

0:02:21.000,0:02:23.000
case.

0:02:23.000,0:02:27.000
So the one I'm gonna show you here is the sudoku,

0:02:27.000,0:02:31.000
which is those little puzzles that show up in

0:02:31.000,0:02:34.000
newspapers everywhere. They're actually not

0:02:34.000,0:02:37.000
attributed to - apparently, to the Japanese, but it apparently got a lot more popular

0:02:37.000,0:02:40.000
under its Japanese name than it did under the original

0:02:40.000,0:02:41.000
English name for it.

0:02:41.000,0:02:44.000
And the goal of a sudoku, if you haven't ever done one, right, is it's

0:02:44.000,0:02:48.000
a nine by nine grid in which you're trying to place numbers,

0:02:48.000,0:02:51.000
and the requirement for the numbers is such that

0:02:51.000,0:02:53.000
within any particular row,

0:02:53.000,0:02:56.000
or any particular column, or any particular block, which is a three by

0:02:56.000,0:02:58.000
three subsection of that,

0:02:58.000,0:03:00.000
the numbers one through nine each appear once.

0:03:00.000,0:03:02.000
So you can never have more than two ones in a row,

0:03:02.000,0:03:04.000
two twos in a column,

0:03:04.000,0:03:06.000
three threes in a block, or anything like that.

0:03:06.000,0:03:09.000
And so there has to be some rearrangement, or, in fact,

0:03:09.000,0:03:11.000
permutation

0:03:11.000,0:03:14.000
of the numbers one through nine in each row, in each column, and each block,

0:03:14.000,0:03:17.000
such that the whole puzzle kind of works out logically.

0:03:17.000,0:03:22.000
So when it's given to you, you know, usually some fraction of the

0:03:22.000,0:03:23.000
slots are already filled in,

0:03:23.000,0:03:27.000
and the goal for you is to fill in those remaining slots without violating any of

0:03:27.000,0:03:29.000
these rules. Now

0:03:29.000,0:03:33.000
the sort of pure sudoku solvers

0:03:33.000,0:03:35.000
don't really use guessing.

0:03:35.000,0:03:37.000
It's considered, actually, poor form,

0:03:37.000,0:03:39.000
you know, that you're supposed to actually logically work it out by constraints

0:03:39.000,0:03:43.000
about what has to be true here versus what has to be true there to kind of

0:03:43.000,0:03:44.000
realize that

0:03:44.000,0:03:46.000
- what choices you have. We're

0:03:46.000,0:03:48.000
actually not gonna be a pure,

0:03:48.000,0:03:51.000
artistic, you know, sudoku solver. What we're gonna do is we're actually gonna use a brute force

0:03:51.000,0:03:54.000
recursive algorithm that's just gonna try recursive backtracking, which is to

0:03:54.000,0:03:55.000
say,

0:03:55.000,0:03:56.000
make an assignment,

0:03:56.000,0:03:59.000
be optimistic about it, and if it works out, great, and if not,

0:03:59.000,0:04:02.000
we'll eventually come back to that decision and revisit it.

0:04:02.000,0:04:04.000
So what we have here basically is a big decision problem.

0:04:04.000,0:04:06.000
You know, of the

0:04:06.000,0:04:08.000
81 squares on here,

0:04:08.000,0:04:10.000
you know, about 50 of them, right, need to be

0:04:10.000,0:04:12.000
chosen.

0:04:12.000,0:04:15.000
For each of those 50 squares, right, we're gonna do them one at a time and recur

0:04:15.000,0:04:19.000
on the remaining ones. So, you know, choose one then we'll just go left to right from the

0:04:19.000,0:04:20.000
top.

0:04:20.000,0:04:23.000
Choose that one at the top, make an assignment that works, and so that's what

0:04:23.000,0:04:26.000
we'll use the context we have in problem here. So, for example, if you look at

0:04:26.000,0:04:28.000
this first row,

0:04:28.000,0:04:31.000
there's a one in this column so we can't use one. There's

0:04:31.000,0:04:33.000
a two in that block so we can't use two,

0:04:33.000,0:04:37.000
but there's not a three in either that row, or that column, or that block, so we'll say, well, three looks good, you

0:04:37.000,0:04:39.000
know, just trying the numbers in order.

0:04:39.000,0:04:43.000
We'll be optimistic, say that works, and say, well if we planted a three here, could

0:04:43.000,0:04:46.000
we recursively solve the remaining 49 holes

0:04:46.000,0:04:48.000
and work it out?

0:04:48.000,0:04:49.000
And so

0:04:49.000,0:04:51.000
we get to that next one - we look at this one and say, okay, well

0:04:51.000,0:04:53.000
we could put a one here,

0:04:53.000,0:04:57.000
right, because there's not a one in this column, not a one in that row, not a one in

0:04:57.000,0:05:01.000
that block, so we'll kind of move on. I'm gonna do a little demo of that for you. And maybe it's

0:05:01.000,0:05:05.000
to kind of keep moving our way across, and only when

0:05:05.000,0:05:06.000
we get to a dead end

0:05:06.000,0:05:08.000
based on some of our earlier decisions will we unmake

0:05:08.000,0:05:10.000
and come back. So

0:05:10.000,0:05:15.000
let me - okay.

0:05:15.000,0:05:20.000
So that's the same set of numbers there. So I put the three up in the corner.

0:05:20.000,0:05:20.000


0:05:20.000,0:05:23.000
And so it puts the one here thinking, okay, that looks good. So it gets to the

0:05:23.000,0:05:25.000
next square over here

0:05:25.000,0:05:26.000
and then

0:05:26.000,0:05:29.000
the one can't be used because it's actually already in use both in that column and

0:05:29.000,0:05:33.000
in the row we're building so far, but two can be used. Two doesn't conflict with anything we

0:05:33.000,0:05:34.000
have so far.

0:05:34.000,0:05:36.000
And so it just keeps going optimistically,

0:05:36.000,0:05:39.000
right? At that stage over there it turns out almost all the numbers are in

0:05:39.000,0:05:43.000
use. Most of the numbers all the way up through seven and nine are there, and seven's

0:05:43.000,0:05:46.000
in its column. So, in fact, the only number that that could possibly be is nine, so

0:05:46.000,0:05:49.000
the only choice we have here to try is nine,

0:05:49.000,0:05:51.000
and then we'll place the seven next

0:05:51.000,0:05:54.000
to it. And so now we have a whole row that doesn't conflict with any of its blocks this

0:05:54.000,0:05:56.000
way, and then we just keep moving on, right,

0:05:56.000,0:05:57.000
so that is to keep kind of

0:05:57.000,0:05:59.000
going from top to bottom, left to right.

0:05:59.000,0:06:01.000
We'll place that four. We'll

0:06:01.000,0:06:04.000
place another one. Place a three.

0:06:04.000,0:06:07.000
So it's actually choosing them - it's actually going in order from one to nine just picking

0:06:07.000,0:06:09.000
the first one that fits,

0:06:09.000,0:06:11.000
right, so

0:06:11.000,0:06:13.000
when we get to the next square here, right,

0:06:13.000,0:06:17.000
it can't use one, it can't use two, it can't use three, it can't use four, it can't use five because they're all in

0:06:17.000,0:06:18.000
that row. It can't

0:06:18.000,0:06:20.000
use six because it's in the column. It

0:06:20.000,0:06:22.000
can't use seven

0:06:22.000,0:06:24.000
because it's in that row, but it should be able to use eight,

0:06:24.000,0:06:26.000
and so it'll place an eight there.

0:06:26.000,0:06:29.000
So it just kind of examines them in sequence until it finds the first one that

0:06:29.000,0:06:32.000
doesn't violate any things already decided,

0:06:32.000,0:06:35.000
and then kind of moves optimistically forward.

0:06:35.000,0:06:38.000
So about this point, right, we're doing pretty well, but we're starting to

0:06:38.000,0:06:40.000
run into some troubles if you look at

0:06:40.000,0:06:42.000
the next one over here.

0:06:42.000,0:06:44.000
It'll place the six there,

0:06:44.000,0:06:46.000
but then it will -

0:06:46.000,0:06:50.000
once the six is placed there, then it looks to the right and it says, oh, I need to put a

0:06:50.000,0:06:52.000
nine there. That's the only number left. It tries all the numbers one, two,

0:06:52.000,0:06:53.000
three, four,

0:06:53.000,0:06:55.000
and it says that isn't gonna work.

0:06:55.000,0:06:59.000
And so it actually fails on the rightmost column,

0:06:59.000,0:07:02.000
which causes it to back up to the one right before and it says, well, why don't you try

0:07:02.000,0:07:05.000
something else here? Well, it looks at seven, eight, and nine, none of those can work either,

0:07:05.000,0:07:07.000
so it's actually gonna back up even further

0:07:07.000,0:07:10.000
and then say, well what if we try to put a nine here? That also doesn't work. So now it's

0:07:10.000,0:07:14.000
gonna start seeing that it's kind of unwinding as the constraints we have made have kind of

0:07:14.000,0:07:17.000
got us down a dead end and it's slowly working its way back out to where the

0:07:17.000,0:07:21.000
original bad decision was made.

0:07:21.000,0:07:24.000
So it tries again on moving nine in here, and moving across, right,

0:07:24.000,0:07:26.000
but again, kind of,

0:07:26.000,0:07:27.000


0:07:27.000,0:07:30.000
you know, working its way forward but then kind of backing its way up. And

0:07:30.000,0:07:32.000
let me go ahead

0:07:32.000,0:07:37.000
and just run it faster so you can kind of see it.

0:07:37.000,0:07:41.000
But, you know, it's working on that row for a while, but essentially to note that the top row stays

0:07:41.000,0:07:44.000
relatively constant. It kind of believes that, well, that first three must have been good because, you

0:07:44.000,0:07:47.000
know, we're getting somewhere on that, and it keeps kind of going. You can see

0:07:47.000,0:07:50.000
that the activity is kind of always at the kind of

0:07:50.000,0:07:54.000
tail end of that decision making, which eventually, right,

0:07:54.000,0:07:56.000
worked its way out. And so it turns out, like, those three ones that we did put in the

0:07:56.000,0:07:59.000
first spots were fine.

0:07:59.000,0:08:01.000
That is, choices, right, it did work out.

0:08:01.000,0:08:04.000
We didn't know that when we started, right, but it was optimistic, right, it put it down

0:08:04.000,0:08:05.000
and then kept moving, and

0:08:05.000,0:08:08.000
then eventually, right,

0:08:08.000,0:08:12.000
worked out how the other things that had to get placed to make the whole puzzle

0:08:12.000,0:08:13.000
be solvable.

0:08:13.000,0:08:18.000
And so this thing can solve, actually, any solvable sudoku, right, and if it's not animating,

0:08:18.000,0:08:19.000
instantaneously,

0:08:19.000,0:08:21.000
even though it is really doing it in a fairly crude way,

0:08:21.000,0:08:24.000
right, it's basically just trying everything it can,

0:08:24.000,0:08:27.000
moving forward, and only when it kind of reaches a contradiction

0:08:27.000,0:08:30.000
based on some of those choices that they will - that can't possibly be because at

0:08:30.000,0:08:33.000
this point I'm forced into a situation where there's nothing that works in this

0:08:33.000,0:08:33.000
square,

0:08:33.000,0:08:36.000
so it must be that some earlier decision was wrong.

0:08:36.000,0:08:39.000
And you notice that when it backs up, it backs up to the most immediate decision.

0:08:39.000,0:08:42.000
So if you think of it in terms of recursive call, here's your first decision, your second

0:08:42.000,0:08:44.000
decision, your third decision, your fourth decision, your fifth decision. If you get down

0:08:44.000,0:08:47.000
here and you're, like, trying to make your eighth decision,

0:08:47.000,0:08:49.000
and there's nothing that works, right,

0:08:49.000,0:08:53.000
the decision that you come back to will be your seventh one. The one right

0:08:53.000,0:08:56.000
before it. You don't go throw everything away and start over. You don't go all the way

0:08:56.000,0:08:59.000
back to the beginning and say, oh, well that didn't work, let's try again.

0:08:59.000,0:09:01.000
It's that you actually use the kind of context to say, well,

0:09:01.000,0:09:04.000
the last decision I made was probably the one that needs a little fixing. Let me

0:09:04.000,0:09:08.000
just back right up to that one. That's the way the calls unwind, and it says we'll pick up

0:09:08.000,0:09:11.000
trying some other options there. Which ones have we not tried on that one? And

0:09:11.000,0:09:15.000
then go forward again, and again, if you get down to that eighth decision and you're still

0:09:15.000,0:09:18.000
stuck, you come back to the seventh decision again, and only after kind of the seventh decision

0:09:18.000,0:09:21.000
has gone back and forth with the eighth unsuccessfully

0:09:21.000,0:09:25.000
through all its options would we eventually return to that sixth decision, and

0:09:25.000,0:09:29.000
potentially back to the fifth, and fourth, and so on.

0:09:29.000,0:09:31.000
The code for this guy,

0:09:31.000,0:09:32.000


0:09:32.000,0:09:36.000
a little abstracted

0:09:36.000,0:09:39.000
that should very much fit the pattern of what you think recursive backtracking

0:09:39.000,0:09:40.000
looks like, and then the kind of

0:09:40.000,0:09:43.000
sort of goofier parts that are about, well, what does it mean to test a

0:09:43.000,0:09:47.000
sudoku for being a sign of having conflicts is actually then

0:09:47.000,0:09:50.000
passed out into these helper functions that manage the more

0:09:50.000,0:09:52.000
domain specific parts of the problem.

0:09:52.000,0:09:55.000
So at the very beginning it's like, find an unassigned location on the grid, and

0:09:55.000,0:09:58.000
it returns the row and column by reference. It turns out in this case

0:09:58.000,0:10:01.000
those are reference parameters. So [inaudible] searches from top to bottom to find the

0:10:01.000,0:10:05.000
first slot that actually does not have a value currently in it.

0:10:05.000,0:10:08.000
If it never finds one, so exhaustively searched the grid and didn't find one, then it

0:10:08.000,0:10:11.000
must be that we have a working sudoku because we never put a number in

0:10:11.000,0:10:17.000
unless it worked for us, and so if we've managed to assign them all, we're done.

0:10:17.000,0:10:19.000
If this didn't return true,

0:10:19.000,0:10:21.000
that meant it found one, and it assigned them a row and column,

0:10:21.000,0:10:24.000
and then what we're gonna go through the process of is assigning that row and

0:10:24.000,0:10:24.000
column.

0:10:24.000,0:10:26.000
So we look at the numbers one through nine.

0:10:26.000,0:10:28.000
If there are no conflicts for that number,

0:10:28.000,0:10:32.000
so it doesn't conflict with the row, column, or block,

0:10:32.000,0:10:35.000
that number isn't already in use in one of those places, then we go ahead and make

0:10:35.000,0:10:36.000
the assignment,

0:10:36.000,0:10:40.000
and then we see if we can solve it from here. So having updated the grid

0:10:40.000,0:10:42.000
to show that new number's in play,

0:10:42.000,0:10:46.000
you know, if we move on, the next [inaudible] of sudoku will then do a

0:10:46.000,0:10:50.000
search for find unassigned location. This time the one that we previously found, right,

0:10:50.000,0:10:52.000
has been assigned, so it actually won't get triggered on that one.

0:10:52.000,0:10:55.000
It'll look past it further down into the puzzle,

0:10:55.000,0:10:57.000
and eventually either find

0:10:57.000,0:11:00.000
the next one to make a call on, and kind of work its way through, or to - you have to

0:11:00.000,0:11:02.000
solve the whole thing.

0:11:02.000,0:11:06.000
If it didn't work, so we made that assignment to the number nine, and we went to solve,

0:11:06.000,0:11:07.000
and eventually this

0:11:07.000,0:11:11.000
tried all its possibilities from here and nothing came up good, then this

0:11:11.000,0:11:13.000
unassigned

0:11:13.000,0:11:15.000
constant is used to unmake that decision,

0:11:15.000,0:11:18.000
and come back around, and try

0:11:18.000,0:11:21.000
assigning it a different number. If we try all of our examples, so for

0:11:21.000,0:11:25.000
example, if we never find one that doesn't already conflict, or

0:11:25.000,0:11:29.000
if we try each one and it comes back false, right, that this return false here is

0:11:29.000,0:11:30.000
what's triggering

0:11:30.000,0:11:33.000
the backtracking up to the previous recursive call

0:11:33.000,0:11:37.000
to reconsider some earlier decision - the most recent early decision

0:11:37.000,0:11:38.000
for this one,

0:11:38.000,0:11:40.000
and say that was really our mistake, right,

0:11:40.000,0:11:42.000
we've got to unmake that one.

0:11:42.000,0:11:45.000
So it should look like kind of all the recursive backtracking all through looks the same,

0:11:45.000,0:11:47.000
right? You know, if

0:11:47.000,0:11:48.000
we're at the end,

0:11:48.000,0:11:49.000
here's our base cases

0:11:49.000,0:11:53.000
for all our options. If we can make this choice, make it, try to solve it, be

0:11:53.000,0:11:56.000
optimistic, if it works out, return.

0:11:56.000,0:11:59.000
Otherwise, unmake it, allow the loop to iterate a

0:11:59.000,0:12:02.000
few more times trying again. If all of those things

0:12:02.000,0:12:06.000
fail to find a solution then that return false here will cause the backtracking

0:12:06.000,0:12:12.000
out of this decision. I just let it

0:12:12.000,0:12:15.000
become constant. You know, I made it up. I used negative one, in fact,

0:12:15.000,0:12:16.000
just to know that

0:12:16.000,0:12:20.000
it has no contents.

0:12:20.000,0:12:26.000
Just specific to sudoku in this case. Now would be a great time

0:12:26.000,0:12:30.000
to ask a question. You guys kind of have that sort of half-okay

0:12:30.000,0:12:34.000
look on your face. It could be I'm totally bored. It could be I'm totally lost. Where do row and column

0:12:34.000,0:12:35.000
get assigned? So they

0:12:35.000,0:12:38.000
- finding assigned location takes [inaudible] reference.

0:12:38.000,0:12:41.000
So if you look at the full code for this - this is actually in the handout I gave out last time, and so

0:12:41.000,0:12:44.000
there's a pass by reference in that function, and it returns true if it assigned

0:12:44.000,0:12:46.000
them something, and then they have the

0:12:46.000,0:12:49.000
coordinates of that

0:12:49.000,0:12:51.000
unassigned location. Question over here. How'd you know

0:12:51.000,0:12:55.000
to write sol sudoku as a bool rather than as, like, a void function? Well, in this

0:12:55.000,0:12:57.000
case - that's a great question, right,

0:12:57.000,0:13:01.000
in most cases in recursive backtracking I am trying to

0:13:01.000,0:13:05.000
discover the success or failure of an operation, and so that's a good way to tell

0:13:05.000,0:13:07.000
because otherwise I need to know did it work.

0:13:07.000,0:13:10.000
And so if I made it void then there had to be some other way I figured it out. Maybe,

0:13:10.000,0:13:13.000
you know, that you have to check the grid when you're done and see that it has - no longer has

0:13:13.000,0:13:16.000
any unassigned locations, but the bool is actually just the easiest way to get that

0:13:16.000,0:13:17.000
information out.

0:13:17.000,0:13:19.000
So typically your recursive backtracking machine

0:13:19.000,0:13:21.000
will probably return something.

0:13:21.000,0:13:22.000


0:13:22.000,0:13:25.000
Often it's a true or false. It could be, you know, in some other case, just some other

0:13:25.000,0:13:27.000
good know value, and some other

0:13:27.000,0:13:31.000
sentinel that says, you know, bad value. So, for example, in the finding an anagram of the

0:13:31.000,0:13:34.000
words it might be that it returned the word if it found one, or returned an empty string if

0:13:34.000,0:13:36.000
it didn't. So using some sort of state that says

0:13:36.000,0:13:39.000
here's how - if you made the call, you'll know whether it worked because we

0:13:39.000,0:13:40.000
really do need to know.

0:13:40.000,0:13:44.000
Make the call and find out whether it worked. Well, how are we gonna find out? One of the best ways to

0:13:44.000,0:13:47.000
get that information is from a return value. Way in

0:13:47.000,0:13:52.000
the back? Exactly does the return calls trigger in the backtracking

0:13:52.000,0:13:52.000
[inaudible]?

0:13:52.000,0:13:56.000
So think about this as that, you know, it's hard to think about because you have to kind of have kind of

0:13:56.000,0:13:58.000
both sides of the recursion in your head, but

0:13:58.000,0:14:00.000
when - let's say we're on

0:14:00.000,0:14:02.000
the fifth decision, right?

0:14:02.000,0:14:05.000
We make the call to solve the sudoku that's gonna look at the sixth

0:14:05.000,0:14:06.000
decision, right?

0:14:06.000,0:14:10.000
If the sixth decision fails, it says, I looked at all my choices and none of them

0:14:10.000,0:14:11.000
worked, right?

0:14:11.000,0:14:12.000
It's that

0:14:12.000,0:14:15.000
that causes the fifth decision to say, well I - here go solve for the sixth decision

0:14:15.000,0:14:18.000
down. Well the sixth decision came back with a false. It got to this case after

0:14:18.000,0:14:19.000
trying all its options,

0:14:19.000,0:14:23.000
then it's the fifth decision that then says, okay, well then I'd better unmake the decision I

0:14:23.000,0:14:24.000
made and try again.

0:14:24.000,0:14:28.000
And so at any given stage you can think about the caller and the callee, it's saying,

0:14:28.000,0:14:31.000
I'm making a decision. You tell me if you can make it work from here.

0:14:31.000,0:14:35.000
If the delegate that you passed on the smaller form of the recursive problem comes

0:14:35.000,0:14:39.000
back with a return false, and then I've tried everything I could possibly do, but

0:14:39.000,0:14:42.000
there was no way. The situation you gave me was unworkable.

0:14:42.000,0:14:46.000
And that says, oh, okay, well you know what, it must have been my fault, right? I put

0:14:46.000,0:14:49.000
the wrong number in my box. Let me try a different number and now you try again.

0:14:49.000,0:14:52.000
And so they're constantly kind of these - you have to keep active in your mind the

0:14:52.000,0:14:52.000
idea

0:14:52.000,0:14:55.000
that there's this whole chain of these things being stacked up, each of them

0:14:55.000,0:14:59.000
being optimistic and then delegating down. And if your delegate comes back

0:14:59.000,0:15:00.000
with the -

0:15:00.000,0:15:02.000
there was nothing I could do,

0:15:02.000,0:15:06.000
then you have to revisit your earlier optimistic decision, unmake it, and

0:15:06.000,0:15:07.000
try again.

0:15:07.000,0:15:09.000
And so

0:15:09.000,0:15:12.000
that - this is the return false to the outer call,

0:15:12.000,0:15:16.000
the one that made the solved call

0:15:16.000,0:15:17.000
that unwinds from.

0:15:17.000,0:15:21.000
Way over here? [Inaudible]?

0:15:21.000,0:15:26.000
Pretty much any recursive piece of thing can be reformed into a backtracking form, right?

0:15:26.000,0:15:29.000
You need to - to do a little bit like the [inaudible] we tried last time,

0:15:29.000,0:15:32.000
we'll take a void returning thing and make it return some true or false, and there's kind of,

0:15:32.000,0:15:36.000
like, make a decision and be optimistic, see if it worked out.

0:15:36.000,0:15:40.000
But that kind of rearrangement of the code should work with pretty much all

0:15:40.000,0:15:43.000
your standard recursion stuff. So any kind of puzzle that actually,

0:15:43.000,0:15:46.000
like, all these kind of jumble puzzles, and crossword puzzles, and things

0:15:46.000,0:15:48.000
that involve kind of choosing, right,

0:15:48.000,0:15:52.000
can be solved with recursive backtracking. It's not necessarily the fastest, right, way

0:15:52.000,0:15:56.000
to get to a solution, but it will exhaustively try all the options until

0:15:56.000,0:16:00.000
a sequence of decisions, right, leads you to a goal if there is a goal to be found.

0:16:00.000,0:16:03.000
And so that if you can think of it as - if you can think of your problem as a

0:16:03.000,0:16:04.000
decision problem -

0:16:04.000,0:16:07.000
I need to make some decisions, and then from there make some more decisions and so

0:16:07.000,0:16:09.000
on, and eventually, right, I will bottom out

0:16:09.000,0:16:11.000
either at a goal or dead end,

0:16:11.000,0:16:14.000
then you can write a recursive problem solving -

0:16:14.000,0:16:18.000
backtracker to solve it. Way in

0:16:18.000,0:16:23.000
the back? This doesn't have anything to do with recursion, but how did you slow down the simulation? How did I slow it down? I'm just using pause. There's a pause

0:16:23.000,0:16:28.000
function in our stenographics library, and you just give it a time. You say one second, half a second, and

0:16:28.000,0:16:29.000
just - I

0:16:29.000,0:16:31.000
use that a lot in our demos, for example, for the maze, so that you can actually see what's

0:16:31.000,0:16:35.000
going on, and that way it just animates a little more. Stenographics, CSTgraph.h. [Inaudible] me

0:16:35.000,0:16:42.000
show you

0:16:42.000,0:16:43.000
one more

0:16:43.000,0:16:45.000
kind

0:16:45.000,0:16:47.000
of just in the same theme. The idea of taking

0:16:47.000,0:16:50.000
sort of some, you know, puzzle that somebody might give you,

0:16:50.000,0:16:53.000
trying to cast it in terms of a decision problem, right, where you make decisions

0:16:53.000,0:16:55.000
and then you move on,

0:16:55.000,0:16:58.000
can I solve something like these little cryptographic puzzles?

0:16:58.000,0:17:01.000
So here's send plus more equals money.

0:17:01.000,0:17:03.000
I've got eight

0:17:03.000,0:17:08.000
digits in there - eight letters in there. You know, D E M N O R S

0:17:08.000,0:17:10.000
Y across all of them,

0:17:10.000,0:17:13.000
and the goal of this puzzle is to assign these letters -

0:17:13.000,0:17:17.000
eight letters to the digits zero through nine without replacement

0:17:17.000,0:17:18.000
so that

0:17:18.000,0:17:21.000
if D's assigned to three, it's assigned to three in all places. For example, O shows up

0:17:21.000,0:17:24.000
two places in the puzzle. Both of those are either a two or both are three.

0:17:24.000,0:17:27.000
There's not one that's one and one that's another. And each

0:17:27.000,0:17:33.000
digit is used once. So, like, if I assigned two to O, then I will not assign two to D. So

0:17:33.000,0:17:35.000
what we've got here is eight letters.

0:17:35.000,0:17:38.000
We've got 10 digits.

0:17:38.000,0:17:41.000
We want to make an assignment.

0:17:41.000,0:17:44.000
What we've got here is some choices. The choices are,

0:17:44.000,0:17:48.000
for each letter, what digit are we gonna map it to?

0:17:48.000,0:17:51.000
Another way to think about it is if you took these eight letters, and then you

0:17:51.000,0:17:53.000
attach two dashes on the end,

0:17:53.000,0:17:56.000
then you considered that the letter's position in the string was - the index

0:17:56.000,0:17:58.000
of it was its digit.

0:17:58.000,0:18:00.000
It's really just like trying the permutations,

0:18:00.000,0:18:02.000
right, rearranging those

0:18:02.000,0:18:06.000
letters in any of those sequences. So right now, for example, maybe D is assigned

0:18:06.000,0:18:09.000
zero, and one, and two, and so on, and these guys are eight, nine. Well, if

0:18:09.000,0:18:12.000
you rearrange the letters into some other permutation then you've made a

0:18:12.000,0:18:13.000
different assignment.

0:18:13.000,0:18:16.000
So in effect, right, what you're looking at is a problem that has a lot in common with

0:18:16.000,0:18:17.000
permutations, right?

0:18:17.000,0:18:21.000
I'm gonna make an assignment, take a letter off, decide what index it's gonna

0:18:21.000,0:18:24.000
be placed at, so it's kind of like deciding where it would go in the permutation,

0:18:24.000,0:18:27.000
and then that leaves us with a smaller form of the problem

0:18:27.000,0:18:30.000
which has one fewer letters to be assigned,

0:18:30.000,0:18:33.000
and then recursively explore the options from there to see if we can make

0:18:33.000,0:18:37.000
something that makes the addition add up correctly that D plus E equals Y

0:18:37.000,0:18:37.000
means that

0:18:37.000,0:18:39.000
if D was assigned five,

0:18:39.000,0:18:43.000
and E was three, then Y better be eight for this to work out.

0:18:43.000,0:18:47.000
So the first form I'm gonna show you is actually just the dumb,

0:18:47.000,0:18:49.000
exhaustive recursive backtracking

0:18:49.000,0:18:53.000
that works very much like the sudoku problem where it just - it finds the next unassigned

0:18:53.000,0:18:57.000
letter, it assigns it a digit of the next auto sign digits, right, and then just

0:18:57.000,0:18:59.000
optimistically figures that'll work out.

0:18:59.000,0:19:02.000
After it makes an assignment for all the letters it says,

0:19:02.000,0:19:07.000
take the puzzle, convert all the letters into their digit equivalents, and see if it adds

0:19:07.000,0:19:08.000
together correctly.

0:19:08.000,0:19:10.000
If so, we're done. If not,

0:19:10.000,0:19:13.000
then let's backtrack.

0:19:13.000,0:19:16.000
So let me - I mean, actually, I'll show you

0:19:16.000,0:19:18.000
the code first

0:19:18.000,0:19:20.000
because it's actually quite easy to

0:19:20.000,0:19:21.000
take a look at.

0:19:21.000,0:19:25.000
Again, it has helper routines that kind of

0:19:25.000,0:19:29.000
try to abstract the pieces of the puzzle that actually aren't interesting

0:19:29.000,0:19:31.000
from kind of looking at just the core of the recursive algorithm, so it looks a

0:19:31.000,0:19:33.000
lot like sudoku

0:19:33.000,0:19:36.000
in that if letters do assign, so it actually keeps the string of the letters that

0:19:36.000,0:19:38.000
haven't yet been assigned.

0:19:38.000,0:19:41.000
If there are no more letters in that string, we take one off at each time we

0:19:41.000,0:19:42.000
assign it,

0:19:42.000,0:19:45.000
then we check and see if the puzzle's solved. So that kind of does the substitution, and does

0:19:45.000,0:19:48.000
the math, and comes back saying yes or no.

0:19:48.000,0:19:50.000


0:19:50.000,0:19:53.000
If it worked out, we'll get a true. If it didn't work out we get a false.

0:19:53.000,0:19:57.000
If we still have letters to assign then it goes through the process of making a choice, and

0:19:57.000,0:19:59.000
that choice is looking at the

0:19:59.000,0:20:00.000


0:20:00.000,0:20:04.000
digits zero through nine if we can assign it. So looking at that first letter in

0:20:04.000,0:20:07.000
that digit, and then that's making sure that we don't already have an assignment for

0:20:07.000,0:20:10.000
that letter, that we don't have an assignment for that digit. Sort of make sure that just the

0:20:10.000,0:20:12.000
constraints of the problem are being met.

0:20:12.000,0:20:14.000
If we're able to make that assignment

0:20:14.000,0:20:16.000
then we go ahead and make a recursive call,

0:20:16.000,0:20:18.000
having one fewer letters

0:20:18.000,0:20:20.000
to make a decision for, and

0:20:20.000,0:20:23.000
if that worked out true, otherwise we do an unassignment and come back around

0:20:23.000,0:20:24.000
that loop

0:20:24.000,0:20:27.000
and then eventually the same return false at the bottom, which said, well

0:20:27.000,0:20:31.000
given the previous assignments of the letters before we got to this call,

0:20:31.000,0:20:33.000
there was nothing I could do from here

0:20:33.000,0:20:36.000
to make this work out. So

0:20:36.000,0:20:40.000
let me show you this guy working because you're gonna see that it is actually

0:20:40.000,0:20:42.000
a crazy way to try to solve this problem

0:20:42.000,0:20:45.000
in terms of what you know about

0:20:45.000,0:20:48.000
stuff. So I say C S plus U equals fun,

0:20:48.000,0:20:54.000
a well-known equation.

0:20:54.000,0:20:57.000
So I did this little animation to try to get you visualized what's going on at any

0:20:57.000,0:20:59.000
given stage.

0:20:59.000,0:21:00.000
So

0:21:00.000,0:21:03.000
it has the letters down across the bottom, S U N C O Y F.

0:21:03.000,0:21:06.000
That's the string of letters to assign.

0:21:06.000,0:21:08.000
It's gonna assign it the next available digit

0:21:08.000,0:21:11.000
when it makes that recursive call, so the first recursive call is

0:21:11.000,0:21:12.000
gonna be about assigning S,

0:21:12.000,0:21:16.000
and then the next call will be assign U, and the next call - and so on. So it always

0:21:16.000,0:21:18.000
gets up to seven deep

0:21:18.000,0:21:19.000
on any particular thing.

0:21:19.000,0:21:21.000
And so it says, okay, well

0:21:21.000,0:21:25.000
first digit available is zero, go ahead and assign that to S. So it's gonna make a

0:21:25.000,0:21:28.000
call there. And then it says, okay, well look at U. Well we can't use

0:21:28.000,0:21:33.000
zero because zero's already in use. What don't we assign U to be one? Okay. Sounds good. Keep going. And

0:21:33.000,0:21:36.000
then it'll say, okay, let's get to N. Let's make an assignment for N. It says I'll look around.

0:21:36.000,0:21:40.000
Okay, well zero's in use, one's in use, how about two? Okay. Good.

0:21:40.000,0:21:41.000
And then it assigns

0:21:41.000,0:21:44.000
this to three, this to four, this to five,

0:21:44.000,0:21:47.000
and this to six. Okay. It gets to here and it says,

0:21:47.000,0:21:48.000
hey, does that work,

0:21:48.000,0:21:50.000
30 plus 541 equals

0:21:50.000,0:21:52.000
612? No?

0:21:52.000,0:21:55.000
Okay. Well, you know what the problem was? It was F,

0:21:55.000,0:22:01.000
right? I assigned F to six. How stupid of me. It can't be six. Let's make it seven.

0:22:01.000,0:22:02.000


0:22:02.000,0:22:05.000
And then it says, oh, oh no, oh I'm sorry. I'm sorry, 30 plus 541 that's not

0:22:05.000,0:22:07.000
712. How silly.

0:22:07.000,0:22:09.000
I need to assign F to be eight.

0:22:09.000,0:22:11.000
And it's gonna do this for a little while.

0:22:11.000,0:22:12.000
A long while [inaudible].

0:22:12.000,0:22:13.000
And then it says, oh, okay. Well,

0:22:13.000,0:22:17.000
you know what, given the letters you'd assigned to the first six things, when you got to

0:22:17.000,0:22:20.000
F, I tried everything I could and there was nothing I could do to fix this.

0:22:20.000,0:22:23.000
You know what the problem was? It's not me. It's not me. I'm not the problem. You're the

0:22:23.000,0:22:24.000
problem.

0:22:24.000,0:22:26.000
So it returns false

0:22:26.000,0:22:29.000
from this call at the bottom, having tried all its options,

0:22:29.000,0:22:31.000
which causes Y to say, oh, yeah, yeah,

0:22:31.000,0:22:36.000
I know. I know I said five. Did I said five? I didn't meant to say five. I meant to say six.

0:22:36.000,0:22:39.000
And so it moves up to the six option.

0:22:39.000,0:22:43.000
Again, optimistically saying that's good. Go for it. See what you can do.

0:22:43.000,0:22:44.000
So it picks five.

0:22:44.000,0:22:44.000
That won't work,

0:22:44.000,0:22:46.000
right? It picks seven. It's gonna

0:22:46.000,0:22:48.000
go for a long time, right, because it turns out, right,

0:22:48.000,0:22:52.000
this is one of those cases where that very first decision, that was one of your problems,

0:22:52.000,0:22:52.000
right?

0:22:52.000,0:22:54.000
If you assign S to be zero,

0:22:54.000,0:22:58.000
there's nothing you can assign U and N to be that are gonna work out.

0:22:58.000,0:23:01.000
So what it's gonna be going through is this process though of

0:23:01.000,0:23:05.000
having, you know, committed to this early decision and kind of moving on it's gonna try

0:23:05.000,0:23:10.000
every other variation over here before it gives up on that. So let me

0:23:10.000,0:23:13.000


0:23:13.000,0:23:16.000
set it to going.

0:23:16.000,0:23:22.000
Even though C S plus U does equal fun. I guarantee it. We'll

0:23:22.000,0:23:23.000
let it do some work for a while.

0:23:23.000,0:23:26.000
So those bars is they grow up are desperation.

0:23:26.000,0:23:29.000
You can think of that as, like, it's running out of options. It's running out of

0:23:29.000,0:23:30.000
time, you know, and it's like oh,

0:23:30.000,0:23:33.000
oh, wait, earlier, back up, back up. And so, okay, you can kind of see

0:23:33.000,0:23:36.000
how far its backed up but sort of how tall

0:23:36.000,0:23:40.000
some of the deeper recursive calls, right, the earlier ones in the sequence. And

0:23:40.000,0:23:41.000
so

0:23:41.000,0:23:44.000
it doesn't, you know, revisit any of these decisions because it's really busy over

0:23:44.000,0:23:47.000
here, but you can see that C is now up to seven.

0:23:47.000,0:23:49.000
It'll get up to eight. It'll get up to nine.

0:23:49.000,0:23:52.000
And that was when it will cause itself to say, you know, I tried everything that was

0:23:52.000,0:23:54.000
possible from C on down,

0:23:54.000,0:23:58.000
and there was no way to make this thing work out. It must be that the bad

0:23:58.000,0:24:00.000
decision was made earlier.

0:24:00.000,0:24:04.000
Let's back up and look at that. And so it'll come back to the decision N,

0:24:04.000,0:24:09.000
bump it up by one, and then go again. It's gonna do this a long time, right?

0:24:09.000,0:24:12.000
Go through all the options for N and its neighbors before it comes back and revisits

0:24:12.000,0:24:14.000
the U. It's gonna have to get U all the way up,

0:24:14.000,0:24:18.000
right, through having tried one, two, three, four. So adding zero to one, and two, and three,

0:24:18.000,0:24:19.000
and four,

0:24:19.000,0:24:21.000
and discovering it can never make a match over there

0:24:21.000,0:24:24.000
before it will eventually decide that the S

0:24:24.000,0:24:25.000
is really where

0:24:25.000,0:24:27.000
we got ourselves in trouble.

0:24:27.000,0:24:29.000
So this is kind of in its most naive

0:24:29.000,0:24:32.000
form, right? The recursive backtracking is doing basically permutations,

0:24:32.000,0:24:34.000
right? You can see this is actually just

0:24:34.000,0:24:37.000
permuting the digits as they're assigned to the numbers, and there are, in this

0:24:37.000,0:24:41.000
case, you know, seven factorial different ways that we can make this assignment,

0:24:41.000,0:24:45.000
and there are a lot of them that are wrong, right? It's not being at all clever

0:24:45.000,0:24:46.000
about

0:24:46.000,0:24:49.000
how to pick and choose among which to explore.

0:24:49.000,0:24:51.000
So in

0:24:51.000,0:24:52.000
its most naive form, right,

0:24:52.000,0:24:54.000
recursive backtracking can be very expensive because often you're looking

0:24:54.000,0:24:59.000
at things that have very high branching, and very long depth to them,

0:24:59.000,0:25:02.000
which can add up to a lot of different things tried.

0:25:02.000,0:25:04.000
Just using some simple - in this case, heuristics,

0:25:04.000,0:25:08.000
sort of information you know about the domain

0:25:08.000,0:25:11.000
can help you to guide your choices instead of just making the choices in order, trying the

0:25:11.000,0:25:14.000
numbers zero through nine as though they're equally likely,

0:25:14.000,0:25:16.000
or

0:25:16.000,0:25:19.000
kind of waiting to make all the assignments before you look at

0:25:19.000,0:25:21.000
anything to see if it's actually good. There's actually some ways we can kind of

0:25:21.000,0:25:24.000
shape our decision making to look at the most likely options before we look at

0:25:24.000,0:25:26.000
these more

0:25:26.000,0:25:30.000
first. Finding the problem instead of niggling around this dead end.

0:25:30.000,0:25:33.000
So I'm gonna let that guy work for a little bit

0:25:33.000,0:25:34.000
while I

0:25:34.000,0:25:36.000
show you another slide over here.

0:25:36.000,0:25:39.000
So what the smarter solver does,

0:25:39.000,0:25:43.000
is that it doesn't really consider all permutations equally plausible. We're

0:25:43.000,0:25:47.000
gonna use a little grade school addition knowledge. If I look at the rightmost column, the

0:25:47.000,0:25:49.000
least significant digit,

0:25:49.000,0:25:51.000
I'm gonna assign D first.

0:25:51.000,0:25:52.000
I assign D to zero. I assign

0:25:52.000,0:25:53.000
E to one,

0:25:53.000,0:25:54.000
and then I look at Y -

0:25:54.000,0:25:59.000
I don't try Y is five, or seven, or anything like that. I say there's

0:25:59.000,0:26:01.000
exactly one thing Y has to be, right, if

0:26:01.000,0:26:04.000
D is zero and E is one, then Y has to be one, and I can say, well that won't work

0:26:04.000,0:26:06.000
because I already used one for E.

0:26:06.000,0:26:07.000
So it'll say,

0:26:07.000,0:26:10.000
well that's impossible. Something must be wrong

0:26:10.000,0:26:13.000
early. Rather than keep going on this kind of dumb

0:26:13.000,0:26:15.000
dead end, it's to realize right away

0:26:15.000,0:26:18.000
that one of the decisions I've already made, D and E, has gotta be wrong. So it'll back up

0:26:18.000,0:26:22.000
to E. It'll try two, three, four, very quickly realizing

0:26:22.000,0:26:25.000
that of all the things you could assign to E, once you have assigned D to

0:26:25.000,0:26:29.000
zero, you're in trouble. And so it will quickly unmake that decision about D and work its way

0:26:29.000,0:26:30.000
down.

0:26:30.000,0:26:34.000
So using the kind of structure of the problem. So it makes it a little bit more

0:26:34.000,0:26:37.000
housekeeping about where I'm at, and what I'm doing, and

0:26:37.000,0:26:37.000


0:26:37.000,0:26:38.000
what's going on,

0:26:38.000,0:26:43.000
but it is using some real smarts about what part of the tree to explore,

0:26:43.000,0:26:45.000
rather than letting it kind of just go

0:26:45.000,0:26:49.000
willy nilly across the whole thing. Let me get that

0:26:49.000,0:26:52.000
out of the way. And I'll

0:26:52.000,0:27:00.000
run this one. I say C S plus U equals fun. Okay.

0:27:00.000,0:27:03.000
So it goes zero here, and

0:27:03.000,0:27:04.000
tries the one, and it

0:27:04.000,0:27:06.000
says no, that won't work. How about the two?

0:27:06.000,0:27:09.000
No, that won't work, right, because there's nothing you can assign the N that'll

0:27:09.000,0:27:13.000
make this work. And so it immediately is kind of failing on this,

0:27:13.000,0:27:16.000
and even after it tries kind of all nine of these, it

0:27:16.000,0:27:18.000
says none of these are looking good,

0:27:18.000,0:27:22.000
then it comes back to this decision and says, no, no, actually, S's a zero. That wasn't so

0:27:22.000,0:27:24.000
hot. How about we try S as one?

0:27:24.000,0:27:27.000
And then kind of works its way

0:27:27.000,0:27:32.000
further down.

0:27:32.000,0:27:34.000
Hello? Okay. So let me try this again. Let me get it

0:27:34.000,0:27:40.000
to just go. Okay.

0:27:40.000,0:27:42.000
So it took 30 assignments

0:27:42.000,0:27:44.000
- 30 different things it tried

0:27:44.000,0:27:47.000
before it was able to come up with 41 plus 582 equals 623,

0:27:47.000,0:27:49.000
which does add correctly.

0:27:49.000,0:27:53.000
It didn't have to unmake once it decided that S was one. It turns out that was a

0:27:53.000,0:27:57.000
workable solution so it didn't have to go very far once it made that commitment,

0:27:57.000,0:27:59.000
and then you can see it kind of working its way up.

0:27:59.000,0:28:03.000
So 30 assignments, right, across this tree that has, you know,

0:28:03.000,0:28:05.000
hundreds of thousands in the factorial, very large number,

0:28:05.000,0:28:08.000
but very quickly kind of pruning down those things that aren't worth looking

0:28:08.000,0:28:09.000
at, and

0:28:09.000,0:28:12.000
so focusing its attention on those things that are more likely to

0:28:12.000,0:28:14.000
work out using information about the problem.

0:28:14.000,0:28:17.000
It doesn't really change what the recursion does. It's kind of interesting if you

0:28:17.000,0:28:20.000
think that the same backtracking and recursive strategy's the same in all these

0:28:20.000,0:28:23.000
problems, but what you're trying to do is pick your options, like,

0:28:23.000,0:28:24.000
looking at the choices you have

0:28:24.000,0:28:28.000
and trying to decide what are the more likely ones, which ones are not worth trying, right, so

0:28:28.000,0:28:29.000
sort of directing

0:28:29.000,0:28:32.000
your decision making

0:28:32.000,0:28:33.000
from the

0:28:33.000,0:28:36.000
standpoint of trying to make sure you don't violate constraints that later will come

0:28:36.000,0:28:38.000
back to bite you, and things like that.

0:28:38.000,0:28:40.000


0:28:40.000,0:28:41.000
This one's back here.

0:28:41.000,0:28:43.000
It's at

0:28:43.000,0:28:47.000
13,000 and working hard. Getting desperate. Doing its thing. Still has not unmade the

0:28:47.000,0:28:52.000
decision about S is zero, so you can get an idea of how much longer it's gonna take. We'll

0:28:52.000,0:28:53.000
just let it keep going.

0:28:53.000,0:28:55.000
I'm in no hurry - and let

0:28:55.000,0:28:56.000
it

0:28:56.000,0:29:07.000
do its thing.

0:29:07.000,0:29:11.000
So let me - before I move away from talking about recursion, just try

0:29:11.000,0:29:12.000


0:29:12.000,0:29:15.000
to get you thinking just a little bit about how the patterns we're seeing,

0:29:15.000,0:29:16.000
right,

0:29:16.000,0:29:18.000
are more alike than they are different.

0:29:18.000,0:29:21.000
That solving a sudoku, solving the eight queens,

0:29:21.000,0:29:26.000
you know, solving the find an anagram in a sequence of letters, that

0:29:26.000,0:29:31.000
they all have this general idea of there being these decisions that you're making,

0:29:31.000,0:29:33.000
and you're working your way down to where there's, you know

0:29:33.000,0:29:37.000
- fewer and fewer of those decisions until eventually you end up, sort of, okay, I'm done. I've

0:29:37.000,0:29:41.000
made all the decisions I can. What letter goes next, or whether something goes in or out.

0:29:41.000,0:29:44.000
And the two problems that I call the kind of master or mother problems,

0:29:44.000,0:29:46.000
right, of permutations and subsets

0:29:46.000,0:29:49.000
are kind of fundamental to

0:29:49.000,0:29:52.000
adapting them to these other domains. And so I'm gonna give you a couple

0:29:52.000,0:29:55.000
examples of some things that come up that actually are just kind of permutations,

0:29:55.000,0:29:58.000
or subsets, or some variation that you can help me think about a little bit.

0:29:58.000,0:30:03.000
One that the CS people are fond of is this idea of knapsack feeling.

0:30:03.000,0:30:07.000
It's often cast as someone breaking into your house. All criminals at

0:30:07.000,0:30:09.000
heart apparently in computer science.

0:30:09.000,0:30:12.000
And you've got this sack, and you can put 50 pounds of stuff in it,

0:30:12.000,0:30:15.000
right, and you're looking around, you know, at all the stuff that's

0:30:15.000,0:30:18.000
up for grabs in this house that you've broken into,

0:30:18.000,0:30:22.000
and you want to try to pack your sack, right, so that you've got 50 pounds of the high value

0:30:22.000,0:30:23.000
stuff.

0:30:23.000,0:30:26.000
So let's say there's, like, 100 things, right, you could pick up, right,

0:30:26.000,0:30:29.000
and they weigh different amounts, and they're worth different amounts.

0:30:29.000,0:30:33.000
What's the strategy for going about finding the optimal

0:30:33.000,0:30:35.000
combination of things to stick into your sack, right,

0:30:35.000,0:30:38.000
so that you got the maximum value from your heist?

0:30:38.000,0:30:44.000
What problem does that look like that you've seen?

0:30:44.000,0:30:47.000
It's a subset. It's a subset. [Inaudible].

0:30:47.000,0:30:48.000
Right? So if you look at the,

0:30:48.000,0:30:52.000
you know, the Wii, and you say, oh, should I take the Wii? You know, it weighs this much, and it's this much

0:30:52.000,0:30:53.000
value, well

0:30:53.000,0:30:56.000
let's try it in and see what happens, right, and see what else I can stuff in the sack with

0:30:56.000,0:30:59.000
that, right, and then see how well that works out. I should also try it with it out.

0:30:59.000,0:31:02.000
So while you're standing there trying to decide what to

0:31:02.000,0:31:05.000
steal, you have to type in all the values of things in every computer program.

0:31:05.000,0:31:08.000
Go through the kind of machinations of well, try this with that because some things

0:31:08.000,0:31:10.000
are big, but have a lot of value,

0:31:10.000,0:31:13.000
but they only leave a little bit of odd space left over you might not be able to

0:31:13.000,0:31:15.000
use well, or something.

0:31:15.000,0:31:18.000
But what we're looking for is the optimal combination, the optimal subset. So

0:31:18.000,0:31:21.000
trying the different subsets tells you how much value and weight

0:31:21.000,0:31:25.000
you can get in a combination, and then you're looking for that best value you can get.

0:31:25.000,0:31:27.000
You're the traveling salesman.

0:31:27.000,0:31:29.000
You've got 10 cities to visit.

0:31:29.000,0:31:33.000
Boston, New York, Phoenix, Minneapolis, right?

0:31:33.000,0:31:36.000
You want to cover them in such a way that you spend the minimal amount of time,

0:31:36.000,0:31:40.000
you know, in painful air travel across the U.S. Well you certainly don't want to be

0:31:40.000,0:31:41.000
going

0:31:41.000,0:31:47.000
Boston, New York, right, like, Boston, to L.A., to New York, to Seattle, to

0:31:47.000,0:31:48.000
D.C.,

0:31:48.000,0:31:51.000
to Los Angeles back and forth, right? There's gotta be a pattern where you

0:31:51.000,0:31:55.000
kind of visit the close cities and work your way to the far cities to kind of

0:31:55.000,0:31:58.000
minimize your total distance overall.

0:31:58.000,0:32:02.000
What problem was that really in disguise? We've

0:32:02.000,0:32:06.000
got 10 cities. What are you trying to do?

0:32:06.000,0:32:08.000
Help me out a little. I hear it almost. Louder.

0:32:08.000,0:32:12.000
Permutations. You've got a permutation problem there, all right?

0:32:12.000,0:32:14.000
You got 10 cities. They all have to show up,

0:32:14.000,0:32:17.000
right? And it's a permutation. Where do you start, where do you end, where do you go in the

0:32:17.000,0:32:20.000
middle, right? What sequencing, right, do you need to take?

0:32:20.000,0:32:21.000
So what you're looking at is

0:32:21.000,0:32:24.000
try the permutations, tell me which ones come up short.

0:32:24.000,0:32:27.000
There are things, right, about heuristics that can help this, right?

0:32:27.000,0:32:28.000
So the idea that

0:32:28.000,0:32:31.000
certainly, like, the ones that are closer to you are likely to make a better

0:32:31.000,0:32:33.000
choice than the longer one. So kind of using

0:32:33.000,0:32:36.000
some information about the problem can help you decide which ones are more

0:32:36.000,0:32:40.000
promising avenues to explore. But in the end it's a permutation problem.

0:32:40.000,0:32:43.000
I'm trying to divide you guys into fair teams. I want to, you know, divide you up into

0:32:43.000,0:32:46.000
10 teams to have a kind of head-to-head programming competition. I happen to know

0:32:46.000,0:32:48.000
all your Iqs.

0:32:48.000,0:32:50.000
I don't know. Some other, you know, useless fact that

0:32:50.000,0:32:53.000
perhaps we could use as some judge of your worth.

0:32:53.000,0:32:54.000


0:32:54.000,0:32:58.000
And I want to make sure that each time has kind of

0:32:58.000,0:33:01.000
a fair amount of IQ power in it

0:33:01.000,0:33:03.000
relative to the others that I didn't put,

0:33:03.000,0:33:09.000
you know, all the superstars on one team. What am I doing? How do

0:33:09.000,0:33:12.000
I divide you guys up? It's a subset problem, right? So

0:33:12.000,0:33:14.000
if -

0:33:14.000,0:33:17.000
in this case it's a subset that's not just in or out. It's like which team am I gonna

0:33:17.000,0:33:21.000
put you in? So I've got 10 subsets to build. But in the end it's an in out

0:33:21.000,0:33:22.000
problem that looks like, well,

0:33:22.000,0:33:23.000
I have the next student.

0:33:23.000,0:33:27.000
Which of the 10 teams can I try them in? I can try them in each of them, right? So

0:33:27.000,0:33:30.000
in some sense it's trying in the first team, the second team, the third team,

0:33:30.000,0:33:32.000
right, and then pull the next student, try him in those teams,

0:33:32.000,0:33:35.000
and then see whether I can come up with something that appears to get a balance ratio when I'm

0:33:35.000,0:33:37.000
done.

0:33:37.000,0:33:41.000
It turns out you can take the letters from Richard Millhouse Dickson and you can

0:33:41.000,0:33:44.000
extract and rearrange them to spell the word criminal. I

0:33:44.000,0:33:48.000
am making no conclusion about anything, having done that,

0:33:48.000,0:33:48.000
just

0:33:48.000,0:33:50.000
an observation of fact.

0:33:50.000,0:33:51.000


0:33:51.000,0:33:55.000
But that sort of process, right, I'm trying to find, well what is the longest word

0:33:55.000,0:33:58.000
that you can extract from a sequence of letters?

0:33:58.000,0:34:05.000
What kind of things is it using?

0:34:05.000,0:34:13.000
Anything you've seen before?

0:34:13.000,0:34:18.000
Oh, somebody come on. I hear the whispering but no one wants to just stand up and be

0:34:18.000,0:34:20.000
committed.

0:34:20.000,0:34:23.000
How about

0:34:23.000,0:34:24.000
a

0:34:24.000,0:34:27.000
little of both, right? The what? Like the sudoku puzzle? It's a little bit like the sudoku, right? It's got a permutation sort of backing, and it's got a little bit of

0:34:27.000,0:34:29.000
a subset backing, right? That is that

0:34:29.000,0:34:32.000
I'm not choosing all the letters from this. And in fact there's a subset process,

0:34:32.000,0:34:35.000
which is deciding whether it's in or out, and then there's a permutation problem,

0:34:35.000,0:34:37.000
which is actually rearranging them, right?

0:34:37.000,0:34:40.000
That picking the C, and the R, and the I, and the M, and then kind of rearranging them. So in fact it

0:34:40.000,0:34:44.000
has kind of a little bit of both, right? Which is what sequence of letters can I

0:34:44.000,0:34:46.000
extract and then rearrange to make a word - would

0:34:46.000,0:34:50.000
end up using kind of elements of both of those kinds of recursions sort of

0:34:50.000,0:34:51.000
mixed together

0:34:51.000,0:34:55.000
so that when you look at a lot of recursion problems, they end up actually just mapping down to

0:34:55.000,0:34:59.000
one or the other, or maybe a little bit of both. And so feeling very comfortable with

0:34:59.000,0:35:00.000
those problems,

0:35:00.000,0:35:03.000
how you turn them into a recursive backtracker,

0:35:03.000,0:35:05.000
and how you can recognize, right,

0:35:05.000,0:35:08.000
their roots inside these other problems, it's kind of a really good first step to

0:35:08.000,0:35:12.000
becoming kind of a journeyman, in a way, or recursion.

0:35:12.000,0:35:14.000
So just whenever you see a new problem you start thinking, okay,

0:35:14.000,0:35:17.000
is it permutations? Is it subset? Or is it something totally new?

0:35:17.000,0:35:21.000
It's probably much more likely to be the first two then the third, and so

0:35:21.000,0:35:24.000
trying to use the ones that you feel really comfortable with to kind of branch

0:35:24.000,0:35:25.000
out to solve

0:35:25.000,0:35:29.000
similar problems, right, where the domain is a little different - the structure

0:35:29.000,0:35:35.000
of the code is still very much the same. All right.

0:35:35.000,0:35:37.000
I've got 10 minutes to teach you about pointers.

0:35:37.000,0:35:39.000
This should be no problem. Let's

0:35:39.000,0:35:42.000
go see what that guy back there's doing. Oh, look at

0:35:42.000,0:35:47.000
that, 38,000 assignments, still has not given up on that S is zero.

0:35:47.000,0:35:53.000
It's a trooper. Okay.

0:35:53.000,0:35:57.000
So this is definitely gonna be your first introduction on kind of the first

0:35:57.000,0:36:01.000
day of talking about this. This is not the only day. So

0:36:01.000,0:36:03.000
don't get to worried about me trying to do it in 10 minutes. What I'm gonna do is give you

0:36:03.000,0:36:07.000
the kind of - a little bit of the basics today, and we're gonna follow up with

0:36:07.000,0:36:10.000
some more stuff tomorrow where we start kind of making use of them and doing something

0:36:10.000,0:36:11.000
kind of interesting with them.

0:36:11.000,0:36:13.000
So there is this notion

0:36:13.000,0:36:17.000
in C++, which is inherited from the C language in fact,

0:36:17.000,0:36:20.000
of using a variable type called a pointer

0:36:20.000,0:36:22.000
as part of the things that you operate on.

0:36:22.000,0:36:26.000
Okay. People tend to have a lot of trepidation. Just the word pointer causes a little bit

0:36:26.000,0:36:28.000
of fear, kind of

0:36:28.000,0:36:30.000
to immediately rise in a new programmer.

0:36:30.000,0:36:34.000
But hopefully we can demystify a little bit, and then also get a little bit of understanding

0:36:34.000,0:36:38.000
of why there are reasons to be a little bit

0:36:38.000,0:36:40.000
wary of working with pointers.

0:36:40.000,0:36:42.000
A pointer is actually an address.

0:36:42.000,0:36:45.000
So here's a couple things we have to kind of think about a little bit how the

0:36:45.000,0:36:48.000
machine works to have a vision of what's going on here,

0:36:48.000,0:36:52.000
that when you declare variables, you

0:36:52.000,0:36:54.000
know, here I am in main.

0:36:54.000,0:36:56.000


0:36:56.000,0:36:58.000
And I declare,

0:36:58.000,0:37:02.000
you know, int Num,

0:37:02.000,0:37:04.000
and string S,

0:37:04.000,0:37:05.000
that there

0:37:05.000,0:37:09.000
is space set aside as part of the working memory of this program

0:37:09.000,0:37:13.000
that is gonna record whatever I assign to Num or S. So if I say Num equals

0:37:13.000,0:37:19.000
45, what is that? S equals hello, that there

0:37:19.000,0:37:20.000
has to be memory

0:37:20.000,0:37:22.000
that's being used to hold onto that.

0:37:22.000,0:37:27.000


0:37:27.000,0:37:28.000


0:37:28.000,0:37:32.000
And as you declare variables, right, more of the space is set aside, and, you know, when

0:37:32.000,0:37:36.000
you initialize it, when you read to it, when you write to it, right, that

0:37:36.000,0:37:40.000
space is being accessed and updated as you go through. When you open

0:37:40.000,0:37:44.000
a new scope, right, new variables come in a scope. When you close that scope, really that

0:37:44.000,0:37:47.000
function, that space gets de-allocated. All this happens on your behalf without you

0:37:47.000,0:37:50.000
actually taking a really active role in it, but in fact you do have to have a little

0:37:50.000,0:37:53.000
bit of understanding of that to kind of idea of what a pointer's about,

0:37:53.000,0:37:56.000
is that there is this just big sequence of

0:37:56.000,0:37:57.000
data,

0:37:57.000,0:38:00.000
starting from an address zero. You can think of these things as actually

0:38:00.000,0:38:02.000
having a little number on them.

0:38:02.000,0:38:06.000
So maybe this is number 1,000, and this is number

0:38:06.000,0:38:08.000
1,004. In this case, assuming that

0:38:08.000,0:38:10.000
we're numbering by the byte,

0:38:10.000,0:38:11.000
which is

0:38:11.000,0:38:12.000


0:38:12.000,0:38:15.000
the smallest chunk of memory we can talk about,

0:38:15.000,0:38:19.000
and that an integer requires four of those bytes to store all the different

0:38:19.000,0:38:20.000
patterns for different kinds of numbers

0:38:20.000,0:38:24.000
so that the bytes from 1,000 to 1,003 are reserved for holding

0:38:24.000,0:38:27.000
onto the information about 45. And then from 1,000 forward -

0:38:27.000,0:38:31.000
to however big the string is, which we don't even really know how big it is, so we'll

0:38:31.000,0:38:33.000
kind of leave it a little bit vague here -

0:38:33.000,0:38:37.000
is gonna be set aside for storing information about that string.

0:38:37.000,0:38:38.000
Okay.

0:38:38.000,0:38:41.000
So usually it's of interest to the compiler, right, to know where things are being

0:38:41.000,0:38:43.000
stored and what's going on.

0:38:43.000,0:38:47.000
But it also turns out to be somewhat useful for us to be able to talk about

0:38:47.000,0:38:50.000
something by address. Instead of saying the variable

0:38:50.000,0:38:51.000
whose name is Num,

0:38:51.000,0:38:56.000
I can talk about the variable who lives at location 1,000. And say

0:38:56.000,0:38:58.000
there's an integer, and

0:38:58.000,0:39:01.000
I can point to it, or refer to it

0:39:01.000,0:39:05.000
by saying go look at memory address 1,000, and read or write the contents

0:39:05.000,0:39:09.000
there that are of integer type. Okay.

0:39:09.000,0:39:13.000
It seems a little bit odd at first. You're like, well I already have other ways to get to Num.

0:39:13.000,0:39:16.000
Why is it I want to go out of my way to find another different mechanism that can

0:39:16.000,0:39:18.000
get me access to that same variable?

0:39:18.000,0:39:21.000
And we're gonna see that actually there's a lot of flexibility

0:39:21.000,0:39:23.000
that is being bought by us

0:39:23.000,0:39:27.000
adding this to our feature set. We can say, well, I could actually have

0:39:27.000,0:39:29.000
one copy of something.

0:39:29.000,0:39:32.000
So imagine that you have

0:39:32.000,0:39:32.000


0:39:32.000,0:39:33.000
a system,

0:39:33.000,0:39:37.000
like, an access system where you have student records, and they're enrolled in a bunch of different

0:39:37.000,0:39:38.000
courses, that your

0:39:38.000,0:39:41.000
enrolled in four, five different courses,

0:39:41.000,0:39:44.000
that when it comes time for a class to know who's in their list, it might be

0:39:44.000,0:39:45.000
handy for them,

0:39:45.000,0:39:48.000
instead of actually having a copy of that student's information to have a pointer

0:39:48.000,0:39:52.000
to one student record, and have a lot of different placers where there are

0:39:52.000,0:39:55.000
additional pointers taken out to that same location and says, go look at the student who's

0:39:55.000,0:39:56.000
at address 1,000.

0:39:56.000,0:39:59.000
I have the students at address 1,000, at 1,026,

0:39:59.000,0:40:02.000
at, you know, 1,035,

0:40:02.000,0:40:05.000
whatever those places are, and that that's one way I can talk about what

0:40:05.000,0:40:09.000
students I have, and those same student addresses might show up in someone else's

0:40:09.000,0:40:11.000
class list in math 51, or

0:40:11.000,0:40:13.000
physics, you know, 43 or whatever,

0:40:13.000,0:40:15.000
and that we are

0:40:15.000,0:40:18.000
all referring to one copy of the student data without duplicating it.

0:40:18.000,0:40:22.000
So this idea of being able to refer to stuff not just by name, but by where it lives,

0:40:22.000,0:40:28.000
is gonna give us some flexibility in terms of how we build things out of that.

0:40:28.000,0:40:31.000
So let me kind of show you a little bit of the basic operations,

0:40:31.000,0:40:35.000
and then - and I'll talk a little bit along the way about this thing about why they're

0:40:35.000,0:40:36.000
scary

0:40:36.000,0:40:37.000
because

0:40:37.000,0:40:40.000
using, you know, memory access as your way to get to something is a little

0:40:40.000,0:40:44.000
bit more error prone and a little bit harder to deal with than

0:40:44.000,0:40:47.000
some of the more - other operations we have.

0:40:47.000,0:40:50.000
So what I'm gonna show you here is a little piece of code.

0:40:50.000,0:40:57.000
It shows some simple use of pointers. All right.

0:40:57.000,0:40:58.000
So

0:40:58.000,0:40:59.000


0:40:59.000,0:41:02.000
I'm gonna draw some of the variables that are going on here. This

0:41:02.000,0:41:04.000
is main and it declared

0:41:04.000,0:41:05.000
an integer

0:41:05.000,0:41:08.000
whose name is Num, so I

0:41:08.000,0:41:09.000
draw a box for that, and it

0:41:09.000,0:41:13.000
declares two pointer variables. So the addition of the asterisk by the name

0:41:13.000,0:41:14.000
there

0:41:14.000,0:41:19.000
says that P and Q are pointers to integers.

0:41:19.000,0:41:23.000
So P and Q themselves are variables

0:41:23.000,0:41:26.000
that live in the stack. So all the local variables we say

0:41:26.000,0:41:30.000
live in the stack.

0:41:30.000,0:41:33.000
They are automatically allocated and de-allocated when you enter a routine. The space for

0:41:33.000,0:41:36.000
them comes into being. When you leave it, it goes away,

0:41:36.000,0:41:40.000
and that P and Q are designed not to hold integers themselves. They don't hold numbers,

0:41:40.000,0:41:44.000
but they hold the address of a number somewhere else.

0:41:44.000,0:41:47.000
And so the first thing I did with

0:41:47.000,0:41:48.000
P there was to assign it

0:41:48.000,0:41:52.000
the address of a new integer variable that came out of the heap. So the

0:41:52.000,0:41:55.000
new operator is like the new operator in Java.

0:41:55.000,0:41:59.000
It takes the thing you want to create one of, it makes one of those in the heap,

0:41:59.000,0:42:02.000
and it returns to you its address. In that way it works exactly like in Java. So, in

0:42:02.000,0:42:04.000
fact, Java actually

0:42:04.000,0:42:07.000
has pointers despite what anybody ever told you,

0:42:07.000,0:42:11.000
that the way you create objects and you use new to access them and stuff like that

0:42:11.000,0:42:15.000
is exactly the same as it is in C++ as it is

0:42:15.000,0:42:16.000
pointers behind the scene.

0:42:16.000,0:42:18.000
So I say P

0:42:18.000,0:42:20.000
gets the value of a new integer.

0:42:20.000,0:42:24.000
This memory over here is called the heap.

0:42:24.000,0:42:27.000
So this is not

0:42:27.000,0:42:29.000
to confuse you with the idea of

0:42:29.000,0:42:32.000
the stack ADT. We've been using the [inaudible]

0:42:32.000,0:42:35.000
but it does kind of - it helps you to remember that the stack actually kind of, like, by

0:42:35.000,0:42:38.000
the virtue of the way function calls get made, main calls A, which

0:42:38.000,0:42:42.000
calls B, which calls C, that that memory actually kind of is laid out like a stack.

0:42:42.000,0:42:46.000
The heap is just this unordered crazy pile of stuff.

0:42:46.000,0:42:49.000
I ask for new integer, so this might be address 1,000.

0:42:49.000,0:42:52.000
This might be address 1,004. This might be address 1,008. Typically

0:42:52.000,0:42:56.000
the stack variables are laid out right next to each other. This could be, like,

0:42:56.000,0:42:56.000
address

0:42:56.000,0:42:59.000
32,016 or something over here.

0:42:59.000,0:43:02.000
Some other larger address. So I've

0:43:02.000,0:43:03.000
assigned P to be that

0:43:03.000,0:43:07.000
thing. So what I actually gotten written into P's box is behind the scenes there really is the number,

0:43:07.000,0:43:10.000
you know, the address, 32,016. What

0:43:10.000,0:43:14.000
I'm gonna draw is an arrow to remind myself that what it is is it's a

0:43:14.000,0:43:18.000
location of an integer stored elsewhere.

0:43:18.000,0:43:20.000
The de-reference operator,

0:43:20.000,0:43:22.000
which is the first thing we see on this next line,

0:43:22.000,0:43:25.000
says to follow P

0:43:25.000,0:43:26.000
and assign it a 10.

0:43:26.000,0:43:29.000
So this is taking that address that's in P,

0:43:29.000,0:43:33.000
using it as a location to go look up something, and it says, and go write to that

0:43:33.000,0:43:35.000
location in address 32,016

0:43:35.000,0:43:42.000
the number 10.

0:43:42.000,0:43:47.000
And I said Q equals no int. So Q gets an

0:43:47.000,0:43:47.000
[inaudible]

0:43:47.000,0:43:53.000
maybe this is at 23,496.

0:43:53.000,0:43:55.000
Some other place out there. And so

0:43:55.000,0:43:58.000
that's actually kind of what's being stored here,

0:43:58.000,0:44:00.000
23,496.

0:44:00.000,0:44:03.000
And then I did this thing where I assigned from

0:44:03.000,0:44:05.000
D referencing P

0:44:05.000,0:44:09.000
to get an integer, and assign that onto what Q is that has the effect of kind of

0:44:09.000,0:44:15.000
following P, reading its 10, and then writing it over here. So copying the integers

0:44:15.000,0:44:19.000
at the end of those two pointers to make them point to the same value.

0:44:19.000,0:44:22.000
So they point to two different locations, but those locations hold the same integer

0:44:22.000,0:44:23.000
value

0:44:23.000,0:44:25.000
that is different

0:44:25.000,0:44:27.000
than the next line.

0:44:27.000,0:44:29.000
Without the stars,

0:44:29.000,0:44:34.000
where I said Q equals P,

0:44:34.000,0:44:37.000
without the stars on it,

0:44:37.000,0:44:43.000
it's saying take the address that's in P, and assign it to Q,

0:44:43.000,0:44:45.000
causing Q and P now to be aliases

0:44:45.000,0:44:48.000
for the same location.

0:44:48.000,0:44:52.000
So now I have two different ways of getting to that same piece of memory,

0:44:52.000,0:44:55.000
either by reaching through P and de-referencing, or reaching through Q and de-referencing

0:44:55.000,0:44:57.000
it - both of them

0:44:57.000,0:45:01.000
are reading and writing to that same location in the heap, where the 10 is,

0:45:01.000,0:45:05.000
and then this one down here's no longer accessible. I sort of lost track of it

0:45:05.000,0:45:06.000
when I

0:45:06.000,0:45:08.000
overwrote Q with the

0:45:08.000,0:45:10.000
copy of P.

0:45:10.000,0:45:12.000
When I am done

0:45:12.000,0:45:14.000
in C++ it is my job

0:45:14.000,0:45:15.000
to delete things

0:45:15.000,0:45:20.000
that are coming out of the heap.

0:45:20.000,0:45:24.000
Yes, it should. I'll take that one at 32,016.

0:45:24.000,0:45:28.000
Whereas in Java, when you say new, and then you stop using something,

0:45:28.000,0:45:30.000
it figures it out and it does what's called garbage collection to kind of clean up

0:45:30.000,0:45:31.000
behind you.

0:45:31.000,0:45:35.000
In C++, things that you new out of the heap are your responsibility to

0:45:35.000,0:45:36.000
delete.

0:45:36.000,0:45:40.000
So you delete something when you're done with it. If I'm no longer using this

0:45:40.000,0:45:42.000
new integer I created in the heap,

0:45:42.000,0:45:44.000
I say to delete P

0:45:44.000,0:45:47.000
to allow that memory to be reclaimed.

0:45:47.000,0:45:51.000
And so that causes this piece of memory to get marked as freed,

0:45:51.000,0:45:56.000
or reusable, so that a subsequent new call can have that space again

0:45:56.000,0:45:58.000
and use it for things.

0:45:58.000,0:46:01.000
I will note that right now, the code as written

0:46:01.000,0:46:05.000
has a little bit of an error in it because it says delete P. And

0:46:05.000,0:46:09.000
delete P says we'll follow out to 32 [inaudible] and mark it as

0:46:09.000,0:46:10.000
available.

0:46:10.000,0:46:13.000
The next thing I did was said delete Q. Well Q points to the same

0:46:13.000,0:46:17.000
place P did. So in fact I'm saying take that piece of freed memory and mark it freed

0:46:17.000,0:46:17.000
again.

0:46:17.000,0:46:19.000


0:46:19.000,0:46:22.000
There is no real guarantee about whether that's gonna do something

0:46:22.000,0:46:25.000
sensible, or whether it's just gonna ignore me. One thing it could do is just say, well look, that

0:46:25.000,0:46:27.000
memory's already freed, so

0:46:27.000,0:46:29.000
you saying to free it twice is kind of stupid.

0:46:29.000,0:46:33.000
On the other hand, it could still cause some more problems depending on how the

0:46:33.000,0:46:37.000
heap allocater works, and there's no guarantee. So it becomes very [inaudible] on the

0:46:37.000,0:46:39.000
programmer to be very careful about this matching, that

0:46:39.000,0:46:41.000
if you make a new call,

0:46:41.000,0:46:43.000
you make a delete call. And

0:46:43.000,0:46:45.000
if you already made a delete call, you don't make another one

0:46:45.000,0:46:49.000
accidentally. So I really should have that line out of there.

0:46:49.000,0:46:54.000
The piece of memory that Q originally pointed to, right, I no longer have any way to get to,

0:46:54.000,0:46:57.000
and so I have no way of making a delete call to it and freeing it. And so this little

0:46:57.000,0:47:01.000
piece of memory we call an orphan.

0:47:01.000,0:47:03.000
He's stranded out there in the heap,

0:47:03.000,0:47:04.000
no way to get back to it,

0:47:04.000,0:47:09.000
and C++ will not automatically reclaim it for us. So we have

0:47:09.000,0:47:12.000
created a little bit of a mess for ourselves. If we did that a lot, right,

0:47:12.000,0:47:16.000
we could end up clogging our heap filled with these orphans,

0:47:16.000,0:47:19.000
and have to keep getting new memory because the old memory, right, was not

0:47:19.000,0:47:22.000
being properly reclaimed.

0:47:22.000,0:47:24.000
We're gonna talk more about this, so this is not

0:47:24.000,0:47:27.000
the all - end all of pointers, but just a little bit to think about today. We'll

0:47:27.000,0:47:30.000
come back on Wednesday, talk more about it, and then talk about how we can use

0:47:30.000,0:47:33.000
this to build linked lists, and that will be

0:47:33.000,0:47:36.000
fun times for all.