Lecture 11 | Programming Abstractions (Stanford)
-
0:00 - 0:09
-
0:09 - 0:11
-
0:11 - 0:14This presentation is delivered by the Stanford Center for Professional Development.
-
0:14 - 0:23
-
0:23 - 0:25Hi there. Good afternoon.
-
0:25 - 0:27Welcome to Monday.
-
0:27 - 0:28Today's a big day.
-
0:28 - 0:31A big day, right? We've got a couple of recursive backtracking examples that we
-
0:31 - 0:35didn't get to on Friday that I'm gonna
-
0:35 - 0:36talk you through today,
-
0:36 - 0:40and then we're gonna talk a little bit about pointers, the long anticipated introduction to
-
0:40 - 0:42one of the scarier parts of the C++ language
-
0:42 - 0:47as kind of a step toward building linked lists and the recursive data idea
-
0:47 - 0:49that we will study today and
-
0:49 - 0:51continue into Wednesday.
-
0:51 - 0:54So the two samples I want to do are both based on the same backtracking pseudocode that we
-
0:54 - 0:56were using on Friday. I
-
0:56 - 0:59just want to go through them. I'm gonna do a little bit less attention to the code and
-
0:59 - 1:03a little bit more attention to the problem solving because at some point I think the problem
-
1:03 - 1:03solving
-
1:03 - 1:05is really where the tricky stuff comes on.
-
1:05 - 1:08And then the kind of - turning it into code, there's some details there but
-
1:08 - 1:11they're not actually as important, so I'm gonna de-emphasize that just a little bit here and
-
1:11 - 1:13think more about solving it.
-
1:13 - 1:16So this is the pseudocode for any form of a backtracker, right, that has
-
1:16 - 1:17some sort of,
-
1:17 - 1:20you know, failure and success cases, like when we run out of choices, we've hit a
-
1:20 - 1:24dead end, or we've hit a goal state, we've - you know, there's no more decisions to make,
-
1:24 - 1:26right, is this want to be, yes or no,
-
1:26 - 1:28and then otherwise there are some decisions to make.
-
1:28 - 1:33And for all the possible decisions we could make, we're gonna try one, be optimistic
-
1:33 - 1:37about it working out, make that recursive call that says that choice was where I
-
1:37 - 1:42wanted to be. If it returns true, or whatever the success return value is,
-
1:42 - 1:44then we return true,
-
1:44 - 1:47right? No need to look any further. That choice was good enough.
-
1:47 - 1:51If it didn't work then we gotta unmake - try some other choices. If we try all the
-
1:51 - 1:55things available to us and no case, right, did solve ever return true,
-
1:55 - 1:59then we can only conclude that the configuration as given to this call was
-
1:59 - 2:00unsolvable,
-
2:00 - 2:02which is where that return false
-
2:02 - 2:06causes it to back up to some earlier call and start unmaking
-
2:06 - 2:08that next layer of decisions,
-
2:08 - 2:11and then recur further down, eventually either
-
2:11 - 2:15unwinding the entire recursive [inaudible] all the way back to the beginning and saying it
-
2:15 - 2:18was totally unsolvable no matter what, or eventually finding
-
2:18 - 2:21some sequence of decisions that will lead to one that will get us to a success
-
2:21 - 2:23case.
-
2:23 - 2:27So the one I'm gonna show you here is the sudoku,
-
2:27 - 2:31which is those little puzzles that show up in
-
2:31 - 2:34newspapers everywhere. They're actually not
-
2:34 - 2:37attributed to - apparently, to the Japanese, but it apparently got a lot more popular
-
2:37 - 2:40under its Japanese name than it did under the original
-
2:40 - 2:41English name for it.
-
2:41 - 2:44And the goal of a sudoku, if you haven't ever done one, right, is it's
-
2:44 - 2:48a nine by nine grid in which you're trying to place numbers,
-
2:48 - 2:51and the requirement for the numbers is such that
-
2:51 - 2:53within any particular row,
-
2:53 - 2:56or any particular column, or any particular block, which is a three by
-
2:56 - 2:58three subsection of that,
-
2:58 - 3:00the numbers one through nine each appear once.
-
3:00 - 3:02So you can never have more than two ones in a row,
-
3:02 - 3:04two twos in a column,
-
3:04 - 3:06three threes in a block, or anything like that.
-
3:06 - 3:09And so there has to be some rearrangement, or, in fact,
-
3:09 - 3:11permutation
-
3:11 - 3:14of the numbers one through nine in each row, in each column, and each block,
-
3:14 - 3:17such that the whole puzzle kind of works out logically.
-
3:17 - 3:22So when it's given to you, you know, usually some fraction of the
-
3:22 - 3:23slots are already filled in,
-
3:23 - 3:27and the goal for you is to fill in those remaining slots without violating any of
-
3:27 - 3:29these rules. Now
-
3:29 - 3:33the sort of pure sudoku solvers
-
3:33 - 3:35don't really use guessing.
-
3:35 - 3:37It's considered, actually, poor form,
-
3:37 - 3:39you know, that you're supposed to actually logically work it out by constraints
-
3:39 - 3:43about what has to be true here versus what has to be true there to kind of
-
3:43 - 3:44realize that
-
3:44 - 3:46- what choices you have. We're
-
3:46 - 3:48actually not gonna be a pure,
-
3:48 - 3:51artistic, you know, sudoku solver. What we're gonna do is we're actually gonna use a brute force
-
3:51 - 3:54recursive algorithm that's just gonna try recursive backtracking, which is to
-
3:54 - 3:55say,
-
3:55 - 3:56make an assignment,
-
3:56 - 3:59be optimistic about it, and if it works out, great, and if not,
-
3:59 - 4:02we'll eventually come back to that decision and revisit it.
-
4:02 - 4:04So what we have here basically is a big decision problem.
-
4:04 - 4:06You know, of the
-
4:06 - 4:0881 squares on here,
-
4:08 - 4:10you know, about 50 of them, right, need to be
-
4:10 - 4:12chosen.
-
4:12 - 4:15For each of those 50 squares, right, we're gonna do them one at a time and recur
-
4:15 - 4:19on the remaining ones. So, you know, choose one then we'll just go left to right from the
-
4:19 - 4:20top.
-
4:20 - 4:23Choose that one at the top, make an assignment that works, and so that's what
-
4:23 - 4:26we'll use the context we have in problem here. So, for example, if you look at
-
4:26 - 4:28this first row,
-
4:28 - 4:31there's a one in this column so we can't use one. There's
-
4:31 - 4:33a two in that block so we can't use two,
-
4:33 - 4:37but there's not a three in either that row, or that column, or that block, so we'll say, well, three looks good, you
-
4:37 - 4:39know, just trying the numbers in order.
-
4:39 - 4:43We'll be optimistic, say that works, and say, well if we planted a three here, could
-
4:43 - 4:46we recursively solve the remaining 49 holes
-
4:46 - 4:48and work it out?
-
4:48 - 4:49And so
-
4:49 - 4:51we get to that next one - we look at this one and say, okay, well
-
4:51 - 4:53we could put a one here,
-
4:53 - 4:57right, because there's not a one in this column, not a one in that row, not a one in
-
4:57 - 5:01that block, so we'll kind of move on. I'm gonna do a little demo of that for you. And maybe it's
-
5:01 - 5:05to kind of keep moving our way across, and only when
-
5:05 - 5:06we get to a dead end
-
5:06 - 5:08based on some of our earlier decisions will we unmake
-
5:08 - 5:10and come back. So
-
5:10 - 5:15let me - okay.
-
5:15 - 5:20So that's the same set of numbers there. So I put the three up in the corner.
-
5:20 - 5:20
-
5:20 - 5:23And so it puts the one here thinking, okay, that looks good. So it gets to the
-
5:23 - 5:25next square over here
-
5:25 - 5:26and then
-
5:26 - 5:29the one can't be used because it's actually already in use both in that column and
-
5:29 - 5:33in the row we're building so far, but two can be used. Two doesn't conflict with anything we
-
5:33 - 5:34have so far.
-
5:34 - 5:36And so it just keeps going optimistically,
-
5:36 - 5:39right? At that stage over there it turns out almost all the numbers are in
-
5:39 - 5:43use. Most of the numbers all the way up through seven and nine are there, and seven's
-
5:43 - 5:46in its column. So, in fact, the only number that that could possibly be is nine, so
-
5:46 - 5:49the only choice we have here to try is nine,
-
5:49 - 5:51and then we'll place the seven next
-
5:51 - 5:54to it. And so now we have a whole row that doesn't conflict with any of its blocks this
-
5:54 - 5:56way, and then we just keep moving on, right,
-
5:56 - 5:57so that is to keep kind of
-
5:57 - 5:59going from top to bottom, left to right.
-
5:59 - 6:01We'll place that four. We'll
-
6:01 - 6:04place another one. Place a three.
-
6:04 - 6:07So it's actually choosing them - it's actually going in order from one to nine just picking
-
6:07 - 6:09the first one that fits,
-
6:09 - 6:11right, so
-
6:11 - 6:13when we get to the next square here, right,
-
6:13 - 6:17it 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
-
6:17 - 6:18that row. It can't
-
6:18 - 6:20use six because it's in the column. It
-
6:20 - 6:22can't use seven
-
6:22 - 6:24because it's in that row, but it should be able to use eight,
-
6:24 - 6:26and so it'll place an eight there.
-
6:26 - 6:29So it just kind of examines them in sequence until it finds the first one that
-
6:29 - 6:32doesn't violate any things already decided,
-
6:32 - 6:35and then kind of moves optimistically forward.
-
6:35 - 6:38So about this point, right, we're doing pretty well, but we're starting to
-
6:38 - 6:40run into some troubles if you look at
-
6:40 - 6:42the next one over here.
-
6:42 - 6:44It'll place the six there,
-
6:44 - 6:46but then it will -
-
6:46 - 6:50once the six is placed there, then it looks to the right and it says, oh, I need to put a
-
6:50 - 6:52nine there. That's the only number left. It tries all the numbers one, two,
-
6:52 - 6:53three, four,
-
6:53 - 6:55and it says that isn't gonna work.
-
6:55 - 6:59And so it actually fails on the rightmost column,
-
6:59 - 7:02which causes it to back up to the one right before and it says, well, why don't you try
-
7:02 - 7:05something else here? Well, it looks at seven, eight, and nine, none of those can work either,
-
7:05 - 7:07so it's actually gonna back up even further
-
7:07 - 7:10and then say, well what if we try to put a nine here? That also doesn't work. So now it's
-
7:10 - 7:14gonna start seeing that it's kind of unwinding as the constraints we have made have kind of
-
7:14 - 7:17got us down a dead end and it's slowly working its way back out to where the
-
7:17 - 7:21original bad decision was made.
-
7:21 - 7:24So it tries again on moving nine in here, and moving across, right,
-
7:24 - 7:26but again, kind of,
-
7:26 - 7:27
-
7:27 - 7:30you know, working its way forward but then kind of backing its way up. And
-
7:30 - 7:32let me go ahead
-
7:32 - 7:37and just run it faster so you can kind of see it.
-
7:37 - 7:41But, you know, it's working on that row for a while, but essentially to note that the top row stays
-
7:41 - 7:44relatively constant. It kind of believes that, well, that first three must have been good because, you
-
7:44 - 7:47know, we're getting somewhere on that, and it keeps kind of going. You can see
-
7:47 - 7:50that the activity is kind of always at the kind of
-
7:50 - 7:54tail end of that decision making, which eventually, right,
-
7:54 - 7:56worked its way out. And so it turns out, like, those three ones that we did put in the
-
7:56 - 7:59first spots were fine.
-
7:59 - 8:01That is, choices, right, it did work out.
-
8:01 - 8:04We didn't know that when we started, right, but it was optimistic, right, it put it down
-
8:04 - 8:05and then kept moving, and
-
8:05 - 8:08then eventually, right,
-
8:08 - 8:12worked out how the other things that had to get placed to make the whole puzzle
-
8:12 - 8:13be solvable.
-
8:13 - 8:18And so this thing can solve, actually, any solvable sudoku, right, and if it's not animating,
-
8:18 - 8:19instantaneously,
-
8:19 - 8:21even though it is really doing it in a fairly crude way,
-
8:21 - 8:24right, it's basically just trying everything it can,
-
8:24 - 8:27moving forward, and only when it kind of reaches a contradiction
-
8:27 - 8:30based on some of those choices that they will - that can't possibly be because at
-
8:30 - 8:33this point I'm forced into a situation where there's nothing that works in this
-
8:33 - 8:33square,
-
8:33 - 8:36so it must be that some earlier decision was wrong.
-
8:36 - 8:39And you notice that when it backs up, it backs up to the most immediate decision.
-
8:39 - 8:42So if you think of it in terms of recursive call, here's your first decision, your second
-
8:42 - 8:44decision, your third decision, your fourth decision, your fifth decision. If you get down
-
8:44 - 8:47here and you're, like, trying to make your eighth decision,
-
8:47 - 8:49and there's nothing that works, right,
-
8:49 - 8:53the decision that you come back to will be your seventh one. The one right
-
8:53 - 8:56before it. You don't go throw everything away and start over. You don't go all the way
-
8:56 - 8:59back to the beginning and say, oh, well that didn't work, let's try again.
-
8:59 - 9:01It's that you actually use the kind of context to say, well,
-
9:01 - 9:04the last decision I made was probably the one that needs a little fixing. Let me
-
9:04 - 9:08just back right up to that one. That's the way the calls unwind, and it says we'll pick up
-
9:08 - 9:11trying some other options there. Which ones have we not tried on that one? And
-
9:11 - 9:15then go forward again, and again, if you get down to that eighth decision and you're still
-
9:15 - 9:18stuck, you come back to the seventh decision again, and only after kind of the seventh decision
-
9:18 - 9:21has gone back and forth with the eighth unsuccessfully
-
9:21 - 9:25through all its options would we eventually return to that sixth decision, and
-
9:25 - 9:29potentially back to the fifth, and fourth, and so on.
-
9:29 - 9:31The code for this guy,
-
9:31 - 9:32
-
9:32 - 9:36a little abstracted
-
9:36 - 9:39that should very much fit the pattern of what you think recursive backtracking
-
9:39 - 9:40looks like, and then the kind of
-
9:40 - 9:43sort of goofier parts that are about, well, what does it mean to test a
-
9:43 - 9:47sudoku for being a sign of having conflicts is actually then
-
9:47 - 9:50passed out into these helper functions that manage the more
-
9:50 - 9:52domain specific parts of the problem.
-
9:52 - 9:55So at the very beginning it's like, find an unassigned location on the grid, and
-
9:55 - 9:58it returns the row and column by reference. It turns out in this case
-
9:58 - 10:01those are reference parameters. So [inaudible] searches from top to bottom to find the
-
10:01 - 10:05first slot that actually does not have a value currently in it.
-
10:05 - 10:08If it never finds one, so exhaustively searched the grid and didn't find one, then it
-
10:08 - 10:11must be that we have a working sudoku because we never put a number in
-
10:11 - 10:17unless it worked for us, and so if we've managed to assign them all, we're done.
-
10:17 - 10:19If this didn't return true,
-
10:19 - 10:21that meant it found one, and it assigned them a row and column,
-
10:21 - 10:24and then what we're gonna go through the process of is assigning that row and
-
10:24 - 10:24column.
-
10:24 - 10:26So we look at the numbers one through nine.
-
10:26 - 10:28If there are no conflicts for that number,
-
10:28 - 10:32so it doesn't conflict with the row, column, or block,
-
10:32 - 10:35that number isn't already in use in one of those places, then we go ahead and make
-
10:35 - 10:36the assignment,
-
10:36 - 10:40and then we see if we can solve it from here. So having updated the grid
-
10:40 - 10:42to show that new number's in play,
-
10:42 - 10:46you know, if we move on, the next [inaudible] of sudoku will then do a
-
10:46 - 10:50search for find unassigned location. This time the one that we previously found, right,
-
10:50 - 10:52has been assigned, so it actually won't get triggered on that one.
-
10:52 - 10:55It'll look past it further down into the puzzle,
-
10:55 - 10:57and eventually either find
-
10:57 - 11:00the next one to make a call on, and kind of work its way through, or to - you have to
-
11:00 - 11:02solve the whole thing.
-
11:02 - 11:06If it didn't work, so we made that assignment to the number nine, and we went to solve,
-
11:06 - 11:07and eventually this
-
11:07 - 11:11tried all its possibilities from here and nothing came up good, then this
-
11:11 - 11:13unassigned
-
11:13 - 11:15constant is used to unmake that decision,
-
11:15 - 11:18and come back around, and try
-
11:18 - 11:21assigning it a different number. If we try all of our examples, so for
-
11:21 - 11:25example, if we never find one that doesn't already conflict, or
-
11:25 - 11:29if we try each one and it comes back false, right, that this return false here is
-
11:29 - 11:30what's triggering
-
11:30 - 11:33the backtracking up to the previous recursive call
-
11:33 - 11:37to reconsider some earlier decision - the most recent early decision
-
11:37 - 11:38for this one,
-
11:38 - 11:40and say that was really our mistake, right,
-
11:40 - 11:42we've got to unmake that one.
-
11:42 - 11:45So it should look like kind of all the recursive backtracking all through looks the same,
-
11:45 - 11:47right? You know, if
-
11:47 - 11:48we're at the end,
-
11:48 - 11:49here's our base cases
-
11:49 - 11:53for all our options. If we can make this choice, make it, try to solve it, be
-
11:53 - 11:56optimistic, if it works out, return.
-
11:56 - 11:59Otherwise, unmake it, allow the loop to iterate a
-
11:59 - 12:02few more times trying again. If all of those things
-
12:02 - 12:06fail to find a solution then that return false here will cause the backtracking
-
12:06 - 12:12out of this decision. I just let it
-
12:12 - 12:15become constant. You know, I made it up. I used negative one, in fact,
-
12:15 - 12:16just to know that
-
12:16 - 12:20it has no contents.
-
12:20 - 12:26Just specific to sudoku in this case. Now would be a great time
-
12:26 - 12:30to ask a question. You guys kind of have that sort of half-okay
-
12:30 - 12:34look on your face. It could be I'm totally bored. It could be I'm totally lost. Where do row and column
-
12:34 - 12:35get assigned? So they
-
12:35 - 12:38- finding assigned location takes [inaudible] reference.
-
12:38 - 12:41So if you look at the full code for this - this is actually in the handout I gave out last time, and so
-
12:41 - 12:44there's a pass by reference in that function, and it returns true if it assigned
-
12:44 - 12:46them something, and then they have the
-
12:46 - 12:49coordinates of that
-
12:49 - 12:51unassigned location. Question over here. How'd you know
-
12:51 - 12:55to write sol sudoku as a bool rather than as, like, a void function? Well, in this
-
12:55 - 12:57case - that's a great question, right,
-
12:57 - 13:01in most cases in recursive backtracking I am trying to
-
13:01 - 13:05discover the success or failure of an operation, and so that's a good way to tell
-
13:05 - 13:07because otherwise I need to know did it work.
-
13:07 - 13:10And so if I made it void then there had to be some other way I figured it out. Maybe,
-
13:10 - 13:13you know, that you have to check the grid when you're done and see that it has - no longer has
-
13:13 - 13:16any unassigned locations, but the bool is actually just the easiest way to get that
-
13:16 - 13:17information out.
-
13:17 - 13:19So typically your recursive backtracking machine
-
13:19 - 13:21will probably return something.
-
13:21 - 13:22
-
13:22 - 13:25Often it's a true or false. It could be, you know, in some other case, just some other
-
13:25 - 13:27good know value, and some other
-
13:27 - 13:31sentinel that says, you know, bad value. So, for example, in the finding an anagram of the
-
13:31 - 13:34words it might be that it returned the word if it found one, or returned an empty string if
-
13:34 - 13:36it didn't. So using some sort of state that says
-
13:36 - 13:39here's how - if you made the call, you'll know whether it worked because we
-
13:39 - 13:40really do need to know.
-
13:40 - 13:44Make the call and find out whether it worked. Well, how are we gonna find out? One of the best ways to
-
13:44 - 13:47get that information is from a return value. Way in
-
13:47 - 13:52the back? Exactly does the return calls trigger in the backtracking
-
13:52 - 13:52[inaudible]?
-
13:52 - 13:56So think about this as that, you know, it's hard to think about because you have to kind of have kind of
-
13:56 - 13:58both sides of the recursion in your head, but
-
13:58 - 14:00when - let's say we're on
-
14:00 - 14:02the fifth decision, right?
-
14:02 - 14:05We make the call to solve the sudoku that's gonna look at the sixth
-
14:05 - 14:06decision, right?
-
14:06 - 14:10If the sixth decision fails, it says, I looked at all my choices and none of them
-
14:10 - 14:11worked, right?
-
14:11 - 14:12It's that
-
14:12 - 14:15that causes the fifth decision to say, well I - here go solve for the sixth decision
-
14:15 - 14:18down. Well the sixth decision came back with a false. It got to this case after
-
14:18 - 14:19trying all its options,
-
14:19 - 14:23then it's the fifth decision that then says, okay, well then I'd better unmake the decision I
-
14:23 - 14:24made and try again.
-
14:24 - 14:28And so at any given stage you can think about the caller and the callee, it's saying,
-
14:28 - 14:31I'm making a decision. You tell me if you can make it work from here.
-
14:31 - 14:35If the delegate that you passed on the smaller form of the recursive problem comes
-
14:35 - 14:39back with a return false, and then I've tried everything I could possibly do, but
-
14:39 - 14:42there was no way. The situation you gave me was unworkable.
-
14:42 - 14:46And that says, oh, okay, well you know what, it must have been my fault, right? I put
-
14:46 - 14:49the wrong number in my box. Let me try a different number and now you try again.
-
14:49 - 14:52And so they're constantly kind of these - you have to keep active in your mind the
-
14:52 - 14:52idea
-
14:52 - 14:55that there's this whole chain of these things being stacked up, each of them
-
14:55 - 14:59being optimistic and then delegating down. And if your delegate comes back
-
14:59 - 15:00with the -
-
15:00 - 15:02there was nothing I could do,
-
15:02 - 15:06then you have to revisit your earlier optimistic decision, unmake it, and
-
15:06 - 15:07try again.
-
15:07 - 15:09And so
-
15:09 - 15:12that - this is the return false to the outer call,
-
15:12 - 15:16the one that made the solved call
-
15:16 - 15:17that unwinds from.
-
15:17 - 15:21Way over here? [Inaudible]?
-
15:21 - 15:26Pretty much any recursive piece of thing can be reformed into a backtracking form, right?
-
15:26 - 15:29You need to - to do a little bit like the [inaudible] we tried last time,
-
15:29 - 15:32we'll take a void returning thing and make it return some true or false, and there's kind of,
-
15:32 - 15:36like, make a decision and be optimistic, see if it worked out.
-
15:36 - 15:40But that kind of rearrangement of the code should work with pretty much all
-
15:40 - 15:43your standard recursion stuff. So any kind of puzzle that actually,
-
15:43 - 15:46like, all these kind of jumble puzzles, and crossword puzzles, and things
-
15:46 - 15:48that involve kind of choosing, right,
-
15:48 - 15:52can be solved with recursive backtracking. It's not necessarily the fastest, right, way
-
15:52 - 15:56to get to a solution, but it will exhaustively try all the options until
-
15:56 - 16:00a sequence of decisions, right, leads you to a goal if there is a goal to be found.
-
16:00 - 16:03And so that if you can think of it as - if you can think of your problem as a
-
16:03 - 16:04decision problem -
-
16:04 - 16:07I need to make some decisions, and then from there make some more decisions and so
-
16:07 - 16:09on, and eventually, right, I will bottom out
-
16:09 - 16:11either at a goal or dead end,
-
16:11 - 16:14then you can write a recursive problem solving -
-
16:14 - 16:18backtracker to solve it. Way in
-
16:18 - 16:23the 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
-
16:23 - 16:28function in our stenographics library, and you just give it a time. You say one second, half a second, and
-
16:28 - 16:29just - I
-
16:29 - 16:31use that a lot in our demos, for example, for the maze, so that you can actually see what's
-
16:31 - 16:35going on, and that way it just animates a little more. Stenographics, CSTgraph.h. [Inaudible] me
-
16:35 - 16:42show you
-
16:42 - 16:43one more
-
16:43 - 16:45kind
-
16:45 - 16:47of just in the same theme. The idea of taking
-
16:47 - 16:50sort of some, you know, puzzle that somebody might give you,
-
16:50 - 16:53trying to cast it in terms of a decision problem, right, where you make decisions
-
16:53 - 16:55and then you move on,
-
16:55 - 16:58can I solve something like these little cryptographic puzzles?
-
16:58 - 17:01So here's send plus more equals money.
-
17:01 - 17:03I've got eight
-
17:03 - 17:08digits in there - eight letters in there. You know, D E M N O R S
-
17:08 - 17:10Y across all of them,
-
17:10 - 17:13and the goal of this puzzle is to assign these letters -
-
17:13 - 17:17eight letters to the digits zero through nine without replacement
-
17:17 - 17:18so that
-
17:18 - 17:21if D's assigned to three, it's assigned to three in all places. For example, O shows up
-
17:21 - 17:24two places in the puzzle. Both of those are either a two or both are three.
-
17:24 - 17:27There's not one that's one and one that's another. And each
-
17:27 - 17:33digit is used once. So, like, if I assigned two to O, then I will not assign two to D. So
-
17:33 - 17:35what we've got here is eight letters.
-
17:35 - 17:38We've got 10 digits.
-
17:38 - 17:41We want to make an assignment.
-
17:41 - 17:44What we've got here is some choices. The choices are,
-
17:44 - 17:48for each letter, what digit are we gonna map it to?
-
17:48 - 17:51Another way to think about it is if you took these eight letters, and then you
-
17:51 - 17:53attach two dashes on the end,
-
17:53 - 17:56then you considered that the letter's position in the string was - the index
-
17:56 - 17:58of it was its digit.
-
17:58 - 18:00It's really just like trying the permutations,
-
18:00 - 18:02right, rearranging those
-
18:02 - 18:06letters in any of those sequences. So right now, for example, maybe D is assigned
-
18:06 - 18:09zero, and one, and two, and so on, and these guys are eight, nine. Well, if
-
18:09 - 18:12you rearrange the letters into some other permutation then you've made a
-
18:12 - 18:13different assignment.
-
18:13 - 18:16So in effect, right, what you're looking at is a problem that has a lot in common with
-
18:16 - 18:17permutations, right?
-
18:17 - 18:21I'm gonna make an assignment, take a letter off, decide what index it's gonna
-
18:21 - 18:24be placed at, so it's kind of like deciding where it would go in the permutation,
-
18:24 - 18:27and then that leaves us with a smaller form of the problem
-
18:27 - 18:30which has one fewer letters to be assigned,
-
18:30 - 18:33and then recursively explore the options from there to see if we can make
-
18:33 - 18:37something that makes the addition add up correctly that D plus E equals Y
-
18:37 - 18:37means that
-
18:37 - 18:39if D was assigned five,
-
18:39 - 18:43and E was three, then Y better be eight for this to work out.
-
18:43 - 18:47So the first form I'm gonna show you is actually just the dumb,
-
18:47 - 18:49exhaustive recursive backtracking
-
18:49 - 18:53that works very much like the sudoku problem where it just - it finds the next unassigned
-
18:53 - 18:57letter, it assigns it a digit of the next auto sign digits, right, and then just
-
18:57 - 18:59optimistically figures that'll work out.
-
18:59 - 19:02After it makes an assignment for all the letters it says,
-
19:02 - 19:07take the puzzle, convert all the letters into their digit equivalents, and see if it adds
-
19:07 - 19:08together correctly.
-
19:08 - 19:10If so, we're done. If not,
-
19:10 - 19:13then let's backtrack.
-
19:13 - 19:16So let me - I mean, actually, I'll show you
-
19:16 - 19:18the code first
-
19:18 - 19:20because it's actually quite easy to
-
19:20 - 19:21take a look at.
-
19:21 - 19:25Again, it has helper routines that kind of
-
19:25 - 19:29try to abstract the pieces of the puzzle that actually aren't interesting
-
19:29 - 19:31from kind of looking at just the core of the recursive algorithm, so it looks a
-
19:31 - 19:33lot like sudoku
-
19:33 - 19:36in that if letters do assign, so it actually keeps the string of the letters that
-
19:36 - 19:38haven't yet been assigned.
-
19:38 - 19:41If there are no more letters in that string, we take one off at each time we
-
19:41 - 19:42assign it,
-
19:42 - 19:45then we check and see if the puzzle's solved. So that kind of does the substitution, and does
-
19:45 - 19:48the math, and comes back saying yes or no.
-
19:48 - 19:50
-
19:50 - 19:53If it worked out, we'll get a true. If it didn't work out we get a false.
-
19:53 - 19:57If we still have letters to assign then it goes through the process of making a choice, and
-
19:57 - 19:59that choice is looking at the
-
19:59 - 20:00
-
20:00 - 20:04digits zero through nine if we can assign it. So looking at that first letter in
-
20:04 - 20:07that digit, and then that's making sure that we don't already have an assignment for
-
20:07 - 20:10that letter, that we don't have an assignment for that digit. Sort of make sure that just the
-
20:10 - 20:12constraints of the problem are being met.
-
20:12 - 20:14If we're able to make that assignment
-
20:14 - 20:16then we go ahead and make a recursive call,
-
20:16 - 20:18having one fewer letters
-
20:18 - 20:20to make a decision for, and
-
20:20 - 20:23if that worked out true, otherwise we do an unassignment and come back around
-
20:23 - 20:24that loop
-
20:24 - 20:27and then eventually the same return false at the bottom, which said, well
-
20:27 - 20:31given the previous assignments of the letters before we got to this call,
-
20:31 - 20:33there was nothing I could do from here
-
20:33 - 20:36to make this work out. So
-
20:36 - 20:40let me show you this guy working because you're gonna see that it is actually
-
20:40 - 20:42a crazy way to try to solve this problem
-
20:42 - 20:45in terms of what you know about
-
20:45 - 20:48stuff. So I say C S plus U equals fun,
-
20:48 - 20:54a well-known equation.
-
20:54 - 20:57So I did this little animation to try to get you visualized what's going on at any
-
20:57 - 20:59given stage.
-
20:59 - 21:00So
-
21:00 - 21:03it has the letters down across the bottom, S U N C O Y F.
-
21:03 - 21:06That's the string of letters to assign.
-
21:06 - 21:08It's gonna assign it the next available digit
-
21:08 - 21:11when it makes that recursive call, so the first recursive call is
-
21:11 - 21:12gonna be about assigning S,
-
21:12 - 21:16and then the next call will be assign U, and the next call - and so on. So it always
-
21:16 - 21:18gets up to seven deep
-
21:18 - 21:19on any particular thing.
-
21:19 - 21:21And so it says, okay, well
-
21:21 - 21:25first digit available is zero, go ahead and assign that to S. So it's gonna make a
-
21:25 - 21:28call there. And then it says, okay, well look at U. Well we can't use
-
21:28 - 21:33zero because zero's already in use. What don't we assign U to be one? Okay. Sounds good. Keep going. And
-
21:33 - 21:36then it'll say, okay, let's get to N. Let's make an assignment for N. It says I'll look around.
-
21:36 - 21:40Okay, well zero's in use, one's in use, how about two? Okay. Good.
-
21:40 - 21:41And then it assigns
-
21:41 - 21:44this to three, this to four, this to five,
-
21:44 - 21:47and this to six. Okay. It gets to here and it says,
-
21:47 - 21:48hey, does that work,
-
21:48 - 21:5030 plus 541 equals
-
21:50 - 21:52612? No?
-
21:52 - 21:55Okay. Well, you know what the problem was? It was F,
-
21:55 - 22:01right? I assigned F to six. How stupid of me. It can't be six. Let's make it seven.
-
22:01 - 22:02
-
22:02 - 22:05And then it says, oh, oh no, oh I'm sorry. I'm sorry, 30 plus 541 that's not
-
22:05 - 22:07712. How silly.
-
22:07 - 22:09I need to assign F to be eight.
-
22:09 - 22:11And it's gonna do this for a little while.
-
22:11 - 22:12A long while [inaudible].
-
22:12 - 22:13And then it says, oh, okay. Well,
-
22:13 - 22:17you know what, given the letters you'd assigned to the first six things, when you got to
-
22:17 - 22:20F, I tried everything I could and there was nothing I could do to fix this.
-
22:20 - 22:23You know what the problem was? It's not me. It's not me. I'm not the problem. You're the
-
22:23 - 22:24problem.
-
22:24 - 22:26So it returns false
-
22:26 - 22:29from this call at the bottom, having tried all its options,
-
22:29 - 22:31which causes Y to say, oh, yeah, yeah,
-
22:31 - 22:36I know. I know I said five. Did I said five? I didn't meant to say five. I meant to say six.
-
22:36 - 22:39And so it moves up to the six option.
-
22:39 - 22:43Again, optimistically saying that's good. Go for it. See what you can do.
-
22:43 - 22:44So it picks five.
-
22:44 - 22:44That won't work,
-
22:44 - 22:46right? It picks seven. It's gonna
-
22:46 - 22:48go for a long time, right, because it turns out, right,
-
22:48 - 22:52this is one of those cases where that very first decision, that was one of your problems,
-
22:52 - 22:52right?
-
22:52 - 22:54If you assign S to be zero,
-
22:54 - 22:58there's nothing you can assign U and N to be that are gonna work out.
-
22:58 - 23:01So what it's gonna be going through is this process though of
-
23:01 - 23:05having, you know, committed to this early decision and kind of moving on it's gonna try
-
23:05 - 23:10every other variation over here before it gives up on that. So let me
-
23:10 - 23:13
-
23:13 - 23:16set it to going.
-
23:16 - 23:22Even though C S plus U does equal fun. I guarantee it. We'll
-
23:22 - 23:23let it do some work for a while.
-
23:23 - 23:26So those bars is they grow up are desperation.
-
23:26 - 23:29You can think of that as, like, it's running out of options. It's running out of
-
23:29 - 23:30time, you know, and it's like oh,
-
23:30 - 23:33oh, wait, earlier, back up, back up. And so, okay, you can kind of see
-
23:33 - 23:36how far its backed up but sort of how tall
-
23:36 - 23:40some of the deeper recursive calls, right, the earlier ones in the sequence. And
-
23:40 - 23:41so
-
23:41 - 23:44it doesn't, you know, revisit any of these decisions because it's really busy over
-
23:44 - 23:47here, but you can see that C is now up to seven.
-
23:47 - 23:49It'll get up to eight. It'll get up to nine.
-
23:49 - 23:52And that was when it will cause itself to say, you know, I tried everything that was
-
23:52 - 23:54possible from C on down,
-
23:54 - 23:58and there was no way to make this thing work out. It must be that the bad
-
23:58 - 24:00decision was made earlier.
-
24:00 - 24:04Let's back up and look at that. And so it'll come back to the decision N,
-
24:04 - 24:09bump it up by one, and then go again. It's gonna do this a long time, right?
-
24:09 - 24:12Go through all the options for N and its neighbors before it comes back and revisits
-
24:12 - 24:14the U. It's gonna have to get U all the way up,
-
24:14 - 24:18right, through having tried one, two, three, four. So adding zero to one, and two, and three,
-
24:18 - 24:19and four,
-
24:19 - 24:21and discovering it can never make a match over there
-
24:21 - 24:24before it will eventually decide that the S
-
24:24 - 24:25is really where
-
24:25 - 24:27we got ourselves in trouble.
-
24:27 - 24:29So this is kind of in its most naive
-
24:29 - 24:32form, right? The recursive backtracking is doing basically permutations,
-
24:32 - 24:34right? You can see this is actually just
-
24:34 - 24:37permuting the digits as they're assigned to the numbers, and there are, in this
-
24:37 - 24:41case, you know, seven factorial different ways that we can make this assignment,
-
24:41 - 24:45and there are a lot of them that are wrong, right? It's not being at all clever
-
24:45 - 24:46about
-
24:46 - 24:49how to pick and choose among which to explore.
-
24:49 - 24:51So in
-
24:51 - 24:52its most naive form, right,
-
24:52 - 24:54recursive backtracking can be very expensive because often you're looking
-
24:54 - 24:59at things that have very high branching, and very long depth to them,
-
24:59 - 25:02which can add up to a lot of different things tried.
-
25:02 - 25:04Just using some simple - in this case, heuristics,
-
25:04 - 25:08sort of information you know about the domain
-
25:08 - 25:11can help you to guide your choices instead of just making the choices in order, trying the
-
25:11 - 25:14numbers zero through nine as though they're equally likely,
-
25:14 - 25:16or
-
25:16 - 25:19kind of waiting to make all the assignments before you look at
-
25:19 - 25:21anything to see if it's actually good. There's actually some ways we can kind of
-
25:21 - 25:24shape our decision making to look at the most likely options before we look at
-
25:24 - 25:26these more
-
25:26 - 25:30first. Finding the problem instead of niggling around this dead end.
-
25:30 - 25:33So I'm gonna let that guy work for a little bit
-
25:33 - 25:34while I
-
25:34 - 25:36show you another slide over here.
-
25:36 - 25:39So what the smarter solver does,
-
25:39 - 25:43is that it doesn't really consider all permutations equally plausible. We're
-
25:43 - 25:47gonna use a little grade school addition knowledge. If I look at the rightmost column, the
-
25:47 - 25:49least significant digit,
-
25:49 - 25:51I'm gonna assign D first.
-
25:51 - 25:52I assign D to zero. I assign
-
25:52 - 25:53E to one,
-
25:53 - 25:54and then I look at Y -
-
25:54 - 25:59I don't try Y is five, or seven, or anything like that. I say there's
-
25:59 - 26:01exactly one thing Y has to be, right, if
-
26:01 - 26:04D is zero and E is one, then Y has to be one, and I can say, well that won't work
-
26:04 - 26:06because I already used one for E.
-
26:06 - 26:07So it'll say,
-
26:07 - 26:10well that's impossible. Something must be wrong
-
26:10 - 26:13early. Rather than keep going on this kind of dumb
-
26:13 - 26:15dead end, it's to realize right away
-
26:15 - 26:18that one of the decisions I've already made, D and E, has gotta be wrong. So it'll back up
-
26:18 - 26:22to E. It'll try two, three, four, very quickly realizing
-
26:22 - 26:25that of all the things you could assign to E, once you have assigned D to
-
26:25 - 26:29zero, you're in trouble. And so it will quickly unmake that decision about D and work its way
-
26:29 - 26:30down.
-
26:30 - 26:34So using the kind of structure of the problem. So it makes it a little bit more
-
26:34 - 26:37housekeeping about where I'm at, and what I'm doing, and
-
26:37 - 26:37
-
26:37 - 26:38what's going on,
-
26:38 - 26:43but it is using some real smarts about what part of the tree to explore,
-
26:43 - 26:45rather than letting it kind of just go
-
26:45 - 26:49willy nilly across the whole thing. Let me get that
-
26:49 - 26:52out of the way. And I'll
-
26:52 - 27:00run this one. I say C S plus U equals fun. Okay.
-
27:00 - 27:03So it goes zero here, and
-
27:03 - 27:04tries the one, and it
-
27:04 - 27:06says no, that won't work. How about the two?
-
27:06 - 27:09No, that won't work, right, because there's nothing you can assign the N that'll
-
27:09 - 27:13make this work. And so it immediately is kind of failing on this,
-
27:13 - 27:16and even after it tries kind of all nine of these, it
-
27:16 - 27:18says none of these are looking good,
-
27:18 - 27:22then it comes back to this decision and says, no, no, actually, S's a zero. That wasn't so
-
27:22 - 27:24hot. How about we try S as one?
-
27:24 - 27:27And then kind of works its way
-
27:27 - 27:32further down.
-
27:32 - 27:34Hello? Okay. So let me try this again. Let me get it
-
27:34 - 27:40to just go. Okay.
-
27:40 - 27:42So it took 30 assignments
-
27:42 - 27:44- 30 different things it tried
-
27:44 - 27:47before it was able to come up with 41 plus 582 equals 623,
-
27:47 - 27:49which does add correctly.
-
27:49 - 27:53It didn't have to unmake once it decided that S was one. It turns out that was a
-
27:53 - 27:57workable solution so it didn't have to go very far once it made that commitment,
-
27:57 - 27:59and then you can see it kind of working its way up.
-
27:59 - 28:03So 30 assignments, right, across this tree that has, you know,
-
28:03 - 28:05hundreds of thousands in the factorial, very large number,
-
28:05 - 28:08but very quickly kind of pruning down those things that aren't worth looking
-
28:08 - 28:09at, and
-
28:09 - 28:12so focusing its attention on those things that are more likely to
-
28:12 - 28:14work out using information about the problem.
-
28:14 - 28:17It doesn't really change what the recursion does. It's kind of interesting if you
-
28:17 - 28:20think that the same backtracking and recursive strategy's the same in all these
-
28:20 - 28:23problems, but what you're trying to do is pick your options, like,
-
28:23 - 28:24looking at the choices you have
-
28:24 - 28:28and trying to decide what are the more likely ones, which ones are not worth trying, right, so
-
28:28 - 28:29sort of directing
-
28:29 - 28:32your decision making
-
28:32 - 28:33from the
-
28:33 - 28:36standpoint of trying to make sure you don't violate constraints that later will come
-
28:36 - 28:38back to bite you, and things like that.
-
28:38 - 28:40
-
28:40 - 28:41This one's back here.
-
28:41 - 28:43It's at
-
28:43 - 28:4713,000 and working hard. Getting desperate. Doing its thing. Still has not unmade the
-
28:47 - 28:52decision about S is zero, so you can get an idea of how much longer it's gonna take. We'll
-
28:52 - 28:53just let it keep going.
-
28:53 - 28:55I'm in no hurry - and let
-
28:55 - 28:56it
-
28:56 - 29:07do its thing.
-
29:07 - 29:11So let me - before I move away from talking about recursion, just try
-
29:11 - 29:12
-
29:12 - 29:15to get you thinking just a little bit about how the patterns we're seeing,
-
29:15 - 29:16right,
-
29:16 - 29:18are more alike than they are different.
-
29:18 - 29:21That solving a sudoku, solving the eight queens,
-
29:21 - 29:26you know, solving the find an anagram in a sequence of letters, that
-
29:26 - 29:31they all have this general idea of there being these decisions that you're making,
-
29:31 - 29:33and you're working your way down to where there's, you know
-
29:33 - 29:37- fewer and fewer of those decisions until eventually you end up, sort of, okay, I'm done. I've
-
29:37 - 29:41made all the decisions I can. What letter goes next, or whether something goes in or out.
-
29:41 - 29:44And the two problems that I call the kind of master or mother problems,
-
29:44 - 29:46right, of permutations and subsets
-
29:46 - 29:49are kind of fundamental to
-
29:49 - 29:52adapting them to these other domains. And so I'm gonna give you a couple
-
29:52 - 29:55examples of some things that come up that actually are just kind of permutations,
-
29:55 - 29:58or subsets, or some variation that you can help me think about a little bit.
-
29:58 - 30:03One that the CS people are fond of is this idea of knapsack feeling.
-
30:03 - 30:07It's often cast as someone breaking into your house. All criminals at
-
30:07 - 30:09heart apparently in computer science.
-
30:09 - 30:12And you've got this sack, and you can put 50 pounds of stuff in it,
-
30:12 - 30:15right, and you're looking around, you know, at all the stuff that's
-
30:15 - 30:18up for grabs in this house that you've broken into,
-
30:18 - 30:22and you want to try to pack your sack, right, so that you've got 50 pounds of the high value
-
30:22 - 30:23stuff.
-
30:23 - 30:26So let's say there's, like, 100 things, right, you could pick up, right,
-
30:26 - 30:29and they weigh different amounts, and they're worth different amounts.
-
30:29 - 30:33What's the strategy for going about finding the optimal
-
30:33 - 30:35combination of things to stick into your sack, right,
-
30:35 - 30:38so that you got the maximum value from your heist?
-
30:38 - 30:44What problem does that look like that you've seen?
-
30:44 - 30:47It's a subset. It's a subset. [Inaudible].
-
30:47 - 30:48Right? So if you look at the,
-
30:48 - 30:52you know, the Wii, and you say, oh, should I take the Wii? You know, it weighs this much, and it's this much
-
30:52 - 30:53value, well
-
30:53 - 30:56let's try it in and see what happens, right, and see what else I can stuff in the sack with
-
30:56 - 30:59that, right, and then see how well that works out. I should also try it with it out.
-
30:59 - 31:02So while you're standing there trying to decide what to
-
31:02 - 31:05steal, you have to type in all the values of things in every computer program.
-
31:05 - 31:08Go through the kind of machinations of well, try this with that because some things
-
31:08 - 31:10are big, but have a lot of value,
-
31:10 - 31:13but they only leave a little bit of odd space left over you might not be able to
-
31:13 - 31:15use well, or something.
-
31:15 - 31:18But what we're looking for is the optimal combination, the optimal subset. So
-
31:18 - 31:21trying the different subsets tells you how much value and weight
-
31:21 - 31:25you can get in a combination, and then you're looking for that best value you can get.
-
31:25 - 31:27You're the traveling salesman.
-
31:27 - 31:29You've got 10 cities to visit.
-
31:29 - 31:33Boston, New York, Phoenix, Minneapolis, right?
-
31:33 - 31:36You want to cover them in such a way that you spend the minimal amount of time,
-
31:36 - 31:40you know, in painful air travel across the U.S. Well you certainly don't want to be
-
31:40 - 31:41going
-
31:41 - 31:47Boston, New York, right, like, Boston, to L.A., to New York, to Seattle, to
-
31:47 - 31:48D.C.,
-
31:48 - 31:51to Los Angeles back and forth, right? There's gotta be a pattern where you
-
31:51 - 31:55kind of visit the close cities and work your way to the far cities to kind of
-
31:55 - 31:58minimize your total distance overall.
-
31:58 - 32:02What problem was that really in disguise? We've
-
32:02 - 32:06got 10 cities. What are you trying to do?
-
32:06 - 32:08Help me out a little. I hear it almost. Louder.
-
32:08 - 32:12Permutations. You've got a permutation problem there, all right?
-
32:12 - 32:14You got 10 cities. They all have to show up,
-
32:14 - 32:17right? And it's a permutation. Where do you start, where do you end, where do you go in the
-
32:17 - 32:20middle, right? What sequencing, right, do you need to take?
-
32:20 - 32:21So what you're looking at is
-
32:21 - 32:24try the permutations, tell me which ones come up short.
-
32:24 - 32:27There are things, right, about heuristics that can help this, right?
-
32:27 - 32:28So the idea that
-
32:28 - 32:31certainly, like, the ones that are closer to you are likely to make a better
-
32:31 - 32:33choice than the longer one. So kind of using
-
32:33 - 32:36some information about the problem can help you decide which ones are more
-
32:36 - 32:40promising avenues to explore. But in the end it's a permutation problem.
-
32:40 - 32:43I'm trying to divide you guys into fair teams. I want to, you know, divide you up into
-
32:43 - 32:4610 teams to have a kind of head-to-head programming competition. I happen to know
-
32:46 - 32:48all your Iqs.
-
32:48 - 32:50I don't know. Some other, you know, useless fact that
-
32:50 - 32:53perhaps we could use as some judge of your worth.
-
32:53 - 32:54
-
32:54 - 32:58And I want to make sure that each time has kind of
-
32:58 - 33:01a fair amount of IQ power in it
-
33:01 - 33:03relative to the others that I didn't put,
-
33:03 - 33:09you know, all the superstars on one team. What am I doing? How do
-
33:09 - 33:12I divide you guys up? It's a subset problem, right? So
-
33:12 - 33:14if -
-
33:14 - 33:17in this case it's a subset that's not just in or out. It's like which team am I gonna
-
33:17 - 33:21put you in? So I've got 10 subsets to build. But in the end it's an in out
-
33:21 - 33:22problem that looks like, well,
-
33:22 - 33:23I have the next student.
-
33:23 - 33:27Which of the 10 teams can I try them in? I can try them in each of them, right? So
-
33:27 - 33:30in some sense it's trying in the first team, the second team, the third team,
-
33:30 - 33:32right, and then pull the next student, try him in those teams,
-
33:32 - 33:35and then see whether I can come up with something that appears to get a balance ratio when I'm
-
33:35 - 33:37done.
-
33:37 - 33:41It turns out you can take the letters from Richard Millhouse Dickson and you can
-
33:41 - 33:44extract and rearrange them to spell the word criminal. I
-
33:44 - 33:48am making no conclusion about anything, having done that,
-
33:48 - 33:48just
-
33:48 - 33:50an observation of fact.
-
33:50 - 33:51
-
33:51 - 33:55But that sort of process, right, I'm trying to find, well what is the longest word
-
33:55 - 33:58that you can extract from a sequence of letters?
-
33:58 - 34:05What kind of things is it using?
-
34:05 - 34:13Anything you've seen before?
-
34:13 - 34:18Oh, somebody come on. I hear the whispering but no one wants to just stand up and be
-
34:18 - 34:20committed.
-
34:20 - 34:23How about
-
34:23 - 34:24a
-
34:24 - 34:27little 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
-
34:27 - 34:29a subset backing, right? That is that
-
34:29 - 34:32I'm not choosing all the letters from this. And in fact there's a subset process,
-
34:32 - 34:35which is deciding whether it's in or out, and then there's a permutation problem,
-
34:35 - 34:37which is actually rearranging them, right?
-
34:37 - 34:40That picking the C, and the R, and the I, and the M, and then kind of rearranging them. So in fact it
-
34:40 - 34:44has kind of a little bit of both, right? Which is what sequence of letters can I
-
34:44 - 34:46extract and then rearrange to make a word - would
-
34:46 - 34:50end up using kind of elements of both of those kinds of recursions sort of
-
34:50 - 34:51mixed together
-
34:51 - 34:55so that when you look at a lot of recursion problems, they end up actually just mapping down to
-
34:55 - 34:59one or the other, or maybe a little bit of both. And so feeling very comfortable with
-
34:59 - 35:00those problems,
-
35:00 - 35:03how you turn them into a recursive backtracker,
-
35:03 - 35:05and how you can recognize, right,
-
35:05 - 35:08their roots inside these other problems, it's kind of a really good first step to
-
35:08 - 35:12becoming kind of a journeyman, in a way, or recursion.
-
35:12 - 35:14So just whenever you see a new problem you start thinking, okay,
-
35:14 - 35:17is it permutations? Is it subset? Or is it something totally new?
-
35:17 - 35:21It's probably much more likely to be the first two then the third, and so
-
35:21 - 35:24trying to use the ones that you feel really comfortable with to kind of branch
-
35:24 - 35:25out to solve
-
35:25 - 35:29similar problems, right, where the domain is a little different - the structure
-
35:29 - 35:35of the code is still very much the same. All right.
-
35:35 - 35:37I've got 10 minutes to teach you about pointers.
-
35:37 - 35:39This should be no problem. Let's
-
35:39 - 35:42go see what that guy back there's doing. Oh, look at
-
35:42 - 35:47that, 38,000 assignments, still has not given up on that S is zero.
-
35:47 - 35:53It's a trooper. Okay.
-
35:53 - 35:57So this is definitely gonna be your first introduction on kind of the first
-
35:57 - 36:01day of talking about this. This is not the only day. So
-
36:01 - 36:03don't get to worried about me trying to do it in 10 minutes. What I'm gonna do is give you
-
36:03 - 36:07the kind of - a little bit of the basics today, and we're gonna follow up with
-
36:07 - 36:10some more stuff tomorrow where we start kind of making use of them and doing something
-
36:10 - 36:11kind of interesting with them.
-
36:11 - 36:13So there is this notion
-
36:13 - 36:17in C++, which is inherited from the C language in fact,
-
36:17 - 36:20of using a variable type called a pointer
-
36:20 - 36:22as part of the things that you operate on.
-
36:22 - 36:26Okay. People tend to have a lot of trepidation. Just the word pointer causes a little bit
-
36:26 - 36:28of fear, kind of
-
36:28 - 36:30to immediately rise in a new programmer.
-
36:30 - 36:34But hopefully we can demystify a little bit, and then also get a little bit of understanding
-
36:34 - 36:38of why there are reasons to be a little bit
-
36:38 - 36:40wary of working with pointers.
-
36:40 - 36:42A pointer is actually an address.
-
36:42 - 36:45So here's a couple things we have to kind of think about a little bit how the
-
36:45 - 36:48machine works to have a vision of what's going on here,
-
36:48 - 36:52that when you declare variables, you
-
36:52 - 36:54know, here I am in main.
-
36:54 - 36:56
-
36:56 - 36:58And I declare,
-
36:58 - 37:02you know, int Num,
-
37:02 - 37:04and string S,
-
37:04 - 37:05that there
-
37:05 - 37:09is space set aside as part of the working memory of this program
-
37:09 - 37:13that is gonna record whatever I assign to Num or S. So if I say Num equals
-
37:13 - 37:1945, what is that? S equals hello, that there
-
37:19 - 37:20has to be memory
-
37:20 - 37:22that's being used to hold onto that.
-
37:22 - 37:27
-
37:27 - 37:28
-
37:28 - 37:32And as you declare variables, right, more of the space is set aside, and, you know, when
-
37:32 - 37:36you initialize it, when you read to it, when you write to it, right, that
-
37:36 - 37:40space is being accessed and updated as you go through. When you open
-
37:40 - 37:44a new scope, right, new variables come in a scope. When you close that scope, really that
-
37:44 - 37:47function, that space gets de-allocated. All this happens on your behalf without you
-
37:47 - 37:50actually taking a really active role in it, but in fact you do have to have a little
-
37:50 - 37:53bit of understanding of that to kind of idea of what a pointer's about,
-
37:53 - 37:56is that there is this just big sequence of
-
37:56 - 37:57data,
-
37:57 - 38:00starting from an address zero. You can think of these things as actually
-
38:00 - 38:02having a little number on them.
-
38:02 - 38:06So maybe this is number 1,000, and this is number
-
38:06 - 38:081,004. In this case, assuming that
-
38:08 - 38:10we're numbering by the byte,
-
38:10 - 38:11which is
-
38:11 - 38:12
-
38:12 - 38:15the smallest chunk of memory we can talk about,
-
38:15 - 38:19and that an integer requires four of those bytes to store all the different
-
38:19 - 38:20patterns for different kinds of numbers
-
38:20 - 38:24so that the bytes from 1,000 to 1,003 are reserved for holding
-
38:24 - 38:27onto the information about 45. And then from 1,000 forward -
-
38:27 - 38:31to however big the string is, which we don't even really know how big it is, so we'll
-
38:31 - 38:33kind of leave it a little bit vague here -
-
38:33 - 38:37is gonna be set aside for storing information about that string.
-
38:37 - 38:38Okay.
-
38:38 - 38:41So usually it's of interest to the compiler, right, to know where things are being
-
38:41 - 38:43stored and what's going on.
-
38:43 - 38:47But it also turns out to be somewhat useful for us to be able to talk about
-
38:47 - 38:50something by address. Instead of saying the variable
-
38:50 - 38:51whose name is Num,
-
38:51 - 38:56I can talk about the variable who lives at location 1,000. And say
-
38:56 - 38:58there's an integer, and
-
38:58 - 39:01I can point to it, or refer to it
-
39:01 - 39:05by saying go look at memory address 1,000, and read or write the contents
-
39:05 - 39:09there that are of integer type. Okay.
-
39:09 - 39:13It seems a little bit odd at first. You're like, well I already have other ways to get to Num.
-
39:13 - 39:16Why is it I want to go out of my way to find another different mechanism that can
-
39:16 - 39:18get me access to that same variable?
-
39:18 - 39:21And we're gonna see that actually there's a lot of flexibility
-
39:21 - 39:23that is being bought by us
-
39:23 - 39:27adding this to our feature set. We can say, well, I could actually have
-
39:27 - 39:29one copy of something.
-
39:29 - 39:32So imagine that you have
-
39:32 - 39:32
-
39:32 - 39:33a system,
-
39:33 - 39:37like, an access system where you have student records, and they're enrolled in a bunch of different
-
39:37 - 39:38courses, that your
-
39:38 - 39:41enrolled in four, five different courses,
-
39:41 - 39:44that when it comes time for a class to know who's in their list, it might be
-
39:44 - 39:45handy for them,
-
39:45 - 39:48instead of actually having a copy of that student's information to have a pointer
-
39:48 - 39:52to one student record, and have a lot of different placers where there are
-
39:52 - 39:55additional pointers taken out to that same location and says, go look at the student who's
-
39:55 - 39:56at address 1,000.
-
39:56 - 39:59I have the students at address 1,000, at 1,026,
-
39:59 - 40:02at, you know, 1,035,
-
40:02 - 40:05whatever those places are, and that that's one way I can talk about what
-
40:05 - 40:09students I have, and those same student addresses might show up in someone else's
-
40:09 - 40:11class list in math 51, or
-
40:11 - 40:13physics, you know, 43 or whatever,
-
40:13 - 40:15and that we are
-
40:15 - 40:18all referring to one copy of the student data without duplicating it.
-
40:18 - 40:22So this idea of being able to refer to stuff not just by name, but by where it lives,
-
40:22 - 40:28is gonna give us some flexibility in terms of how we build things out of that.
-
40:28 - 40:31So let me kind of show you a little bit of the basic operations,
-
40:31 - 40:35and then - and I'll talk a little bit along the way about this thing about why they're
-
40:35 - 40:36scary
-
40:36 - 40:37because
-
40:37 - 40:40using, you know, memory access as your way to get to something is a little
-
40:40 - 40:44bit more error prone and a little bit harder to deal with than
-
40:44 - 40:47some of the more - other operations we have.
-
40:47 - 40:50So what I'm gonna show you here is a little piece of code.
-
40:50 - 40:57It shows some simple use of pointers. All right.
-
40:57 - 40:58So
-
40:58 - 40:59
-
40:59 - 41:02I'm gonna draw some of the variables that are going on here. This
-
41:02 - 41:04is main and it declared
-
41:04 - 41:05an integer
-
41:05 - 41:08whose name is Num, so I
-
41:08 - 41:09draw a box for that, and it
-
41:09 - 41:13declares two pointer variables. So the addition of the asterisk by the name
-
41:13 - 41:14there
-
41:14 - 41:19says that P and Q are pointers to integers.
-
41:19 - 41:23So P and Q themselves are variables
-
41:23 - 41:26that live in the stack. So all the local variables we say
-
41:26 - 41:30live in the stack.
-
41:30 - 41:33They are automatically allocated and de-allocated when you enter a routine. The space for
-
41:33 - 41:36them comes into being. When you leave it, it goes away,
-
41:36 - 41:40and that P and Q are designed not to hold integers themselves. They don't hold numbers,
-
41:40 - 41:44but they hold the address of a number somewhere else.
-
41:44 - 41:47And so the first thing I did with
-
41:47 - 41:48P there was to assign it
-
41:48 - 41:52the address of a new integer variable that came out of the heap. So the
-
41:52 - 41:55new operator is like the new operator in Java.
-
41:55 - 41:59It takes the thing you want to create one of, it makes one of those in the heap,
-
41:59 - 42:02and it returns to you its address. In that way it works exactly like in Java. So, in
-
42:02 - 42:04fact, Java actually
-
42:04 - 42:07has pointers despite what anybody ever told you,
-
42:07 - 42:11that the way you create objects and you use new to access them and stuff like that
-
42:11 - 42:15is exactly the same as it is in C++ as it is
-
42:15 - 42:16pointers behind the scene.
-
42:16 - 42:18So I say P
-
42:18 - 42:20gets the value of a new integer.
-
42:20 - 42:24This memory over here is called the heap.
-
42:24 - 42:27So this is not
-
42:27 - 42:29to confuse you with the idea of
-
42:29 - 42:32the stack ADT. We've been using the [inaudible]
-
42:32 - 42:35but it does kind of - it helps you to remember that the stack actually kind of, like, by
-
42:35 - 42:38the virtue of the way function calls get made, main calls A, which
-
42:38 - 42:42calls B, which calls C, that that memory actually kind of is laid out like a stack.
-
42:42 - 42:46The heap is just this unordered crazy pile of stuff.
-
42:46 - 42:49I ask for new integer, so this might be address 1,000.
-
42:49 - 42:52This might be address 1,004. This might be address 1,008. Typically
-
42:52 - 42:56the stack variables are laid out right next to each other. This could be, like,
-
42:56 - 42:56address
-
42:56 - 42:5932,016 or something over here.
-
42:59 - 43:02Some other larger address. So I've
-
43:02 - 43:03assigned P to be that
-
43:03 - 43:07thing. So what I actually gotten written into P's box is behind the scenes there really is the number,
-
43:07 - 43:10you know, the address, 32,016. What
-
43:10 - 43:14I'm gonna draw is an arrow to remind myself that what it is is it's a
-
43:14 - 43:18location of an integer stored elsewhere.
-
43:18 - 43:20The de-reference operator,
-
43:20 - 43:22which is the first thing we see on this next line,
-
43:22 - 43:25says to follow P
-
43:25 - 43:26and assign it a 10.
-
43:26 - 43:29So this is taking that address that's in P,
-
43:29 - 43:33using it as a location to go look up something, and it says, and go write to that
-
43:33 - 43:35location in address 32,016
-
43:35 - 43:42the number 10.
-
43:42 - 43:47And I said Q equals no int. So Q gets an
-
43:47 - 43:47[inaudible]
-
43:47 - 43:53maybe this is at 23,496.
-
43:53 - 43:55Some other place out there. And so
-
43:55 - 43:58that's actually kind of what's being stored here,
-
43:58 - 44:0023,496.
-
44:00 - 44:03And then I did this thing where I assigned from
-
44:03 - 44:05D referencing P
-
44:05 - 44:09to get an integer, and assign that onto what Q is that has the effect of kind of
-
44:09 - 44:15following P, reading its 10, and then writing it over here. So copying the integers
-
44:15 - 44:19at the end of those two pointers to make them point to the same value.
-
44:19 - 44:22So they point to two different locations, but those locations hold the same integer
-
44:22 - 44:23value
-
44:23 - 44:25that is different
-
44:25 - 44:27than the next line.
-
44:27 - 44:29Without the stars,
-
44:29 - 44:34where I said Q equals P,
-
44:34 - 44:37without the stars on it,
-
44:37 - 44:43it's saying take the address that's in P, and assign it to Q,
-
44:43 - 44:45causing Q and P now to be aliases
-
44:45 - 44:48for the same location.
-
44:48 - 44:52So now I have two different ways of getting to that same piece of memory,
-
44:52 - 44:55either by reaching through P and de-referencing, or reaching through Q and de-referencing
-
44:55 - 44:57it - both of them
-
44:57 - 45:01are reading and writing to that same location in the heap, where the 10 is,
-
45:01 - 45:05and then this one down here's no longer accessible. I sort of lost track of it
-
45:05 - 45:06when I
-
45:06 - 45:08overwrote Q with the
-
45:08 - 45:10copy of P.
-
45:10 - 45:12When I am done
-
45:12 - 45:14in C++ it is my job
-
45:14 - 45:15to delete things
-
45:15 - 45:20that are coming out of the heap.
-
45:20 - 45:24Yes, it should. I'll take that one at 32,016.
-
45:24 - 45:28Whereas in Java, when you say new, and then you stop using something,
-
45:28 - 45:30it figures it out and it does what's called garbage collection to kind of clean up
-
45:30 - 45:31behind you.
-
45:31 - 45:35In C++, things that you new out of the heap are your responsibility to
-
45:35 - 45:36delete.
-
45:36 - 45:40So you delete something when you're done with it. If I'm no longer using this
-
45:40 - 45:42new integer I created in the heap,
-
45:42 - 45:44I say to delete P
-
45:44 - 45:47to allow that memory to be reclaimed.
-
45:47 - 45:51And so that causes this piece of memory to get marked as freed,
-
45:51 - 45:56or reusable, so that a subsequent new call can have that space again
-
45:56 - 45:58and use it for things.
-
45:58 - 46:01I will note that right now, the code as written
-
46:01 - 46:05has a little bit of an error in it because it says delete P. And
-
46:05 - 46:09delete P says we'll follow out to 32 [inaudible] and mark it as
-
46:09 - 46:10available.
-
46:10 - 46:13The next thing I did was said delete Q. Well Q points to the same
-
46:13 - 46:17place P did. So in fact I'm saying take that piece of freed memory and mark it freed
-
46:17 - 46:17again.
-
46:17 - 46:19
-
46:19 - 46:22There is no real guarantee about whether that's gonna do something
-
46:22 - 46:25sensible, or whether it's just gonna ignore me. One thing it could do is just say, well look, that
-
46:25 - 46:27memory's already freed, so
-
46:27 - 46:29you saying to free it twice is kind of stupid.
-
46:29 - 46:33On the other hand, it could still cause some more problems depending on how the
-
46:33 - 46:37heap allocater works, and there's no guarantee. So it becomes very [inaudible] on the
-
46:37 - 46:39programmer to be very careful about this matching, that
-
46:39 - 46:41if you make a new call,
-
46:41 - 46:43you make a delete call. And
-
46:43 - 46:45if you already made a delete call, you don't make another one
-
46:45 - 46:49accidentally. So I really should have that line out of there.
-
46:49 - 46:54The piece of memory that Q originally pointed to, right, I no longer have any way to get to,
-
46:54 - 46:57and so I have no way of making a delete call to it and freeing it. And so this little
-
46:57 - 47:01piece of memory we call an orphan.
-
47:01 - 47:03He's stranded out there in the heap,
-
47:03 - 47:04no way to get back to it,
-
47:04 - 47:09and C++ will not automatically reclaim it for us. So we have
-
47:09 - 47:12created a little bit of a mess for ourselves. If we did that a lot, right,
-
47:12 - 47:16we could end up clogging our heap filled with these orphans,
-
47:16 - 47:19and have to keep getting new memory because the old memory, right, was not
-
47:19 - 47:22being properly reclaimed.
-
47:22 - 47:24We're gonna talk more about this, so this is not
-
47:24 - 47:27the all - end all of pointers, but just a little bit to think about today. We'll
-
47:27 - 47:30come back on Wednesday, talk more about it, and then talk about how we can use
-
47:30 - 47:33this to build linked lists, and that will be
-
47:33 - 47:36fun times for all.
- Title:
- Lecture 11 | Programming Abstractions (Stanford)
- Description:
-
Lecture 11 by Julie Zelenski for the Programming Abstractions Course (CS106B) in the Stanford Computer Science Department.
Julie continues with recursive backtracking and introduces pointers and recursive data. Following, she focuses on solving the problems rather than the exact code and later uses the example of a program that will solve a Sudoku puzzle. She explains that recognizing and looking for patterns between all of the different recursive examples is an important component to learning recursion.
Complete Playlist for the Course:
http://www.youtube.com/view_play_list?p=FE6E58F856038C69CS 106B Course Website:
http://cs106b.stanford.eduStanford Center for Professional Development:
http://scpd.stanford.edu/Stanford University:
http://www.stanford.edu/Stanford University Channel on YouTube:
http://www.youtube.com/stanforduniversity/ - Video Language:
- English
- Duration:
- 47:48
![]() |
N. Ueda edited English subtitles for Lecture 11 | Programming Abstractions (Stanford) | Apr 26, 2013, 11:30 AM |
![]() |
Eunjeong_Kim added a translation | Oct 16, 2012, 7:27 AM |