[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:08.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:08.00,0:00:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:11.00,0:00:22.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional Development.
Dialogue: 0,0:00:22.00,0:00:25.00,Default,,0000,0000,0000,,Okay, so thank you for coming out in the rain.
Dialogue: 0,0:00:25.00,0:00:26.00,Default,,0000,0000,0000,,I
Dialogue: 0,0:00:26.00,0:00:27.00,Default,,0000,0000,0000,,appreciate you
Dialogue: 0,0:00:27.00,0:00:29.00,Default,,0000,0000,0000,,trudging over here and
Dialogue: 0,0:00:29.00,0:00:30.00,Default,,0000,0000,0000,,risking
Dialogue: 0,0:00:30.00,0:00:31.00,Default,,0000,0000,0000,,your health and life.
Dialogue: 0,0:00:31.00,0:00:37.00,Default,,0000,0000,0000,,So I'm gonna do a little diversion here to explain this idea of functions as data before I come back
Dialogue: 0,0:00:37.00,0:00:40.00,Default,,0000,0000,0000,,to fixing the problem we had kind of hit upon at the very end of the last lecture
Dialogue: 0,0:00:40.00,0:00:42.00,Default,,0000,0000,0000,,about set.
Dialogue: 0,0:00:42.00,0:00:44.00,Default,,0000,0000,0000,,So what I'm just gonna show you is
Dialogue: 0,0:00:44.00,0:00:45.00,Default,,0000,0000,0000,,a little bit about
Dialogue: 0,0:00:45.00,0:00:46.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:46.00,0:00:49.00,Default,,0000,0000,0000,,the design of something in C++
Dialogue: 0,0:00:49.00,0:00:52.00,Default,,0000,0000,0000,,that is gonna helpful in solving the problem we'd run into.
Dialogue: 0,0:00:52.00,0:00:55.00,Default,,0000,0000,0000,,What I'm gonna show you here is two pieces of code that plot
Dialogue: 0,0:00:55.00,0:00:57.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:00:57.00,0:01:01.00,Default,,0000,0000,0000,,single value function across the number line. So in this case, the function is that it's the
Dialogue: 0,0:01:01.00,0:01:05.00,Default,,0000,0000,0000,,top one is applying the sine function, the sine wave as it varies across, and then the
Dialogue: 0,0:01:05.00,0:01:06.00,Default,,0000,0000,0000,,square root function
Dialogue: 0,0:01:06.00,0:01:09.00,Default,,0000,0000,0000,,which goes up and has a sloping curve to it,
Dialogue: 0,0:01:09.00,0:01:13.00,Default,,0000,0000,0000,,and that both of these have exactly the same behaviors. They're designed to kind of go into the graphics
Dialogue: 0,0:01:13.00,0:01:17.00,Default,,0000,0000,0000,,window, and they're just using a kind of a very simple kind of hand moving strategy. It
Dialogue: 0,0:01:17.00,0:01:21.00,Default,,0000,0000,0000,,starts on a particular location based on what the value of sine is here,
Dialogue: 0,0:01:21.00,0:01:23.00,Default,,0000,0000,0000,,and then over a particular interval
Dialogue: 0,0:01:23.00,0:01:24.00,Default,,0000,0000,0000,,at 0.1
Dialogue: 0,0:01:24.00,0:01:28.00,Default,,0000,0000,0000,,of one tenth of an inch, it plots the next point and connects a line between
Dialogue: 0,0:01:28.00,0:01:31.00,Default,,0000,0000,0000,,them. So it does a simple kind of line approximation of what
Dialogue: 0,0:01:31.00,0:01:34.00,Default,,0000,0000,0000,,that function looks like over the interval you asked it to plot.
Dialogue: 0,0:01:34.00,0:01:37.00,Default,,0000,0000,0000,,The same code is being used here for plotting the square root.
Dialogue: 0,0:01:37.00,0:01:41.00,Default,,0000,0000,0000,,And the thing to note and I tried to highlight by putting it in blue here was that every other
Dialogue: 0,0:01:41.00,0:01:45.00,Default,,0000,0000,0000,,part of the code is exactly the same except for those two calls where I need to know what's
Dialogue: 0,0:01:45.00,0:01:48.00,Default,,0000,0000,0000,,the value of square root starting at this particular
Dialogue: 0,0:01:48.00,0:01:51.00,Default,,0000,0000,0000,,X. So starting at Value 1,
Dialogue: 0,0:01:51.00,0:01:53.00,Default,,0000,0000,0000,,what is sine of one? What is square root of one? As I
Dialogue: 0,0:01:53.00,0:01:57.00,Default,,0000,0000,0000,,work my way across the interval, what's a square root of 1.1, 1.2, 1.3 and
Dialogue: 0,0:01:57.00,0:01:59.00,Default,,0000,0000,0000,,sine of those same values?
Dialogue: 0,0:01:59.00,0:02:03.00,Default,,0000,0000,0000,,And so everything about the code is functionally identical. It's kind of frustrating
Dialogue: 0,0:02:03.00,0:02:07.00,Default,,0000,0000,0000,,to look at it, though, and realize if I wanted to plot a bunch of other things -I also wanna be able to plot
Dialogue: 0,0:02:07.00,0:02:09.00,Default,,0000,0000,0000,,the cosine function, or
Dialogue: 0,0:02:09.00,0:02:12.00,Default,,0000,0000,0000,,some other function of my own creation
Dialogue: 0,0:02:12.00,0:02:13.00,Default,,0000,0000,0000,,-across this interval
Dialogue: 0,0:02:13.00,0:02:17.00,Default,,0000,0000,0000,,that I keep having to copy and paste this code and duplicate it.
Dialogue: 0,0:02:17.00,0:02:21.00,Default,,0000,0000,0000,,And so one of the things that hopefully your 106A and prior experiences really
Dialogue: 0,0:02:21.00,0:02:24.00,Default,,0000,0000,0000,,heightened your attention to is
Dialogue: 0,0:02:24.00,0:02:26.00,Default,,0000,0000,0000,,if I have the same piece of code
Dialogue: 0,0:02:26.00,0:02:30.00,Default,,0000,0000,0000,,in multiple places, I ought to be able to unify it. I ought to be able to make there be a plot
Dialogue: 0,0:02:30.00,0:02:31.00,Default,,0000,0000,0000,,function
Dialogue: 0,0:02:31.00,0:02:36.00,Default,,0000,0000,0000,,that can handle both sine and square root without actually having to distinguish it by copy and pasting,
Dialogue: 0,0:02:36.00,0:02:38.00,Default,,0000,0000,0000,,so I wanna unify these two.
Dialogue: 0,0:02:38.00,0:02:43.00,Default,,0000,0000,0000,,And so there is -the mechanism that we're gonna use kinda follows naturally if you don't let yourself get
Dialogue: 0,0:02:43.00,0:02:45.00,Default,,0000,0000,0000,,too tripped up by what it means.
Dialogue: 0,0:02:45.00,0:02:48.00,Default,,0000,0000,0000,,Just imagine that the parameter for example going into the function right now are the start and the stop,
Dialogue: 0,0:02:48.00,0:02:49.00,Default,,0000,0000,0000,,the interval
Dialogue: 0,0:02:49.00,0:02:52.00,Default,,0000,0000,0000,,from X is one to five.
Dialogue: 0,0:02:52.00,0:02:55.00,Default,,0000,0000,0000,,What we'd like to do is further parameterize the function.
Dialogue: 0,0:02:55.00,0:02:58.00,Default,,0000,0000,0000,,We'd like to add a third argument to it, which is to say
Dialogue: 0,0:02:58.00,0:03:03.00,Default,,0000,0000,0000,,and when you're ready to know what function you're plotting, here's the one to use.
Dialogue: 0,0:03:03.00,0:03:04.00,Default,,0000,0000,0000,,I'd like you to plot
Dialogue: 0,0:03:04.00,0:03:08.00,Default,,0000,0000,0000,,sine over the interval start to stop. I'd like you to plot square root over that. So we added the third argument,
Dialogue: 0,0:03:08.00,0:03:11.00,Default,,0000,0000,0000,,which was the function we wanted to invoke there.
Dialogue: 0,0:03:11.00,0:03:16.00,Default,,0000,0000,0000,,Then we would be able to unify this down to where we had one generic plot function.
Dialogue: 0,0:03:16.00,0:03:19.00,Default,,0000,0000,0000,,The good news is that this does actually
Dialogue: 0,0:03:19.00,0:03:20.00,Default,,0000,0000,0000,,have
Dialogue: 0,0:03:20.00,0:03:23.00,Default,,0000,0000,0000,,support features in the C++ language that let us do this.
Dialogue: 0,0:03:23.00,0:03:26.00,Default,,0000,0000,0000,,The syntax for it is a little bit unusual, and
Dialogue: 0,0:03:26.00,0:03:29.00,Default,,0000,0000,0000,,if you think about it too much, it can actually make your head hurt a little bit, think about what
Dialogue: 0,0:03:29.00,0:03:33.00,Default,,0000,0000,0000,,it's doing. But you can actually use a function, a function's name
Dialogue: 0,0:03:33.00,0:03:35.00,Default,,0000,0000,0000,,and the code that is associated with that name,
Dialogue: 0,0:03:35.00,0:03:37.00,Default,,0000,0000,0000,,as a piece of data
Dialogue: 0,0:03:37.00,0:03:41.00,Default,,0000,0000,0000,,that not just -you think of the code as we're calling this function, and
Dialogue: 0,0:03:41.00,0:03:44.00,Default,,0000,0000,0000,,we're moving these things around, and executing things.
Dialogue: 0,0:03:44.00,0:03:47.00,Default,,0000,0000,0000,,The things that we tend to be executing and operating on you think of as being integers, and strings,
Dialogue: 0,0:03:47.00,0:03:49.00,Default,,0000,0000,0000,,and characters, and files.
Dialogue: 0,0:03:49.00,0:03:52.00,Default,,0000,0000,0000,,But you can also extend your notion of what's data
Dialogue: 0,0:03:52.00,0:03:54.00,Default,,0000,0000,0000,,to include the code you wrote
Dialogue: 0,0:03:54.00,0:03:56.00,Default,,0000,0000,0000,,as part of the possibilities.
Dialogue: 0,0:03:56.00,0:03:59.00,Default,,0000,0000,0000,,So in this case, I've added that third argument that I wanted to plot,
Dialogue: 0,0:03:59.00,0:04:02.00,Default,,0000,0000,0000,,and this
Dialogue: 0,0:04:02.00,0:04:06.00,Default,,0000,0000,0000,,syntax here that's a little bit unusual to you, and I'll kind of identify it, is that the
Dialogue: 0,0:04:06.00,0:04:09.00,Default,,0000,0000,0000,,name of the parameter is actually FN.
Dialogue: 0,0:04:09.00,0:04:12.00,Default,,0000,0000,0000,,Its name is enclosed in parentheses there.
Dialogue: 0,0:04:12.00,0:04:16.00,Default,,0000,0000,0000,,And then to the right would be a list of the arguments
Dialogue: 0,0:04:16.00,0:04:17.00,Default,,0000,0000,0000,,or the prototype
Dialogue: 0,0:04:17.00,0:04:21.00,Default,,0000,0000,0000,,information about this function, and on the left is its return value.
Dialogue: 0,0:04:21.00,0:04:24.00,Default,,0000,0000,0000,,So what this says is you have two doubles, the start and stop,
Dialogue: 0,0:04:24.00,0:04:26.00,Default,,0000,0000,0000,,and the third thing in there isn't a double at all. It is a
Dialogue: 0,0:04:26.00,0:04:27.00,Default,,0000,0000,0000,,function
Dialogue: 0,0:04:27.00,0:04:32.00,Default,,0000,0000,0000,,of one double that returns a double, so a single value function that operates on doubles
Dialogue: 0,0:04:32.00,0:04:33.00,Default,,0000,0000,0000,,here.
Dialogue: 0,0:04:33.00,0:04:36.00,Default,,0000,0000,0000,,That is the syntax in C++ for specifying what you want coming in here
Dialogue: 0,0:04:36.00,0:04:37.00,Default,,0000,0000,0000,,is
Dialogue: 0,0:04:37.00,0:04:41.00,Default,,0000,0000,0000,,not a double, not a ray of doubles, anything funky like that. It is a function of a
Dialogue: 0,0:04:41.00,0:04:43.00,Default,,0000,0000,0000,,double that returns a double.
Dialogue: 0,0:04:43.00,0:04:45.00,Default,,0000,0000,0000,,And then in the body of this code,
Dialogue: 0,0:04:45.00,0:04:47.00,Default,,0000,0000,0000,,when I say FN here
Dialogue: 0,0:04:47.00,0:04:50.00,Default,,0000,0000,0000,,where I would've said sine, or square root, or identified
Dialogue: 0,0:04:50.00,0:04:51.00,Default,,0000,0000,0000,,a particular function,
Dialogue: 0,0:04:51.00,0:04:53.00,Default,,0000,0000,0000,,it's using the parameter
Dialogue: 0,0:04:53.00,0:04:57.00,Default,,0000,0000,0000,,that was passed in by the client, so it says call the client's function
Dialogue: 0,0:04:57.00,0:04:58.00,Default,,0000,0000,0000,,passing these values
Dialogue: 0,0:04:58.00,0:05:01.00,Default,,0000,0000,0000,,to plot over the range
Dialogue: 0,0:05:01.00,0:05:03.00,Default,,0000,0000,0000,,using their function
Dialogue: 0,0:05:03.00,0:05:07.00,Default,,0000,0000,0000,,in. So the idea is that valid calls to plot now become things like plot -and then give it an
Dialogue: 0,0:05:07.00,0:05:09.00,Default,,0000,0000,0000,,interval, zero to two,
Dialogue: 0,0:05:09.00,0:05:11.00,Default,,0000,0000,0000,,and you give the name of a function:
Dialogue: 0,0:05:11.00,0:05:15.00,Default,,0000,0000,0000,,the sine function, which comes out of the math library, the square root function,
Dialogue: 0,0:05:15.00,0:05:16.00,Default,,0000,0000,0000,,also in the math library.
Dialogue: 0,0:05:16.00,0:05:19.00,Default,,0000,0000,0000,,It could be that the function is something you wrote yourself,
Dialogue: 0,0:05:19.00,0:05:21.00,Default,,0000,0000,0000,,the my function.
Dialogue: 0,0:05:21.00,0:05:25.00,Default,,0000,0000,0000,,In order for this to be valid though, you can't just put any old function name there. It is
Dialogue: 0,0:05:25.00,0:05:27.00,Default,,0000,0000,0000,,actually being quite specific about it
Dialogue: 0,0:05:27.00,0:05:30.00,Default,,0000,0000,0000,,that plot was to find [inaudible]. It took a double, returned a double. That's the kind of function
Dialogue: 0,0:05:30.00,0:05:33.00,Default,,0000,0000,0000,,that you can give it, so any function that has that
Dialogue: 0,0:05:33.00,0:05:36.00,Default,,0000,0000,0000,,prototype, so it matches that
Dialogue: 0,0:05:36.00,0:05:40.00,Default,,0000,0000,0000,,format is an acceptable one to pass in. If you try to pass something that actually
Dialogue: 0,0:05:40.00,0:05:42.00,Default,,0000,0000,0000,,just does some other kind of function,
Dialogue: 0,0:05:42.00,0:05:45.00,Default,,0000,0000,0000,,it doesn't have the same prototype, so the get line that takes no arguments and returns a string just
Dialogue: 0,0:05:45.00,0:05:47.00,Default,,0000,0000,0000,,doesn't match on any front.
Dialogue: 0,0:05:47.00,0:05:51.00,Default,,0000,0000,0000,,And if I try to say here, plot the get line function of the integral two to five,
Dialogue: 0,0:05:51.00,0:05:53.00,Default,,0000,0000,0000,,it will quite rightfully complain to me
Dialogue: 0,0:05:53.00,0:05:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:05:54.00,0:05:56.00,Default,,0000,0000,0000,,that that just doesn't make sense.
Dialogue: 0,0:05:56.00,0:05:57.00,Default,,0000,0000,0000,,That's because it doesn't match.
Dialogue: 0,0:05:57.00,0:06:02.00,Default,,0000,0000,0000,,So a little bit of syntax here, but actually kind of a very powerful thing, and it allows us to write to
Dialogue: 0,0:06:02.00,0:06:05.00,Default,,0000,0000,0000,,an addition to kind of parameterizing on these things you think of as traditional
Dialogue: 0,0:06:05.00,0:06:07.00,Default,,0000,0000,0000,,data, integers, and strings, and whatnot. It's
Dialogue: 0,0:06:07.00,0:06:12.00,Default,,0000,0000,0000,,also say as part of your operations, you may need to make a call out to some other function.
Dialogue: 0,0:06:12.00,0:06:15.00,Default,,0000,0000,0000,,Let's leave it open what that function is and allow the client to specify what function
Dialogue: 0,0:06:15.00,0:06:20.00,Default,,0000,0000,0000,,to call at that time. So in this case for a plot, what function that you're trying to plot, let the client
Dialogue: 0,0:06:20.00,0:06:21.00,Default,,0000,0000,0000,,tell you,
Dialogue: 0,0:06:21.00,0:06:29.00,Default,,0000,0000,0000,,and then based on what they ask you to plot you can plot different things. All right. Way in the back. Is
Dialogue: 0,0:06:29.00,0:06:34.00,Default,,0000,0000,0000,,there a similar setup for multivariable functions [inaudible]? Certainly. So all I would
Dialogue: 0,0:06:34.00,0:06:37.00,Default,,0000,0000,0000,,need to do if this was a function that took a couple arguments, I would say double comma double comma int. If it
Dialogue: 0,0:06:37.00,0:06:42.00,Default,,0000,0000,0000,,returned void, [inaudible] returned. Sometimes it looks a little bit like the prototype kinda taken out of context
Dialogue: 0,0:06:42.00,0:06:43.00,Default,,0000,0000,0000,,and stuffed in there,
Dialogue: 0,0:06:43.00,0:06:46.00,Default,,0000,0000,0000,,and then those parens around the function are a very important part of that
Dialogue: 0,0:06:46.00,0:06:50.00,Default,,0000,0000,0000,,which is telling you yeah, this is a function of these
Dialogue: 0,0:06:50.00,0:06:52.00,Default,,0000,0000,0000,,with this prototype information.
Dialogue: 0,0:06:52.00,0:06:54.00,Default,,0000,0000,0000,,Behind you. No? You're good now. Somebody else? Over here? Is that FN a fixed
Dialogue: 0,0:06:54.00,0:06:56.00,Default,,0000,0000,0000,,name
Dialogue: 0,0:06:56.00,0:06:57.00,Default,,0000,0000,0000,,
Dialogue: 0,0:06:57.00,0:07:01.00,Default,,0000,0000,0000,,[inaudible]? No. It's just like any parameter name. You get to pick it. So I could've called it plot function, my function,
Dialogue: 0,0:07:01.00,0:07:08.00,Default,,0000,0000,0000,,your function, whatever I wanted. Here
Dialogue: 0,0:07:08.00,0:07:12.00,Default,,0000,0000,0000,,in the front. [Inaudible] Java? So Java doesn't really have a similar mechanism that looks like this. C does, so C++ inherits it
Dialogue: 0,0:07:12.00,0:07:14.00,Default,,0000,0000,0000,,from
Dialogue: 0,0:07:14.00,0:07:18.00,Default,,0000,0000,0000,,C. There are other ways you try to accomplish this in Java. It tries to support the same functionality in the end, but it
Dialogue: 0,0:07:18.00,0:07:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:19.00,0:07:22.00,Default,,0000,0000,0000,,uses a pretty different approach than a functions as
Dialogue: 0,0:07:22.00,0:07:27.00,Default,,0000,0000,0000,,data approach. [Inaudible]?
Dialogue: 0,0:07:27.00,0:07:28.00,Default,,0000,0000,0000,,Can you pass like a
Dialogue: 0,0:07:28.00,0:07:31.00,Default,,0000,0000,0000,,method, like an operator? So typically not.
Dialogue: 0,0:07:31.00,0:07:35.00,Default,,0000,0000,0000,,This syntax that's being used here is for a free function, a function
Dialogue: 0,0:07:35.00,0:07:38.00,Default,,0000,0000,0000,,that's kind of out in the global namespace, that level.
Dialogue: 0,0:07:38.00,0:07:42.00,Default,,0000,0000,0000,,There is a different syntax for passing a method, which is a little bit more messy,
Dialogue: 0,0:07:42.00,0:07:46.00,Default,,0000,0000,0000,,and we won't tend to need it, so I won't go there with you, but it does exist. It just as it stands
Dialogue: 0,0:07:46.00,0:07:50.00,Default,,0000,0000,0000,,does not want a method. It wants a function. So
Dialogue: 0,0:07:50.00,0:07:54.00,Default,,0000,0000,0000,,a method meaning member function of a class.
Dialogue: 0,0:07:54.00,0:07:56.00,Default,,0000,0000,0000,,Okay, so let me -that was kind of just to
Dialogue: 0,0:07:56.00,0:08:00.00,Default,,0000,0000,0000,,set the groundwork for the problem we were trying to solve in set,
Dialogue: 0,0:08:00.00,0:08:05.00,Default,,0000,0000,0000,,which was set is holding this collection of elements that the client has stuffed in there. It's
Dialogue: 0,0:08:05.00,0:08:05.00,Default,,0000,0000,0000,,a generic
Dialogue: 0,0:08:05.00,0:08:07.00,Default,,0000,0000,0000,,templative class, so it doesn't
Dialogue: 0,0:08:07.00,0:08:11.00,Default,,0000,0000,0000,,have any preconceived notion about what's being stored. Are the strings? Are they student structures?
Dialogue: 0,0:08:11.00,0:08:13.00,Default,,0000,0000,0000,,Are they integers?
Dialogue: 0,0:08:13.00,0:08:17.00,Default,,0000,0000,0000,,And that in order to perform its operations efficiently, it actually is using this
Dialogue: 0,0:08:17.00,0:08:22.00,Default,,0000,0000,0000,,notion of ordering, keeping them in an order so that it can iterate an order. It can quickly find on the basis
Dialogue: 0,0:08:22.00,0:08:27.00,Default,,0000,0000,0000,,of using order to quickly decide where something has to be and if it's present in the collection.
Dialogue: 0,0:08:27.00,0:08:29.00,Default,,0000,0000,0000,,So how does it know how to compare
Dialogue: 0,0:08:29.00,0:08:31.00,Default,,0000,0000,0000,,something that's of unknown type?
Dialogue: 0,0:08:31.00,0:08:36.00,Default,,0000,0000,0000,,Well, what it does is it has a default strategy. It makes an assumption that
Dialogue: 0,0:08:36.00,0:08:39.00,Default,,0000,0000,0000,,if I used equals equals and less than that would tell me kinda where to go.
Dialogue: 0,0:08:39.00,0:08:42.00,Default,,0000,0000,0000,,And so it's got this idea that it wants to know. We'll give it two things.
Dialogue: 0,0:08:42.00,0:08:47.00,Default,,0000,0000,0000,,Are they the same thing? In which case, it uses kinda the zero to show the ordering between them. If one
Dialogue: 0,0:08:47.00,0:08:51.00,Default,,0000,0000,0000,,precedes the other, it wants to have some negative number that says well this one precedes it, or some
Dialogue: 0,0:08:51.00,0:08:53.00,Default,,0000,0000,0000,,positive number
Dialogue: 0,0:08:53.00,0:08:54.00,Default,,0000,0000,0000,,if it follows it.
Dialogue: 0,0:08:54.00,0:08:57.00,Default,,0000,0000,0000,,So it applies this operation to the [inaudible] that
Dialogue: 0,0:08:57.00,0:09:02.00,Default,,0000,0000,0000,,are there, and for strings, and ints, and doubles, and characters,
Dialogue: 0,0:09:02.00,0:09:04.00,Default,,0000,0000,0000,,this works perfectly well.
Dialogue: 0,0:09:04.00,0:09:08.00,Default,,0000,0000,0000,,And so that's how without us going out of our way, we can have sets of things
Dialogue: 0,0:09:08.00,0:09:11.00,Default,,0000,0000,0000,,that respond to the built in relational operators
Dialogue: 0,0:09:11.00,0:09:14.00,Default,,0000,0000,0000,,without any special effort as a client.
Dialogue: 0,0:09:14.00,0:09:17.00,Default,,0000,0000,0000,,But what we can get into trouble with right is when
Dialogue: 0,0:09:17.00,0:09:20.00,Default,,0000,0000,0000,,equals equals less than don't make sense for type.
Dialogue: 0,0:09:20.00,0:09:24.00,Default,,0000,0000,0000,,So let me just go actually type some code, and I'll show you. I have it on the slide, but I'm gonna -wow,
Dialogue: 0,0:09:24.00,0:09:29.00,Default,,0000,0000,0000,,this chair suddenly got really short. [Inaudible] fix that. Okay.
Dialogue: 0,0:09:29.00,0:09:30.00,Default,,0000,0000,0000,,
Dialogue: 0,0:09:30.00,0:09:33.00,Default,,0000,0000,0000,,We'll go over here because I think it's better just to see it really happening,
Dialogue: 0,0:09:33.00,0:09:36.00,Default,,0000,0000,0000,,so I'm gonna ignore this piece of code because it's not what I wanted.
Dialogue: 0,0:09:36.00,0:09:40.00,Default,,0000,0000,0000,,But if I make some student T structure,
Dialogue: 0,0:09:40.00,0:09:40.00,Default,,0000,0000,0000,,and it's got
Dialogue: 0,0:09:40.00,0:09:44.00,Default,,0000,0000,0000,,the first and last name, and it's got the ID number,
Dialogue: 0,0:09:44.00,0:09:48.00,Default,,0000,0000,0000,,and maybe that's all I want for now
Dialogue: 0,0:09:48.00,0:09:48.00,Default,,0000,0000,0000,,-that if
Dialogue: 0,0:09:48.00,0:09:51.00,Default,,0000,0000,0000,,down in my main -can't
Dialogue: 0,0:09:51.00,0:09:54.00,Default,,0000,0000,0000,,find my main. There it is. I'm
Dialogue: 0,0:09:54.00,0:09:56.00,Default,,0000,0000,0000,,gonna need that piece of code later, so I'm gonna leave it there.
Dialogue: 0,0:09:56.00,0:09:58.00,Default,,0000,0000,0000,,If I make a set,
Dialogue: 0,0:09:58.00,0:10:05.00,Default,,0000,0000,0000,,and I say I'd like a set of students -my class
Dialogue: 0,0:10:05.00,0:10:09.00,Default,,0000,0000,0000,,-and I do this. And so I feel like I haven't gotten [inaudible]. I made this structure. I
Dialogue: 0,0:10:09.00,0:10:14.00,Default,,0000,0000,0000,,say I'd like to make a set of students, that each student is in the class exactly once and I don't need any duplicates,
Dialogue: 0,0:10:14.00,0:10:18.00,Default,,0000,0000,0000,,and I go through the process of trying to compile this, it's gonna give me some complaints.
Dialogue: 0,0:10:18.00,0:10:21.00,Default,,0000,0000,0000,,And its complaint, which is a little bit hard to see up here, is
Dialogue: 0,0:10:21.00,0:10:26.00,Default,,0000,0000,0000,,there's no match for operator equals equals in one, equals equals two, and operator less than in
Dialogue: 0,0:10:26.00,0:10:27.00,Default,,0000,0000,0000,,one equals
Dialogue: 0,0:10:27.00,0:10:30.00,Default,,0000,0000,0000,,two. So it's kind of showing me another piece of code that's kind of a
Dialogue: 0,0:10:30.00,0:10:35.00,Default,,0000,0000,0000,,hidden piece of code I haven't actually seen directly, which is this operator compare function.
Dialogue: 0,0:10:35.00,0:10:37.00,Default,,0000,0000,0000,,And that is the one that the set is using, as
Dialogue: 0,0:10:37.00,0:10:40.00,Default,,0000,0000,0000,,it has this idea of what's the way it should compare two things. It says well I have some of this
Dialogue: 0,0:10:40.00,0:10:46.00,Default,,0000,0000,0000,,operator compare that works generically on any type of things using equals equals and less than. And
Dialogue: 0,0:10:46.00,0:10:50.00,Default,,0000,0000,0000,,if I click up here on the instantiate from here, it's gonna help me to understand what caused
Dialogue: 0,0:10:50.00,0:10:52.00,Default,,0000,0000,0000,,this problem.
Dialogue: 0,0:10:52.00,0:10:53.00,Default,,0000,0000,0000,,The problem was caused by
Dialogue: 0,0:10:53.00,0:10:57.00,Default,,0000,0000,0000,,trying to create a set who was holding student T.
Dialogue: 0,0:10:57.00,0:11:00.00,Default,,0000,0000,0000,,And so this gives you a little bit of an insight on how the template
Dialogue: 0,0:11:00.00,0:11:02.00,Default,,0000,0000,0000,,operations are handled by the compiler, that
Dialogue: 0,0:11:02.00,0:11:06.00,Default,,0000,0000,0000,,I have built this whole set class, and it depends on there being equals equals and less than
Dialogue: 0,0:11:06.00,0:11:08.00,Default,,0000,0000,0000,,working for the type.
Dialogue: 0,0:11:08.00,0:11:13.00,Default,,0000,0000,0000,,The fact that it didn't work for student T wasn't a cause for alarm until
Dialogue: 0,0:11:13.00,0:11:15.00,Default,,0000,0000,0000,,I actually tried to instantiate
Dialogue: 0,0:11:15.00,0:11:18.00,Default,,0000,0000,0000,,it. So at the point where I said I'd like to make a set holding student
Dialogue: 0,0:11:18.00,0:11:22.00,Default,,0000,0000,0000,,T, the first point where the compiler actually goes through the process of generating a whole set
Dialogue: 0,0:11:22.00,0:11:25.00,Default,,0000,0000,0000,,class, the set angle brackets student T,
Dialogue: 0,0:11:25.00,0:11:29.00,Default,,0000,0000,0000,,filling in all the details, kinda working it all out, making the add, and contains, and whatever
Dialogue: 0,0:11:29.00,0:11:32.00,Default,,0000,0000,0000,,operations, and then in the process of those, those
Dialogue: 0,0:11:32.00,0:11:36.00,Default,,0000,0000,0000,,things are making calls that try to take student T objects and compare them using less than and
Dialogue: 0,0:11:36.00,0:11:37.00,Default,,0000,0000,0000,,equals equals.
Dialogue: 0,0:11:37.00,0:11:39.00,Default,,0000,0000,0000,,And that causes that code to fail.
Dialogue: 0,0:11:39.00,0:11:42.00,Default,,0000,0000,0000,,So the code that's really failing is kind of somewhere in the class library,
Dialogue: 0,0:11:42.00,0:11:44.00,Default,,0000,0000,0000,,but it's failing because
Dialogue: 0,0:11:44.00,0:11:49.00,Default,,0000,0000,0000,,the things that we're passing through and instantiating for don't work with that
Dialogue: 0,0:11:49.00,0:11:50.00,Default,,0000,0000,0000,,setup.
Dialogue: 0,0:11:50.00,0:11:52.00,Default,,0000,0000,0000,,So it's something we've gotta
Dialogue: 0,0:11:52.00,0:11:54.00,Default,,0000,0000,0000,,fix, we've gotta do something about.
Dialogue: 0,0:11:54.00,0:11:59.00,Default,,0000,0000,0000,,Let me go back here and say what am I gonna do. Well, so
Dialogue: 0,0:11:59.00,0:12:01.00,Default,,0000,0000,0000,,there's my error message. Same one,
Dialogue: 0,0:12:01.00,0:12:04.00,Default,,0000,0000,0000,,right? Saying yeah, you can't do that
Dialogue: 0,0:12:04.00,0:12:05.00,Default,,0000,0000,0000,,with a [inaudible]. Well, what
Dialogue: 0,0:12:05.00,0:12:06.00,Default,,0000,0000,0000,,we do
Dialogue: 0,0:12:06.00,0:12:09.00,Default,,0000,0000,0000,,is we use this notion of functions as data
Dialogue: 0,0:12:09.00,0:12:12.00,Default,,0000,0000,0000,,to work out a solution for this problem
Dialogue: 0,0:12:12.00,0:12:15.00,Default,,0000,0000,0000,,that if you think about kinda what's going on, the set actually knows everything about how
Dialogue: 0,0:12:15.00,0:12:19.00,Default,,0000,0000,0000,,to store things. It's a very fancy efficient structure that says given your things, keeps them
Dialogue: 0,0:12:19.00,0:12:20.00,Default,,0000,0000,0000,,in order, and
Dialogue: 0,0:12:20.00,0:12:22.00,Default,,0000,0000,0000,,it manages to update, and
Dialogue: 0,0:12:22.00,0:12:24.00,Default,,0000,0000,0000,,insert, and search that thing very efficiently.
Dialogue: 0,0:12:24.00,0:12:28.00,Default,,0000,0000,0000,,But it doesn't know given any two random things how to compare them other than this assumption
Dialogue: 0,0:12:28.00,0:12:32.00,Default,,0000,0000,0000,,it was making about less than and equals equals being a way to tell.
Dialogue: 0,0:12:32.00,0:12:37.00,Default,,0000,0000,0000,,If it wants to have sort of a more sophisticated handling of that, what it needs to do is cooperate
Dialogue: 0,0:12:37.00,0:12:38.00,Default,,0000,0000,0000,,with the client -that
Dialogue: 0,0:12:38.00,0:12:43.00,Default,,0000,0000,0000,,the implementer of the set can't do it all. So there's these two programmers that
Dialogue: 0,0:12:43.00,0:12:44.00,Default,,0000,0000,0000,,need to work in harmony.
Dialogue: 0,0:12:44.00,0:12:50.00,Default,,0000,0000,0000,,So what the set does is it allows for the client to specify by providing a function.
Dialogue: 0,0:12:50.00,0:12:54.00,Default,,0000,0000,0000,,It says well when I need to compare two things, how about you give me the name of a function
Dialogue: 0,0:12:54.00,0:12:58.00,Default,,0000,0000,0000,,that when given two elements will return to me their ordering, this integer zero,
Dialogue: 0,0:12:58.00,0:13:00.00,Default,,0000,0000,0000,,negative, positive that tells me how to put them in place.
Dialogue: 0,0:13:00.00,0:13:05.00,Default,,0000,0000,0000,,And so the set kind of writes all of its operations in terms of well there's some function I can call, this function that
Dialogue: 0,0:13:05.00,0:13:07.00,Default,,0000,0000,0000,,will compare two things.
Dialogue: 0,0:13:07.00,0:13:11.00,Default,,0000,0000,0000,,If they don't specify one, I'll use this default one that maps them to the relationals, but if they do give
Dialogue: 0,0:13:11.00,0:13:15.00,Default,,0000,0000,0000,,me one, I'll just ask them to do the comparison. And so then as its doing its searching and inserting
Dialogue: 0,0:13:15.00,0:13:16.00,Default,,0000,0000,0000,,and whatnot,
Dialogue: 0,0:13:16.00,0:13:19.00,Default,,0000,0000,0000,,it's calling back. We call that calling back to the client.
Dialogue: 0,0:13:19.00,0:13:22.00,Default,,0000,0000,0000,,So the client writes a function. If I wanna put
Dialogue: 0,0:13:22.00,0:13:25.00,Default,,0000,0000,0000,,student Ts into a set,
Dialogue: 0,0:13:25.00,0:13:28.00,Default,,0000,0000,0000,,then I need to say when you compare two student Ts, what do you look at to know if they're
Dialogue: 0,0:13:28.00,0:13:29.00,Default,,0000,0000,0000,,the same or how to order them.
Dialogue: 0,0:13:29.00,0:13:31.00,Default,,0000,0000,0000,,So maybe I'm gonna order them by ID number.
Dialogue: 0,0:13:31.00,0:13:33.00,Default,,0000,0000,0000,,Maybe I'm gonna use their first and last name.
Dialogue: 0,0:13:33.00,0:13:37.00,Default,,0000,0000,0000,,Whatever it means for two things to be equal and have some sense of order,
Dialogue: 0,0:13:37.00,0:13:38.00,Default,,0000,0000,0000,,I supply
Dialogue: 0,0:13:38.00,0:13:40.00,Default,,0000,0000,0000,,-I write the function,
Dialogue: 0,0:13:40.00,0:13:43.00,Default,,0000,0000,0000,,and then I pass it to the set constructor.
Dialogue: 0,0:13:43.00,0:13:44.00,Default,,0000,0000,0000,,I say here's the function to use.
Dialogue: 0,0:13:44.00,0:13:49.00,Default,,0000,0000,0000,,The set will hold on to that function. So I say here's the compare student structure function.
Dialogue: 0,0:13:49.00,0:13:52.00,Default,,0000,0000,0000,,It holds onto that name, and when needed it calls back.
Dialogue: 0,0:13:52.00,0:13:53.00,Default,,0000,0000,0000,,It says I'm
Dialogue: 0,0:13:53.00,0:13:57.00,Default,,0000,0000,0000,,about to go look for a student structure. Is this the one? Well, I don't know if two student structures are
Dialogue: 0,0:13:57.00,0:14:01.00,Default,,0000,0000,0000,,the same. I'll ask the client. Here's two student structures. Are they the same?
Dialogue: 0,0:14:01.00,0:14:02.00,Default,,0000,0000,0000,,And then
Dialogue: 0,0:14:02.00,0:14:06.00,Default,,0000,0000,0000,,as needed, it'll keep looking or
Dialogue: 0,0:14:06.00,0:14:09.00,Default,,0000,0000,0000,,insert and add and do whatever I need to do.
Dialogue: 0,0:14:09.00,0:14:13.00,Default,,0000,0000,0000,,So let's go back over here.
Dialogue: 0,0:14:13.00,0:14:19.00,Default,,0000,0000,0000,,I'll write a little function. So the
Dialogue: 0,0:14:19.00,0:14:21.00,Default,,0000,0000,0000,,prototype for it is it takes two elem Ts
Dialogue: 0,0:14:21.00,0:14:24.00,Default,,0000,0000,0000,,and it returns an int.
Dialogue: 0,0:14:24.00,0:14:31.00,Default,,0000,0000,0000,,That int is expected to have a value zero if they are the same,
Dialogue: 0,0:14:31.00,0:14:33.00,Default,,0000,0000,0000,,and a value that is negative if
Dialogue: 0,0:14:33.00,0:14:37.00,Default,,0000,0000,0000,,the first argument precedes the second. So if A is less than B, returns some negative
Dialogue: 0,0:14:37.00,0:14:41.00,Default,,0000,0000,0000,,thing. You can return negative one, or negative 100, or negative one million,
Dialogue: 0,0:14:41.00,0:14:42.00,Default,,0000,0000,0000,,but
Dialogue: 0,0:14:42.00,0:14:45.00,Default,,0000,0000,0000,,you need to return some negative value. And then if A [cuts
Dialogue: 0,0:14:45.00,0:14:47.00,Default,,0000,0000,0000,,out] some ordering, so they're not equal
Dialogue: 0,0:14:47.00,0:14:51.00,Default,,0000,0000,0000,,[cuts out] later, it will return some positive value: 1, 10, 6 million.
Dialogue: 0,0:14:51.00,0:14:55.00,Default,,0000,0000,0000,,So if I do [cuts out] say I use ID num as my comparison.
Dialogue: 0,0:14:55.00,0:14:56.00,Default,,0000,0000,0000,,Based on [cuts
Dialogue: 0,0:14:56.00,0:14:58.00,Default,,0000,0000,0000,,out] are the same, if they are
Dialogue: 0,0:14:58.00,0:15:01.00,Default,,0000,0000,0000,,I can return zero. And if
Dialogue: 0,0:15:01.00,0:15:03.00,Default,,0000,0000,0000,,ID num of A
Dialogue: 0,0:15:03.00,0:15:07.00,Default,,0000,0000,0000,,is less than the ID num of B, I can
Dialogue: 0,0:15:07.00,0:15:08.00,Default,,0000,0000,0000,,return negative one, and then in
Dialogue: 0,0:15:08.00,0:15:11.00,Default,,0000,0000,0000,,the other case, I'll return one.
Dialogue: 0,0:15:11.00,0:15:14.00,Default,,0000,0000,0000,,So it will compare them on the basis [cuts out]
Dialogue: 0,0:15:14.00,0:15:16.00,Default,,0000,0000,0000,,figuring that the name field
Dialogue: 0,0:15:16.00,0:15:17.00,Default,,0000,0000,0000,,at that point is
Dialogue: 0,0:15:17.00,0:15:19.00,Default,,0000,0000,0000,,nothing new.
Dialogue: 0,0:15:19.00,0:15:24.00,Default,,0000,0000,0000,,And then the way I use that is over here when I'm constructing it is there is
Dialogue: 0,0:15:24.00,0:15:27.00,Default,,0000,0000,0000,,[cuts out] to the constructor, and so that's how I would pass [cuts out] add
Dialogue: 0,0:15:27.00,0:15:29.00,Default,,0000,0000,0000,,parens to the [cuts
Dialogue: 0,0:15:29.00,0:15:35.00,Default,,0000,0000,0000,,out] as I'm declaring it, and then I pass the name. Do I call it compare student or compare students? I can't remember. Compare student. Okay.
Dialogue: 0,0:15:35.00,0:15:38.00,Default,,0000,0000,0000,,And
Dialogue: 0,0:15:38.00,0:15:42.00,Default,,0000,0000,0000,,this then -so now there's nothing going on in the code -causes it to compile,
Dialogue: 0,0:15:42.00,0:15:45.00,Default,,0000,0000,0000,,and that if you were to put
Dialogue: 0,0:15:45.00,0:15:50.00,Default,,0000,0000,0000,,let's say a see out statement in your comparison function just for fun, you would find out as
Dialogue: 0,0:15:50.00,0:15:53.00,Default,,0000,0000,0000,,you were doing adds, and compares, and removes, and whatnot on this set
Dialogue: 0,0:15:53.00,0:15:58.00,Default,,0000,0000,0000,,that you would see that your call kept being made. It kept calling back to you as the
Dialogue: 0,0:15:58.00,0:16:01.00,Default,,0000,0000,0000,,client saying I need to compare these things. I need to compare these things to decide where to put something,
Dialogue: 0,0:16:01.00,0:16:03.00,Default,,0000,0000,0000,,whether it had something,
Dialogue: 0,0:16:03.00,0:16:04.00,Default,,0000,0000,0000,,and whatnot.
Dialogue: 0,0:16:04.00,0:16:08.00,Default,,0000,0000,0000,,And then based on your ordering, that would control for example how the iterator worked, that
Dialogue: 0,0:16:08.00,0:16:12.00,Default,,0000,0000,0000,,the smallest one according to your function would be the one first returned by your
Dialogue: 0,0:16:12.00,0:16:14.00,Default,,0000,0000,0000,,iterator, and it would move through larger
Dialogue: 0,0:16:14.00,0:16:17.00,Default,,0000,0000,0000,,or sort of later in the ordering ones until the end. So
Dialogue: 0,0:16:17.00,0:16:20.00,Default,,0000,0000,0000,,it's a very powerful mechanism
Dialogue: 0,0:16:20.00,0:16:24.00,Default,,0000,0000,0000,,that's at work here because it means that for
Dialogue: 0,0:16:24.00,0:16:28.00,Default,,0000,0000,0000,,anything you wanna put in a set, as long as you're willing to say how it is you compare
Dialogue: 0,0:16:28.00,0:16:28.00,Default,,0000,0000,0000,,it,
Dialogue: 0,0:16:28.00,0:16:33.00,Default,,0000,0000,0000,,then the set will take over and do the very efficient storing, and searching, and organizing
Dialogue: 0,0:16:33.00,0:16:34.00,Default,,0000,0000,0000,,of that.
Dialogue: 0,0:16:34.00,0:16:38.00,Default,,0000,0000,0000,,But you, the only piece you need to supply is this one little thing it can't figure
Dialogue: 0,0:16:38.00,0:16:42.00,Default,,0000,0000,0000,,out for itself, which is given your type of thing, how do you compare
Dialogue: 0,0:16:42.00,0:16:46.00,Default,,0000,0000,0000,,it. For the built in types string, and int, and double, and car,
Dialogue: 0,0:16:46.00,0:16:51.00,Default,,0000,0000,0000,,it does have a default comparison function, that one that was called operator compare. Let
Dialogue: 0,0:16:51.00,0:16:55.00,Default,,0000,0000,0000,,me go open it for you
Dialogue: 0,0:16:55.00,0:16:56.00,Default,,0000,0000,0000,,[inaudible] the 106.
Dialogue: 0,0:16:56.00,0:16:58.00,Default,,0000,0000,0000,,So there is a
Dialogue: 0,0:16:58.00,0:17:00.00,Default,,0000,0000,0000,,compare function dot H,
Dialogue: 0,0:17:00.00,0:17:02.00,Default,,0000,0000,0000,,and this is actually what
Dialogue: 0,0:17:02.00,0:17:05.00,Default,,0000,0000,0000,,the default version of it looks. It's actually written as a template itself
Dialogue: 0,0:17:05.00,0:17:07.00,Default,,0000,0000,0000,,that given two things it
Dialogue: 0,0:17:07.00,0:17:08.00,Default,,0000,0000,0000,,just
Dialogue: 0,0:17:08.00,0:17:11.00,Default,,0000,0000,0000,,turns around and asks the built in operators to help us out with that.
Dialogue: 0,0:17:11.00,0:17:15.00,Default,,0000,0000,0000,,And that is the name that's being used
Dialogue: 0,0:17:15.00,0:17:17.00,Default,,0000,0000,0000,,if I open the set
Dialogue: 0,0:17:17.00,0:17:20.00,Default,,0000,0000,0000,,and you look at its constructor call. I had said that I would come back and tell you about
Dialogue: 0,0:17:20.00,0:17:22.00,Default,,0000,0000,0000,,what this was
Dialogue: 0,0:17:22.00,0:17:25.00,Default,,0000,0000,0000,,that the argument going into the set constructor
Dialogue: 0,0:17:25.00,0:17:31.00,Default,,0000,0000,0000,,is one parameter whose name is CMP function that takes two elem type things -so here's the
Dialogue: 0,0:17:31.00,0:17:33.00,Default,,0000,0000,0000,,one in the example of the two argument prototype
Dialogue: 0,0:17:33.00,0:17:38.00,Default,,0000,0000,0000,,-returns an int, and then it uses a default assignment for that of operator compare, the one we just
Dialogue: 0,0:17:38.00,0:17:39.00,Default,,0000,0000,0000,,looked at,
Dialogue: 0,0:17:39.00,0:17:41.00,Default,,0000,0000,0000,,so that if you don't specify it, it goes
Dialogue: 0,0:17:41.00,0:17:46.00,Default,,0000,0000,0000,,through and generates the standard comparison function for the type,
Dialogue: 0,0:17:46.00,0:17:47.00,Default,,0000,0000,0000,,which
Dialogue: 0,0:17:47.00,0:17:49.00,Default,,0000,0000,0000,,for built-ins will work fine, but for
Dialogue: 0,0:17:49.00,0:17:53.00,Default,,0000,0000,0000,,user defined things is gonna create compiler errors.
Dialogue: 0,0:17:53.00,0:17:56.00,Default,,0000,0000,0000,,So you can also choose if you don't like the default ordering works.
Dialogue: 0,0:17:56.00,0:18:01.00,Default,,0000,0000,0000,,So for example, if you wanted to build a set of strings that was case insensitive
Dialogue: 0,0:18:01.00,0:18:04.00,Default,,0000,0000,0000,,-so the default string handling would be to use equals equals and less than, which actually
Dialogue: 0,0:18:04.00,0:18:08.00,Default,,0000,0000,0000,,does care about case. It doesn't think that capital [inaudible] is the same as lower case.
Dialogue: 0,0:18:08.00,0:18:10.00,Default,,0000,0000,0000,,If you wanted it to consider them the same,
Dialogue: 0,0:18:10.00,0:18:14.00,Default,,0000,0000,0000,,you could supply your own. A compare case insensitively function took two strings,
Dialogue: 0,0:18:14.00,0:18:16.00,Default,,0000,0000,0000,,converted their case, and then compared them.
Dialogue: 0,0:18:16.00,0:18:19.00,Default,,0000,0000,0000,,And then when you establish a set of strings, instead of letting the default argument take over,
Dialogue: 0,0:18:19.00,0:18:24.00,Default,,0000,0000,0000,,go ahead and use your case insensitive compare, and then now you have a set of strings
Dialogue: 0,0:18:24.00,0:18:26.00,Default,,0000,0000,0000,,that operates case insensitively.
Dialogue: 0,0:18:26.00,0:18:28.00,Default,,0000,0000,0000,,So you can change
Dialogue: 0,0:18:28.00,0:18:31.00,Default,,0000,0000,0000,,the ordering, adapt the ordering, whatever you like for the primitives, as well as supply the necessary
Dialogue: 0,0:18:31.00,0:18:32.00,Default,,0000,0000,0000,,one for the
Dialogue: 0,0:18:32.00,0:18:34.00,Default,,0000,0000,0000,,things the built-ins
Dialogue: 0,0:18:34.00,0:18:35.00,Default,,0000,0000,0000,,don't have
Dialogue: 0,0:18:35.00,0:18:40.00,Default,,0000,0000,0000,,properties for. So then that's that piece of code right
Dialogue: 0,0:18:40.00,0:18:41.00,Default,,0000,0000,0000,,there. All right. So
Dialogue: 0,0:18:41.00,0:18:44.00,Default,,0000,0000,0000,,does that make sense?
Dialogue: 0,0:18:44.00,0:18:45.00,Default,,0000,0000,0000,,Well, now you know
Dialogue: 0,0:18:45.00,0:18:49.00,Default,,0000,0000,0000,,kind of the whole range of things that are available in the class library. All
Dialogue: 0,0:18:49.00,0:18:53.00,Default,,0000,0000,0000,,right, so we saw the four sequential containers, the vector, stack, queue,
Dialogue: 0,0:18:53.00,0:18:55.00,Default,,0000,0000,0000,,and the grid that you kinda indexed ordering,
Dialogue: 0,0:18:55.00,0:18:58.00,Default,,0000,0000,0000,,and kinda allowed you to throw things in and get them back out.
Dialogue: 0,0:18:58.00,0:19:02.00,Default,,0000,0000,0000,,We went through the map, which is the sort of fancy heavy lifter that does that key value
Dialogue: 0,0:19:02.00,0:19:04.00,Default,,0000,0000,0000,,lookup, and then we've seen the set, which does kind of
Dialogue: 0,0:19:04.00,0:19:06.00,Default,,0000,0000,0000,,aggregate collection management,
Dialogue: 0,0:19:06.00,0:19:10.00,Default,,0000,0000,0000,,and very efficient operations for kind of searching, retrieving, ordering,
Dialogue: 0,0:19:10.00,0:19:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:19:12.00,0:19:13.00,Default,,0000,0000,0000,,joining with other kind of sets, and stuff
Dialogue: 0,0:19:13.00,0:19:16.00,Default,,0000,0000,0000,,that also has a lot of high utility. I wanna do
Dialogue: 0,0:19:16.00,0:19:19.00,Default,,0000,0000,0000,,one quick little program with you before I start recursion
Dialogue: 0,0:19:19.00,0:19:21.00,Default,,0000,0000,0000,,just because I think it's kinda cool
Dialogue: 0,0:19:21.00,0:19:23.00,Default,,0000,0000,0000,,is to talk a little about this idea of like once
Dialogue: 0,0:19:23.00,0:19:26.00,Default,,0000,0000,0000,,you have these ADTs, you can solve a lot of cool problems, and that's certainly what this
Dialogue: 0,0:19:26.00,0:19:29.00,Default,,0000,0000,0000,,week's assignment is about. It's like well here are these tasks that
Dialogue: 0,0:19:29.00,0:19:31.00,Default,,0000,0000,0000,,if you didn't have
Dialogue: 0,0:19:31.00,0:19:34.00,Default,,0000,0000,0000,,-So ADTs, just a reminder -I say this word as though everybody knows exactly what it means
Dialogue: 0,0:19:34.00,0:19:37.00,Default,,0000,0000,0000,,-is just the idea of an abstract data type.
Dialogue: 0,0:19:37.00,0:19:39.00,Default,,0000,0000,0000,,So an abstract data type is a data type
Dialogue: 0,0:19:39.00,0:19:42.00,Default,,0000,0000,0000,,that you think of in terms of what it provides as an abstraction.
Dialogue: 0,0:19:42.00,0:19:44.00,Default,,0000,0000,0000,,So a queue is this FIFO line,
Dialogue: 0,0:19:44.00,0:19:47.00,Default,,0000,0000,0000,,and how it works internally, what it's implemented as, we're not worried
Dialogue: 0,0:19:47.00,0:19:51.00,Default,,0000,0000,0000,,about it at all. We're only worried about the abstraction of enqueue and dequeue, and it coming first
Dialogue: 0,0:19:51.00,0:19:53.00,Default,,0000,0000,0000,,in first out. So we talk
Dialogue: 0,0:19:53.00,0:19:56.00,Default,,0000,0000,0000,,about ADTs, we say once we have a queue, a stack, or a vector,
Dialogue: 0,0:19:56.00,0:19:58.00,Default,,0000,0000,0000,,we know what those things do,
Dialogue: 0,0:19:58.00,0:20:00.00,Default,,0000,0000,0000,,what a mathematical set is about.
Dialogue: 0,0:20:00.00,0:20:03.00,Default,,0000,0000,0000,,We build on top of that. We write code
Dialogue: 0,0:20:03.00,0:20:06.00,Default,,0000,0000,0000,,that leverages those ADTs to do cool things
Dialogue: 0,0:20:06.00,0:20:10.00,Default,,0000,0000,0000,,without having to also manage the low level details of where the memory came from for these things,
Dialogue: 0,0:20:10.00,0:20:13.00,Default,,0000,0000,0000,,how they grow, how they search, how
Dialogue: 0,0:20:13.00,0:20:15.00,Default,,0000,0000,0000,,they store and organize the data.
Dialogue: 0,0:20:15.00,0:20:17.00,Default,,0000,0000,0000,,You just get to do real cool things.
Dialogue: 0,0:20:17.00,0:20:21.00,Default,,0000,0000,0000,,So you probably got a little taste of that at the end of 106A when you get to use the array list and the
Dialogue: 0,0:20:21.00,0:20:24.00,Default,,0000,0000,0000,,hashmap to do things. This set kinda just expands out
Dialogue: 0,0:20:24.00,0:20:26.00,Default,,0000,0000,0000,,to fill out some other niches
Dialogue: 0,0:20:26.00,0:20:28.00,Default,,0000,0000,0000,,where you can do a lot of really cool things
Dialogue: 0,0:20:28.00,0:20:30.00,Default,,0000,0000,0000,,because you have these things around to build on.
Dialogue: 0,0:20:30.00,0:20:34.00,Default,,0000,0000,0000,,So one of the things that happens a lot is you tend to do layered things, and you'll see a little bit of this
Dialogue: 0,0:20:34.00,0:20:38.00,Default,,0000,0000,0000,,in the assignment you're doing this week where it's not just a set of something, it's a set of a map
Dialogue: 0,0:20:38.00,0:20:39.00,Default,,0000,0000,0000,,of something, or
Dialogue: 0,0:20:39.00,0:20:43.00,Default,,0000,0000,0000,,a vector of queues, a map of set. So I gave you a couple of examples here of
Dialogue: 0,0:20:43.00,0:20:44.00,Default,,0000,0000,0000,,the things
Dialogue: 0,0:20:44.00,0:20:48.00,Default,,0000,0000,0000,,that might be useful. Like if you think of what a smoothie is, it's a set of things
Dialogue: 0,0:20:48.00,0:20:52.00,Default,,0000,0000,0000,,mixed together, some yogurt, and some different fruits, some wheatgrass, whatever it is you have in
Dialogue: 0,0:20:52.00,0:20:53.00,Default,,0000,0000,0000,,it.
Dialogue: 0,0:20:53.00,0:20:57.00,Default,,0000,0000,0000,,And that the menu for a smoothie shop is really just a bunch of those sets, so each set
Dialogue: 0,0:20:57.00,0:21:00.00,Default,,0000,0000,0000,,of ingredients is a particular smoothie they have, and then
Dialogue: 0,0:21:00.00,0:21:04.00,Default,,0000,0000,0000,,the set of all those sets is the menu that they post up on the board you can come
Dialogue: 0,0:21:04.00,0:21:06.00,Default,,0000,0000,0000,,in and order.
Dialogue: 0,0:21:06.00,0:21:07.00,Default,,0000,0000,0000,,The
Dialogue: 0,0:21:07.00,0:21:09.00,Default,,0000,0000,0000,,compiler tends to use a map
Dialogue: 0,0:21:09.00,0:21:13.00,Default,,0000,0000,0000,,to keep track of all the variables that are in scope. As you declare variables, it
Dialogue: 0,0:21:13.00,0:21:17.00,Default,,0000,0000,0000,,adds them to the map so that when you later use that name, it knows where to find it.
Dialogue: 0,0:21:17.00,0:21:19.00,Default,,0000,0000,0000,,Well, it also has to manage though
Dialogue: 0,0:21:19.00,0:21:21.00,Default,,0000,0000,0000,,not just one map,
Dialogue: 0,0:21:21.00,0:21:25.00,Default,,0000,0000,0000,,but the idea is as you enter and exit scopes, there is this
Dialogue: 0,0:21:25.00,0:21:27.00,Default,,0000,0000,0000,,layering of open scopes.
Dialogue: 0,0:21:27.00,0:21:32.00,Default,,0000,0000,0000,,So you have some open scope here. You go into a for loop where you open another scope. You add some
Dialogue: 0,0:21:32.00,0:21:33.00,Default,,0000,0000,0000,,new variables
Dialogue: 0,0:21:33.00,0:21:37.00,Default,,0000,0000,0000,,that when you look it actually shadows then at the nearest definition, so if you had two variables
Dialogue: 0,0:21:37.00,0:21:41.00,Default,,0000,0000,0000,,of the same, it needs to look at the one that's closest.
Dialogue: 0,0:21:41.00,0:21:44.00,Default,,0000,0000,0000,,And then when you exit that scope, it needs those variables to go away and
Dialogue: 0,0:21:44.00,0:21:48.00,Default,,0000,0000,0000,,no longer be accessible. So one model for that could be very much a stack of
Dialogue: 0,0:21:48.00,0:21:51.00,Default,,0000,0000,0000,,maps where each of those maps represents the scope
Dialogue: 0,0:21:51.00,0:21:52.00,Default,,0000,0000,0000,,that's active,
Dialogue: 0,0:21:52.00,0:21:56.00,Default,,0000,0000,0000,,a set of variable names, and maybe their types and information is stored in that map. And then
Dialogue: 0,0:21:56.00,0:21:58.00,Default,,0000,0000,0000,,you stack them up. As you
Dialogue: 0,0:21:58.00,0:22:01.00,Default,,0000,0000,0000,,open a scope, you push on a new empty map.
Dialogue: 0,0:22:01.00,0:22:03.00,Default,,0000,0000,0000,,You put things into it, and then
Dialogue: 0,0:22:03.00,0:22:06.00,Default,,0000,0000,0000,,maybe you enter another scope. You push on another new empty map. You stick things into it, but as you
Dialogue: 0,0:22:06.00,0:22:11.00,Default,,0000,0000,0000,,exit and hit those closing braces, you pop those things from the stack to get to
Dialogue: 0,0:22:11.00,0:22:13.00,Default,,0000,0000,0000,,this previous
Dialogue: 0,0:22:13.00,0:22:16.00,Default,,0000,0000,0000,,environment you were in. So let me do a
Dialogue: 0,0:22:16.00,0:22:19.00,Default,,0000,0000,0000,,little program with you. I just have
Dialogue: 0,0:22:19.00,0:22:22.00,Default,,0000,0000,0000,,this idea of how this would work, and we'll see if
Dialogue: 0,0:22:22.00,0:22:26.00,Default,,0000,0000,0000,,I can code something up. So I have -let's go
Dialogue: 0,0:22:26.00,0:22:28.00,Default,,0000,0000,0000,,back over
Dialogue: 0,0:22:28.00,0:22:32.00,Default,,0000,0000,0000,,here. I'm going to -this is the piece of code that just reads
Dialogue: 0,0:22:32.00,0:22:34.00,Default,,0000,0000,0000,,words, so that's a
Dialogue: 0,0:22:34.00,0:22:36.00,Default,,0000,0000,0000,,fine piece of code to have here.
Dialogue: 0,0:22:36.00,0:22:38.00,Default,,0000,0000,0000,,I have a file here -let
Dialogue: 0,0:22:38.00,0:22:39.00,Default,,0000,0000,0000,,me open
Dialogue: 0,0:22:39.00,0:22:43.00,Default,,0000,0000,0000,,it up for you -that just contains the contents of the Official Scrabble Players' Dictionary,
Dialogue: 0,0:22:43.00,0:22:45.00,Default,,0000,0000,0000,,Edition 2.
Dialogue: 0,0:22:45.00,0:22:47.00,Default,,0000,0000,0000,,It's got a lot of words it.
Dialogue: 0,0:22:47.00,0:22:48.00,Default,,0000,0000,0000,,It's pretty long.
Dialogue: 0,0:22:48.00,0:22:49.00,Default,,0000,0000,0000,,It's still loading.
Dialogue: 0,0:22:49.00,0:22:53.00,Default,,0000,0000,0000,,Let's go back and do something else while it's loading.
Dialogue: 0,0:22:53.00,0:22:54.00,Default,,0000,0000,0000,,It happened to have
Dialogue: 0,0:22:54.00,0:22:55.00,Default,,0000,0000,0000,,
Dialogue: 0,0:22:55.00,0:22:58.00,Default,,0000,0000,0000,,about 120,000 words I think is what it would be right now.
Dialogue: 0,0:22:58.00,0:22:59.00,Default,,0000,0000,0000,,So it's busy loading,
Dialogue: 0,0:22:59.00,0:23:01.00,Default,,0000,0000,0000,,and I have this question for you.
Dialogue: 0,0:23:01.00,0:23:04.00,Default,,0000,0000,0000,,There are certain words that are anagrams of each other.
Dialogue: 0,0:23:04.00,0:23:06.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:06.00,0:23:08.00,Default,,0000,0000,0000,,The word
Dialogue: 0,0:23:08.00,0:23:10.00,Default,,0000,0000,0000,,cheap can be anagrammed into the word peach,
Dialogue: 0,0:23:10.00,0:23:11.00,Default,,0000,0000,0000,,things like that.
Dialogue: 0,0:23:11.00,0:23:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:12.00,0:23:13.00,Default,,0000,0000,0000,,And so I
Dialogue: 0,0:23:13.00,0:23:15.00,Default,,0000,0000,0000,,am curious for the
Dialogue: 0,0:23:15.00,0:23:16.00,Default,,0000,0000,0000,,Official Scrabble Players' Dictionary
Dialogue: 0,0:23:16.00,0:23:20.00,Default,,0000,0000,0000,,what -so if you imagine that some words can be anagrammed a couple times, five
Dialogue: 0,0:23:20.00,0:23:24.00,Default,,0000,0000,0000,,or six different words just on how you can rearrange the letters. I'm curious to know what the largest anagram
Dialogue: 0,0:23:24.00,0:23:28.00,Default,,0000,0000,0000,,cluster is in the Official Scrabble Players' Dictionary. So I'd like to know across
Dialogue: 0,0:23:28.00,0:23:30.00,Default,,0000,0000,0000,,all 127,000 words
Dialogue: 0,0:23:30.00,0:23:34.00,Default,,0000,0000,0000,,that they form little clusters, and I'd like to find out what's the biggest of
Dialogue: 0,0:23:34.00,0:23:39.00,Default,,0000,0000,0000,,those clusters.
Dialogue: 0,0:23:39.00,0:23:41.00,Default,,0000,0000,0000,,Okay. That's my goal. So
Dialogue: 0,0:23:41.00,0:23:45.00,Default,,0000,0000,0000,,here's what I've got going. I've got something that's gonna read them one by one.
Dialogue: 0,0:23:45.00,0:23:48.00,Default,,0000,0000,0000,,So let's brainstorm for a second.
Dialogue: 0,0:23:48.00,0:23:49.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:49.00,0:23:51.00,Default,,0000,0000,0000,,I want a way to take a particular word and kinda stick
Dialogue: 0,0:23:51.00,0:23:55.00,Default,,0000,0000,0000,,it with its other anagram cluster friends.
Dialogue: 0,0:23:55.00,0:23:57.00,Default,,0000,0000,0000,,What's a way I might do that?
Dialogue: 0,0:23:57.00,0:24:03.00,Default,,0000,0000,0000,,Help me design my data structure.
Dialogue: 0,0:24:03.00,0:24:06.00,Default,,0000,0000,0000,,Help me out. [Inaudible]. I've
Dialogue: 0,0:24:06.00,0:24:08.00,Default,,0000,0000,0000,,got the word peach.
Dialogue: 0,0:24:08.00,0:24:10.00,Default,,0000,0000,0000,,Where should I stick it so I can ? You could treat each string as like a set of
Dialogue: 0,0:24:10.00,0:24:13.00,Default,,0000,0000,0000,,? So I have this
Dialogue: 0,0:24:13.00,0:24:17.00,Default,,0000,0000,0000,,string,
Dialogue: 0,0:24:17.00,0:24:21.00,Default,,0000,0000,0000,,which represents the letters. I've
Dialogue: 0,0:24:21.00,0:24:22.00,Default,,0000,0000,0000,,got the word peach. I wanna be able to stick peach with cheap,
Dialogue: 0,0:24:22.00,0:24:26.00,Default,,0000,0000,0000,,so where should I stick peach in such a way that I could find it. And you've got this idea that
Dialogue: 0,0:24:26.00,0:24:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:24:27.00,0:24:29.00,Default,,0000,0000,0000,,the letters there are a set.
Dialogue: 0,0:24:29.00,0:24:32.00,Default,,0000,0000,0000,,They're not quite a set, though. Be careful because the word banana has a
Dialogue: 0,0:24:32.00,0:24:36.00,Default,,0000,0000,0000,,couple As and a couple Ns, and so it's not that I'd really want it to come down to be
Dialogue: 0,0:24:36.00,0:24:39.00,Default,,0000,0000,0000,,the set BAN. I wouldn't wanna coalesce the duplicates on that, so I really do wanna preserve all the letters that
Dialogue: 0,0:24:39.00,0:24:43.00,Default,,0000,0000,0000,,are in there,
Dialogue: 0,0:24:43.00,0:24:46.00,Default,,0000,0000,0000,,but your idea's getting us somewhere. It's like there is this idea of kind of like for any
Dialogue: 0,0:24:46.00,0:24:49.00,Default,,0000,0000,0000,,particular word there's the
Dialogue: 0,0:24:49.00,0:24:53.00,Default,,0000,0000,0000,,collection of letters that it is formed from.
Dialogue: 0,0:24:53.00,0:24:56.00,Default,,0000,0000,0000,,And somehow if I could use that as an identifier
Dialogue: 0,0:24:56.00,0:24:58.00,Default,,0000,0000,0000,,in a way that was reliable
Dialogue: 0,0:24:58.00,0:25:01.00,Default,,0000,0000,0000,,-anybody
Dialogue: 0,0:25:01.00,0:25:02.00,Default,,0000,0000,0000,,got any
Dialogue: 0,0:25:02.00,0:25:03.00,Default,,0000,0000,0000,,ideas
Dialogue: 0,0:25:03.00,0:25:08.00,Default,,0000,0000,0000,,about what to do with that? If you did that a vector, each letter and then the frequency of each letter in the word? So I could certainly do that. I could build kind of a vector that
Dialogue: 0,0:25:08.00,0:25:12.00,Default,,0000,0000,0000,,had kinda frequencies, that had this little struct that maybe it was number of times it occurs.
Dialogue: 0,0:25:12.00,0:25:15.00,Default,,0000,0000,0000,,Then I could try to build something on the basis of that vector that was like
Dialogue: 0,0:25:15.00,0:25:18.00,Default,,0000,0000,0000,,here is -do these two vectors
Dialogue: 0,0:25:18.00,0:25:22.00,Default,,0000,0000,0000,,match? Does banana match apple? And you'd say well no. It turns out they don't
Dialogue: 0,0:25:22.00,0:25:23.00,Default,,0000,0000,0000,,have the same letters. I'm trying to
Dialogue: 0,0:25:23.00,0:25:27.00,Default,,0000,0000,0000,,think of a really easy way to represent that. Your idea's good,
Dialogue: 0,0:25:27.00,0:25:31.00,Default,,0000,0000,0000,,but I'm thinking really lazy. So somebody help me who's lazy. Could you
Dialogue: 0,0:25:31.00,0:25:36.00,Default,,0000,0000,0000,,have a map where the key is all the letters in alphabetical order and the value is a
Dialogue: 0,0:25:36.00,0:25:41.00,Default,,0000,0000,0000,,vector of all the ? Yeah. That is a great idea. You're taking his idea, and you're making it easier.
Dialogue: 0,0:25:41.00,0:25:43.00,Default,,0000,0000,0000,,You're capitalizing on lazy, which is yeah
Dialogue: 0,0:25:43.00,0:25:45.00,Default,,0000,0000,0000,,-I wanna keep track of all the letters that are in the word,
Dialogue: 0,0:25:45.00,0:25:48.00,Default,,0000,0000,0000,,but I wanna do it in a way that makes it really easy for
Dialogue: 0,0:25:48.00,0:25:52.00,Default,,0000,0000,0000,,example to know whether two have the same -we'll call it the signature. The signature of
Dialogue: 0,0:25:52.00,0:25:54.00,Default,,0000,0000,0000,,the word is the letter frequency across it.
Dialogue: 0,0:25:54.00,0:25:57.00,Default,,0000,0000,0000,,If I could come up with a way to represent the signature that was really to compare two
Dialogue: 0,0:25:57.00,0:26:01.00,Default,,0000,0000,0000,,signatures quickly to see if they're the same, then I will have less work to do. And so your idea is a great
Dialogue: 0,0:26:01.00,0:26:04.00,Default,,0000,0000,0000,,one. We take the letters and we alphabetize them.
Dialogue: 0,0:26:04.00,0:26:08.00,Default,,0000,0000,0000,,So cheap and peach both turn into the same ACEHP. It's
Dialogue: 0,0:26:08.00,0:26:13.00,Default,,0000,0000,0000,,a nonsense thing, but it's a signature. It's unique for any anagram, and
Dialogue: 0,0:26:13.00,0:26:14.00,Default,,0000,0000,0000,,if I use a map
Dialogue: 0,0:26:14.00,0:26:15.00,Default,,0000,0000,0000,,where that's the key,
Dialogue: 0,0:26:15.00,0:26:17.00,Default,,0000,0000,0000,,then I can associate with every word
Dialogue: 0,0:26:17.00,0:26:20.00,Default,,0000,0000,0000,,that had that same signature.
Dialogue: 0,0:26:20.00,0:26:23.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:26:23.00,0:26:27.00,Default,,0000,0000,0000,,let's start building that. So let me write
Dialogue: 0,0:26:27.00,0:26:29.00,Default,,0000,0000,0000,,-I wanna call this the signature.
Dialogue: 0,0:26:29.00,0:26:31.00,Default,,0000,0000,0000,,Given a string,
Dialogue: 0,0:26:31.00,0:26:33.00,Default,,0000,0000,0000,,it's going to
Dialogue: 0,0:26:33.00,0:26:34.00,Default,,0000,0000,0000,,alphabetize it.
Dialogue: 0,0:26:34.00,0:26:37.00,Default,,0000,0000,0000,,I'm going to write the
Dialogue: 0,0:26:37.00,0:26:40.00,Default,,0000,0000,0000,,dumbest version of this ever,
Dialogue: 0,0:26:40.00,0:26:47.00,Default,,0000,0000,0000,,but I'm just gonna use a simple sorting routine on this. So
Dialogue: 0,0:26:47.00,0:26:51.00,Default,,0000,0000,0000,,smallest is gonna small index -we'll call it min index. That's a better name for it.
Dialogue: 0,0:26:51.00,0:26:53.00,Default,,0000,0000,0000,,Min index equals I,
Dialogue: 0,0:26:53.00,0:26:57.00,Default,,0000,0000,0000,,and then I'm gonna look through the string, and I'm gonna find the smallest letter that's
Dialogue: 0,0:26:57.00,0:26:58.00,Default,,0000,0000,0000,,there and
Dialogue: 0,0:26:58.00,0:27:03.00,Default,,0000,0000,0000,,move it to the front. That's basically gonna be my strategy. I've
Dialogue: 0,0:27:03.00,0:27:05.00,Default,,0000,0000,0000,,got the wrong place to start, though. I'm gonna
Dialogue: 0,0:27:05.00,0:27:11.00,Default,,0000,0000,0000,,look from I to the one. So if
Dialogue: 0,0:27:11.00,0:27:13.00,Default,,0000,0000,0000,,S sub J
Dialogue: 0,0:27:13.00,0:27:15.00,Default,,0000,0000,0000,,is less than S sub min index,
Dialogue: 0,0:27:15.00,0:27:20.00,Default,,0000,0000,0000,,so it is a smaller letter, then the min index gets to be J.
Dialogue: 0,0:27:20.00,0:27:23.00,Default,,0000,0000,0000,,So far, what I've done is I've run this loop that kind
Dialogue: 0,0:27:23.00,0:27:27.00,Default,,0000,0000,0000,,of starts in this case on the very first iteration and says the first character in Slot 0, that
Dialogue: 0,0:27:27.00,0:27:31.00,Default,,0000,0000,0000,,must be the min. And then it looks from there to the end. Is there anything smaller? Whenever it
Dialogue: 0,0:27:31.00,0:27:34.00,Default,,0000,0000,0000,,find anything smaller, it updates the min index, so when it's done
Dialogue: 0,0:27:34.00,0:27:39.00,Default,,0000,0000,0000,,after that second loop has fully
Dialogue: 0,0:27:39.00,0:27:40.00,Default,,0000,0000,0000,,operated,
Dialogue: 0,0:27:40.00,0:27:44.00,Default,,0000,0000,0000,,then min index will point to the smallest alphabetically
Dialogue: 0,0:27:44.00,0:27:45.00,Default,,0000,0000,0000,,character in the
Dialogue: 0,0:27:45.00,0:27:49.00,Default,,0000,0000,0000,,string that we have. Then I'm gonna swap it to the front.
Dialogue: 0,0:27:49.00,0:27:52.00,Default,,0000,0000,0000,,So S sub I
Dialogue: 0,0:27:52.00,0:27:55.00,Default,,0000,0000,0000,,with S sub min index, and
Dialogue: 0,0:27:55.00,0:28:08.00,Default,,0000,0000,0000,,I'll write a swap because swap is pretty easy to write.
Dialogue: 0,0:28:08.00,0:28:10.00,Default,,0000,0000,0000,,See about how we do this, okay.
Dialogue: 0,0:28:10.00,0:28:12.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:28:12.00,0:28:13.00,Default,,0000,0000,0000,,if I
Dialogue: 0,0:28:13.00,0:28:16.00,Default,,0000,0000,0000,,-I like how this works, and then let me stop and say
Dialogue: 0,0:28:16.00,0:28:17.00,Default,,0000,0000,0000,,right here, now
Dialogue: 0,0:28:17.00,0:28:19.00,Default,,0000,0000,0000,,is a good time to test this thing.
Dialogue: 0,0:28:19.00,0:28:23.00,Default,,0000,0000,0000,,I just wrote signature. It probably works, but it potentially
Dialogue: 0,0:28:23.00,0:28:24.00,Default,,0000,0000,0000,,could not.
Dialogue: 0,0:28:24.00,0:28:27.00,Default,,0000,0000,0000,,And I'm just gonna show you a little bit of how I write code. This is good to know. As I
Dialogue: 0,0:28:27.00,0:28:28.00,Default,,0000,0000,0000,,say,
Dialogue: 0,0:28:28.00,0:28:29.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:29.00,0:28:32.00,Default,,0000,0000,0000,,I put some code in here that I plan on throwing away.
Dialogue: 0,0:28:32.00,0:28:35.00,Default,,0000,0000,0000,,Enter word
Dialogue: 0,0:28:35.00,0:28:42.00,Default,,0000,0000,0000,,-and then I throw it through my function. I think I called it
Dialogue: 0,0:28:42.00,0:28:44.00,Default,,0000,0000,0000,,signature, didn't I?
Dialogue: 0,0:28:44.00,0:28:47.00,Default,,0000,0000,0000,,Signature S
Dialogue: 0,0:28:47.00,0:28:51.00,Default,,0000,0000,0000,,-so the idea being if it doesn't work, I wanna find out sooner rather than
Dialogue: 0,0:28:51.00,0:28:52.00,Default,,0000,0000,0000,,later. It
Dialogue: 0,0:28:52.00,0:28:55.00,Default,,0000,0000,0000,,doesn't like my use of get line. Is that because it's not
Dialogue: 0,0:28:55.00,0:28:57.00,Default,,0000,0000,0000,,included?
Dialogue: 0,0:28:57.00,0:29:00.00,Default,,0000,0000,0000,,Yes, it's not. So let's go get the right header files. This is half the
Dialogue: 0,0:29:00.00,0:29:03.00,Default,,0000,0000,0000,,battle sometimes is figuring out what
Dialogue: 0,0:29:03.00,0:29:04.00,Default,,0000,0000,0000,,headers
Dialogue: 0,0:29:04.00,0:29:05.00,Default,,0000,0000,0000,,are needed to make
Dialogue: 0,0:29:05.00,0:29:10.00,Default,,0000,0000,0000,,your compiler happy. So now it's up
Dialogue: 0,0:29:10.00,0:29:14.00,Default,,0000,0000,0000,,here at enter word, and I say what does cheap come out as?
Dialogue: 0,0:29:14.00,0:29:16.00,Default,,0000,0000,0000,,It goes into the debugger. That's good.
Dialogue: 0,0:29:16.00,0:29:17.00,Default,,0000,0000,0000,,So it wasn't right.
Dialogue: 0,0:29:17.00,0:29:19.00,Default,,0000,0000,0000,,Now we're gonna get to find out
Dialogue: 0,0:29:19.00,0:29:21.00,Default,,0000,0000,0000,,what does it not like about that.
Dialogue: 0,0:29:21.00,0:29:27.00,Default,,0000,0000,0000,,It says
Dialogue: 0,0:29:27.00,0:29:29.00,Default,,0000,0000,0000,,-did we forget to return something?
Dialogue: 0,0:29:29.00,0:29:30.00,Default,,0000,0000,0000,,Let's go look at our code.
Dialogue: 0,0:29:30.00,0:29:34.00,Default,,0000,0000,0000,,So it's complaining about -oh yeah, I can see where we're gonna get in trouble here. It's
Dialogue: 0,0:29:34.00,0:29:38.00,Default,,0000,0000,0000,,complaining that the return -it was saying that I'm trying to print something and it looks like garbage, that
Dialogue: 0,0:29:38.00,0:29:40.00,Default,,0000,0000,0000,,what I'm trying to print didn't make sense at all.
Dialogue: 0,0:29:40.00,0:29:47.00,Default,,0000,0000,0000,,I could say well that's funny. Let's go look at signature. [Inaudible] pass the [inaudible].
Dialogue: 0,0:29:47.00,0:29:51.00,Default,,0000,0000,0000,,That's probably a good idea. We ought to fix that while we're there.
Dialogue: 0,0:29:51.00,0:29:54.00,Default,,0000,0000,0000,,Let me leave that bug in for a minute because I'm gonna fix my first bug, and then I'll come back
Dialogue: 0,0:29:54.00,0:29:55.00,Default,,0000,0000,0000,,to that one.
Dialogue: 0,0:29:55.00,0:29:57.00,Default,,0000,0000,0000,,So it turns out what it's really complaining about though is it has to do with
Dialogue: 0,0:29:57.00,0:30:01.00,Default,,0000,0000,0000,,-I said well what does signature return. Somehow, what's being returned by signature is being interpreted
Dialogue: 0,0:30:01.00,0:30:04.00,Default,,0000,0000,0000,,as total crap when it got back to main, and there's a very good reason for that
Dialogue: 0,0:30:04.00,0:30:06.00,Default,,0000,0000,0000,,because I never returned
Dialogue: 0,0:30:06.00,0:30:09.00,Default,,0000,0000,0000,,anything. So maybe if I had been less cavalier about the fact that it was giving me a warning
Dialogue: 0,0:30:09.00,0:30:11.00,Default,,0000,0000,0000,,over here that said
Dialogue: 0,0:30:11.00,0:30:14.00,Default,,0000,0000,0000,,control reaches the end of non-void function, but I was being lazy and I didn't look
Dialogue: 0,0:30:14.00,0:30:17.00,Default,,0000,0000,0000,,-was that I
Dialogue: 0,0:30:17.00,0:30:18.00,Default,,0000,0000,0000,,didn't pay attention to the fact.
Dialogue: 0,0:30:18.00,0:30:20.00,Default,,0000,0000,0000,,So let's leave my other bug in that you've already pointed out
Dialogue: 0,0:30:20.00,0:30:24.00,Default,,0000,0000,0000,,because this is exactly what it's like when you're doing it. You enter words and you say cheap,
Dialogue: 0,0:30:24.00,0:30:25.00,Default,,0000,0000,0000,,and it says cheap, and you're like
Dialogue: 0,0:30:25.00,0:30:28.00,Default,,0000,0000,0000,,no.
Dialogue: 0,0:30:28.00,0:30:32.00,Default,,0000,0000,0000,,And then you're like about how about an. Hey look, that's in alphabetical order. And then you spend all your time thinking about words
Dialogue: 0,0:30:32.00,0:30:37.00,Default,,0000,0000,0000,,for a while. Well, tux. That's in alphabetical order. It seems to work. You could do that for a while, but
Dialogue: 0,0:30:37.00,0:30:39.00,Default,,0000,0000,0000,,then
Dialogue: 0,0:30:39.00,0:30:41.00,Default,,0000,0000,0000,,you're like this whole cheap,
Dialogue: 0,0:30:41.00,0:30:42.00,Default,,0000,0000,0000,,not good.
Dialogue: 0,0:30:42.00,0:30:46.00,Default,,0000,0000,0000,,Okay, so I come back here and my friend who's already one step ahead of me has pointed out that my swap
Dialogue: 0,0:30:46.00,0:30:50.00,Default,,0000,0000,0000,,is missing the all important pass by reference
Dialogue: 0,0:30:50.00,0:30:53.00,Default,,0000,0000,0000,,that as it is it what swapping the copies that got passed to
Dialogue: 0,0:30:53.00,0:30:56.00,Default,,0000,0000,0000,,the function, but of course nothing was happening back here in signature land.
Dialogue: 0,0:30:56.00,0:30:57.00,Default,,0000,0000,0000,,So if I fix that, and
Dialogue: 0,0:30:57.00,0:30:59.00,Default,,0000,0000,0000,,I come back in here,
Dialogue: 0,0:30:59.00,0:31:01.00,Default,,0000,0000,0000,,I'm gonna feel better about this. Oh,
Dialogue: 0,0:31:01.00,0:31:04.00,Default,,0000,0000,0000,,my gosh. And even tux still works.
Dialogue: 0,0:31:04.00,0:31:08.00,Default,,0000,0000,0000,,And if I say banana, I should get a bunch of As, a bunch of B and an N, so there's various cases to test out if you have
Dialogue: 0,0:31:08.00,0:31:09.00,Default,,0000,0000,0000,,multiple letters, and if
Dialogue: 0,0:31:09.00,0:31:12.00,Default,,0000,0000,0000,,you have letters that are the same letters like
Dialogue: 0,0:31:12.00,0:31:16.00,Default,,0000,0000,0000,,apple so that it doesn't lose your duplicates, and it seems to come out right.
Dialogue: 0,0:31:16.00,0:31:17.00,Default,,0000,0000,0000,,So given this,
Dialogue: 0,0:31:17.00,0:31:19.00,Default,,0000,0000,0000,,the word peach
Dialogue: 0,0:31:19.00,0:31:22.00,Default,,0000,0000,0000,,should come down to the same signature as cheap, and so that seems to indicate we're on
Dialogue: 0,0:31:22.00,0:31:24.00,Default,,0000,0000,0000,,the path
Dialogue: 0,0:31:24.00,0:31:24.00,Default,,0000,0000,0000,,toward
Dialogue: 0,0:31:24.00,0:31:26.00,Default,,0000,0000,0000,,building the thing we wanted to build. So I
Dialogue: 0,0:31:26.00,0:31:28.00,Default,,0000,0000,0000,,have this read file thing that I
Dialogue: 0,0:31:28.00,0:31:29.00,Default,,0000,0000,0000,,have left over from last time that
Dialogue: 0,0:31:29.00,0:31:31.00,Default,,0000,0000,0000,,reads each word,
Dialogue: 0,0:31:31.00,0:31:35.00,Default,,0000,0000,0000,,and I wanna change my vector
Dialogue: 0,0:31:35.00,0:31:37.00,Default,,0000,0000,0000,,into a map of
Dialogue: 0,0:31:37.00,0:31:40.00,Default,,0000,0000,0000,,set of string.
Dialogue: 0,0:31:40.00,0:31:48.00,Default,,0000,0000,0000,,What capitalization do you not like? [Inaudible].
Dialogue: 0,0:31:48.00,0:31:52.00,Default,,0000,0000,0000,,Yeah. So it turns out this file happens to all be
Dialogue: 0,0:31:52.00,0:32:00.00,Default,,0000,0000,0000,,lower case, but there's no harm in doing this.
Dialogue: 0,0:32:00.00,0:32:03.00,Default,,0000,0000,0000,,That way even if they weren't, it'll
Dialogue: 0,0:32:03.00,0:32:06.00,Default,,0000,0000,0000,,take care of that problem for us if we wanted it to.
Dialogue: 0,0:32:06.00,0:32:09.00,Default,,0000,0000,0000,,[Inaudible].
Dialogue: 0,0:32:09.00,0:32:11.00,Default,,0000,0000,0000,,I want lower case. Oh
Dialogue: 0,0:32:11.00,0:32:12.00,Default,,0000,0000,0000,,yeah, I do. Well, your
Dialogue: 0,0:32:12.00,0:32:15.00,Default,,0000,0000,0000,,case. You guys are so picky.
Dialogue: 0,0:32:15.00,0:32:18.00,Default,,0000,0000,0000,,All right. Here's my deal. I'm gonna take my map,
Dialogue: 0,0:32:18.00,0:32:21.00,Default,,0000,0000,0000,,and this is gonna be a line of code that's gonna make your head spin.
Dialogue: 0,0:32:21.00,0:32:31.00,Default,,0000,0000,0000,,Just go with it.
Dialogue: 0,0:32:31.00,0:32:38.00,Default,,0000,0000,0000,,This is the do all
Dialogue: 0,0:32:38.00,0:32:40.00,Default,,0000,0000,0000,,craziness. Okay.
Dialogue: 0,0:32:40.00,0:32:41.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:32:41.00,0:32:43.00,Default,,0000,0000,0000,,I've got this map,
Dialogue: 0,0:32:43.00,0:32:46.00,Default,,0000,0000,0000,,and what I wanna do is under the signature of this word,
Dialogue: 0,0:32:46.00,0:32:50.00,Default,,0000,0000,0000,,I want to look up the set of strings that's associated with it and tack this one in.
Dialogue: 0,0:32:50.00,0:32:54.00,Default,,0000,0000,0000,,And the add in this case with the set, I know that's gonna do non-duplication. In fact,
Dialogue: 0,0:32:54.00,0:32:58.00,Default,,0000,0000,0000,,the file doesn't contain duplicates, but if it did, I certainly don't want it to record it
Dialogue: 0,0:32:58.00,0:33:00.00,Default,,0000,0000,0000,,twice anyway, so I might as well do this.
Dialogue: 0,0:33:00.00,0:33:04.00,Default,,0000,0000,0000,,Now this form of this is a heavy lifter for a small piece of
Dialogue: 0,0:33:04.00,0:33:04.00,Default,,0000,0000,0000,,code.
Dialogue: 0,0:33:04.00,0:33:09.00,Default,,0000,0000,0000,,The signature then went and converted into the ACEHP form.
Dialogue: 0,0:33:09.00,0:33:12.00,Default,,0000,0000,0000,,I used that as the key into the table.
Dialogue: 0,0:33:12.00,0:33:16.00,Default,,0000,0000,0000,,If it was already there, it's gonna retrieve me an existing set that I'm gonna just go ahead and
Dialogue: 0,0:33:16.00,0:33:21.00,Default,,0000,0000,0000,,add a word onto. If it wasn't there, the behavior for the brackets is to create
Dialogue: 0,0:33:21.00,0:33:26.00,Default,,0000,0000,0000,,kind of a new empty
Dialogue: 0,0:33:26.00,0:33:28.00,Default,,0000,0000,0000,,value for that. So it'll use the key
Dialogue: 0,0:33:28.00,0:33:32.00,Default,,0000,0000,0000,,and create a default value for type. Well, the default value for set of string -so if you just create a
Dialogue: 0,0:33:32.00,0:33:32.00,Default,,0000,0000,0000,,set
Dialogue: 0,0:33:32.00,0:33:36.00,Default,,0000,0000,0000,,without any other information in the default constructor will always create you a
Dialogue: 0,0:33:36.00,0:33:40.00,Default,,0000,0000,0000,,nice clean empty set. So in fact, it will get me exactly what I want which is to put it in there with an empty
Dialogue: 0,0:33:40.00,0:33:43.00,Default,,0000,0000,0000,,set that I will immediately add the word into. So after
Dialogue: 0,0:33:43.00,0:33:46.00,Default,,0000,0000,0000,,I do this, I should have this fully populated map. And
Dialogue: 0,0:33:46.00,0:33:49.00,Default,,0000,0000,0000,,then I'm
Dialogue: 0,0:33:49.00,0:33:56.00,Default,,0000,0000,0000,,gonna do this just as a little test. I'm gonna say num words when I'm done
Dialogue: 0,0:33:56.00,0:33:58.00,Default,,0000,0000,0000,,to feel
Dialogue: 0,0:33:58.00,0:34:00.00,Default,,0000,0000,0000,,a little bit confident about what
Dialogue: 0,0:34:00.00,0:34:04.00,Default,,0000,0000,0000,,got put in there. How
Dialogue: 0,0:34:04.00,0:34:06.00,Default,,0000,0000,0000,,about I call it -that's a good idea. It's
Dialogue: 0,0:34:06.00,0:34:11.00,Default,,0000,0000,0000,,so fussy. C++ never does what you want.
Dialogue: 0,0:34:11.00,0:34:15.00,Default,,0000,0000,0000,,I think I called this thing OSPD2.txt that has the
Dialogue: 0,0:34:15.00,0:34:20.00,Default,,0000,0000,0000,,words in it.
Dialogue: 0,0:34:20.00,0:34:29.00,Default,,0000,0000,0000,,And then I need to declare the variable that I'm sticking all this stuff into is a set. So
Dialogue: 0,0:34:29.00,0:34:32.00,Default,,0000,0000,0000,,go in, load stuff,
Dialogue: 0,0:34:32.00,0:34:35.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:35.00,0:34:36.00,Default,,0000,0000,0000,,doing it's thing, the
Dialogue: 0,0:34:36.00,0:34:38.00,Default,,0000,0000,0000,,number of words 112,882. Okay.
Dialogue: 0,0:34:38.00,0:34:42.00,Default,,0000,0000,0000,,That's close enough. I can't remember the number that's in there, but that sounds like a fine
Dialogue: 0,0:34:42.00,0:34:43.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:43.00,0:34:47.00,Default,,0000,0000,0000,,approximation of it. So I feel like it did sort of manage to do something for it. And I can actually do this if I
Dialogue: 0,0:34:47.00,0:34:51.00,Default,,0000,0000,0000,,just wanna get a little glimpse of it is to use my iterator to look
Dialogue: 0,0:34:51.00,0:34:53.00,Default,,0000,0000,0000,,at
Dialogue: 0,0:34:53.00,0:35:04.00,Default,,0000,0000,0000,,something that's in there. Wait, is map a set of string? Iterator --
Dialogue: 0,0:35:04.00,0:35:05.00,Default,,0000,0000,0000,,file iter.hasNext. I'm gonna
Dialogue: 0,0:35:05.00,0:35:07.00,Default,,0000,0000,0000,,say key
Dialogue: 0,0:35:07.00,0:35:10.00,Default,,0000,0000,0000,,equals iter.next,
Dialogue: 0,0:35:10.00,0:35:13.00,Default,,0000,0000,0000,,
Dialogue: 0,0:35:13.00,0:35:18.00,Default,,0000,0000,0000,,and I'm going to print that key, and I'm going to print the size of the
Dialogue: 0,0:35:18.00,0:35:28.00,Default,,0000,0000,0000,,set because I'm at this
Dialogue: 0,0:35:28.00,0:35:33.00,Default,,0000,0000,0000,,point -I should see gobs of printing come out of this thing. It
Dialogue: 0,0:35:33.00,0:35:37.00,Default,,0000,0000,0000,,takes a little bit of a while to process the thing, and then
Dialogue: 0,0:35:37.00,0:35:42.00,Default,,0000,0000,0000,,see gobs and gobs of stuff going by. It looks like a lot of things are ones if you can
Dialogue: 0,0:35:42.00,0:35:45.00,Default,,0000,0000,0000,,imagine reading them as they go by because a lot of words are really just not anagrams
Dialogue: 0,0:35:45.00,0:35:48.00,Default,,0000,0000,0000,,of anything else. But
Dialogue: 0,0:35:48.00,0:35:52.00,Default,,0000,0000,0000,,some of the shorter ones have sort of a better chance.
Dialogue: 0,0:35:52.00,0:35:56.00,Default,,0000,0000,0000,,So you can find out here at the end that there are EEIKLPST. I don't know what that is. Leakiest? No. I don't
Dialogue: 0,0:35:56.00,0:35:58.00,Default,,0000,0000,0000,,know
Dialogue: 0,0:35:58.00,0:35:59.00,Default,,0000,0000,0000,,what that word is. I
Dialogue: 0,0:35:59.00,0:36:03.00,Default,,0000,0000,0000,,should write it in for any of them.
Dialogue: 0,0:36:03.00,0:36:09.00,Default,,0000,0000,0000,,This dictionary has a bunch of really crazy words in it too, so it makes it especially challenging. What is that? I don't know. That one
Dialogue: 0,0:36:09.00,0:36:10.00,Default,,0000,0000,0000,,almost looks
Dialogue: 0,0:36:10.00,0:36:14.00,Default,,0000,0000,0000,,like beginners, but it's got an F in it. It's the F beginners, a very famous
Dialogue: 0,0:36:14.00,0:36:16.00,Default,,0000,0000,0000,,word. You guys have probably heard
Dialogue: 0,0:36:16.00,0:36:19.00,Default,,0000,0000,0000,,of it. So I've seen that, and now I wanna do the thing where I will pick the
Dialogue: 0,0:36:19.00,0:36:21.00,Default,,0000,0000,0000,,largest one. I'd like to know.
Dialogue: 0,0:36:21.00,0:36:23.00,Default,,0000,0000,0000,,Somebody should tell me.
Dialogue: 0,0:36:23.00,0:36:25.00,Default,,0000,0000,0000,,Int max size [cuts
Dialogue: 0,0:36:25.00,0:36:28.00,Default,,0000,0000,0000,,out]
Dialogue: 0,0:36:28.00,0:36:30.00,Default,,0000,0000,0000,,max key, so I'll
Dialogue: 0,0:36:30.00,0:36:33.00,Default,,0000,0000,0000,,set this to be zero, and max
Dialogue: 0,0:36:33.00,0:36:34.00,Default,,0000,0000,0000,,key is that.
Dialogue: 0,0:36:34.00,0:36:35.00,Default,,0000,0000,0000,,And then I'm gonna do this. If
Dialogue: 0,0:36:35.00,0:36:38.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:36:38.00,0:36:40.00,Default,,0000,0000,0000,,size of this key is
Dialogue: 0,0:36:40.00,0:36:43.00,Default,,0000,0000,0000,,greater than my max size,
Dialogue: 0,0:36:43.00,0:36:55.00,Default,,0000,0000,0000,,then it's gonna get to be the new key.
Dialogue: 0,0:36:55.00,0:37:06.00,Default,,0000,0000,0000,,So after I did all of that then [cuts out]
Dialogue: 0,0:37:06.00,0:37:08.00,Default,,0000,0000,0000,,key.
Dialogue: 0,0:37:08.00,0:37:13.00,Default,,0000,0000,0000,,And then I probably wanna see what they are, so why don't I go ahead and take a look. Ah, I have to go to
Dialogue: 0,0:37:13.00,0:37:17.00,Default,,0000,0000,0000,,the type, though. [Inaudible]
Dialogue: 0,0:37:17.00,0:37:21.00,Default,,0000,0000,0000,,to equals
Dialogue: 0,0:37:21.00,0:37:22.00,Default,,0000,0000,0000,,M of
Dialogue: 0,0:37:22.00,0:37:27.00,Default,,0000,0000,0000,,key -max key, I guess, dot
Dialogue: 0,0:37:27.00,0:37:29.00,Default,,0000,0000,0000,,iterator,
Dialogue: 0,0:37:29.00,0:37:30.00,Default,,0000,0000,0000,,[inaudible] IT
Dialogue: 0,0:37:30.00,0:37:37.00,Default,,0000,0000,0000,,has next, CLIT.next [inaudible].
Dialogue: 0,0:37:37.00,0:37:43.00,Default,,0000,0000,0000,,So it went back. It found the maximum, in this case using the size of the sets as the distinguishing
Dialogue: 0,0:37:43.00,0:37:47.00,Default,,0000,0000,0000,,feature. And
Dialogue: 0,0:37:47.00,0:37:49.00,Default,,0000,0000,0000,,then max is AEPRS,
Dialogue: 0,0:37:49.00,0:37:51.00,Default,,0000,0000,0000,,which
Dialogue: 0,0:37:51.00,0:37:53.00,Default,,0000,0000,0000,,it's got a big old list of about 12.
Dialogue: 0,0:37:53.00,0:37:55.00,Default,,0000,0000,0000,,I think that's
Dialogue: 0,0:37:55.00,0:37:58.00,Default,,0000,0000,0000,,12, actually. Maybe 13.
Dialogue: 0,0:37:58.00,0:37:59.00,Default,,0000,0000,0000,,So now you know.
Dialogue: 0,0:37:59.00,0:38:02.00,Default,,0000,0000,0000,,You can impress your friends at parties. This is the kind of thing you can win bar bets on.
Dialogue: 0,0:38:02.00,0:38:03.00,Default,,0000,0000,0000,,Oh,
Dialogue: 0,0:38:03.00,0:38:06.00,Default,,0000,0000,0000,,yeah. What's the size of the largest
Dialogue: 0,0:38:06.00,0:38:07.00,Default,,0000,0000,0000,,anagram cluster?
Dialogue: 0,0:38:07.00,0:38:10.00,Default,,0000,0000,0000,,Everybody wants to know this kind of stuff. I can't believe you guys can sleep at night without
Dialogue: 0,0:38:10.00,0:38:12.00,Default,,0000,0000,0000,,actually knowing this.
Dialogue: 0,0:38:12.00,0:38:16.00,Default,,0000,0000,0000,,And what's neat to know though [inaudible] just to point out a couple of things that -you can use a little decomposition
Dialogue: 0,0:38:16.00,0:38:18.00,Default,,0000,0000,0000,,on this code,
Dialogue: 0,0:38:18.00,0:38:23.00,Default,,0000,0000,0000,,but there's kind of a very small amount of things we're having to do. For example, one of the things that's really
Dialogue: 0,0:38:23.00,0:38:27.00,Default,,0000,0000,0000,,powerful, things like the map where we can just figure out how to key the things
Dialogue: 0,0:38:27.00,0:38:29.00,Default,,0000,0000,0000,,to store the collection right under that key,
Dialogue: 0,0:38:29.00,0:38:33.00,Default,,0000,0000,0000,,then looking it up and adding something is a very
Dialogue: 0,0:38:33.00,0:38:36.00,Default,,0000,0000,0000,,efficient sort of direct operation, just building on these things and it going through and doing all
Dialogue: 0,0:38:36.00,0:38:37.00,Default,,0000,0000,0000,,the work of
Dialogue: 0,0:38:37.00,0:38:41.00,Default,,0000,0000,0000,,storing them, sorting them, making it efficient for us to retrieve them and look them up such that I can
Dialogue: 0,0:38:41.00,0:38:44.00,Default,,0000,0000,0000,,process 100,000 words
Dialogue: 0,0:38:44.00,0:38:49.00,Default,,0000,0000,0000,,in the blink of an eye, and then go back through, look at them all, find the biggest one,
Dialogue: 0,0:38:49.00,0:38:51.00,Default,,0000,0000,0000,,get my information out.
Dialogue: 0,0:38:51.00,0:38:55.00,Default,,0000,0000,0000,,When you make the call to M.size, is
Dialogue: 0,0:38:55.00,0:39:00.00,Default,,0000,0000,0000,,that the number of words? [Inaudible]. That is the number of keys. Keys, right. So that's not actually [inaudible].
Dialogue: 0,0:39:00.00,0:39:01.00,Default,,0000,0000,0000,,Yeah. So it doesn't know anything about
Dialogue: 0,0:39:01.00,0:39:04.00,Default,,0000,0000,0000,,everything else that was [inaudible], but in fact that's why it's
Dialogue: 0,0:39:04.00,0:39:07.00,Default,,0000,0000,0000,,[inaudible]. I know the dictionary has about 127,000 words. It turns out they form about
Dialogue: 0,0:39:07.00,0:39:08.00,Default,,0000,0000,0000,,
Dialogue: 0,0:39:08.00,0:39:11.00,Default,,0000,0000,0000,,112 unique
Dialogue: 0,0:39:11.00,0:39:14.00,Default,,0000,0000,0000,,signatures, and so there's actually another 20,000 words that are
Dialogue: 0,0:39:14.00,0:39:17.00,Default,,0000,0000,0000,,clung onto some existing signature. That's the number of unique signatures across
Dialogue: 0,0:39:17.00,0:39:20.00,Default,,0000,0000,0000,,the dictionary, not the number of words, so that's probably the wrong name to call
Dialogue: 0,0:39:20.00,0:39:22.00,Default,,0000,0000,0000,,it. For the M
Dialogue: 0,0:39:22.00,0:39:24.00,Default,,0000,0000,0000,,
Dialogue: 0,0:39:24.00,0:39:28.00,Default,,0000,0000,0000,,signature word thing where [inaudible] of the default just to create a new stack, that
Dialogue: 0,0:39:28.00,0:39:32.00,Default,,0000,0000,0000,,works as well for vectors [inaudible]? Yeah. It works for anything if you were just to declare
Dialogue: 0,0:39:32.00,0:39:34.00,Default,,0000,0000,0000,,it on the stack and the right thing happened,
Dialogue: 0,0:39:34.00,0:39:37.00,Default,,0000,0000,0000,,so vectors, set, maps. All those things do.
Dialogue: 0,0:39:37.00,0:39:41.00,Default,,0000,0000,0000,,But the primitive types like int and double, it doesn't. So it would work for string. String
Dialogue: 0,0:39:41.00,0:39:45.00,Default,,0000,0000,0000,,is an empty string. So for some of the fancier, more modern types tend to actually
Dialogue: 0,0:39:45.00,0:39:49.00,Default,,0000,0000,0000,,know how to just default construct themselves into a good state, but the primitives don't do that.
Dialogue: 0,0:39:49.00,0:39:53.00,Default,,0000,0000,0000,,So if you were having a map of ints and you wanted to have them start at zero, you need to really
Dialogue: 0,0:39:53.00,0:39:58.00,Default,,0000,0000,0000,,start them at zero. You can call just M sub this. It would be garbage, and it would just be operating with
Dialogue: 0,0:39:58.00,0:40:02.00,Default,,0000,0000,0000,,garbage from that way forward.
Dialogue: 0,0:40:02.00,0:40:06.00,Default,,0000,0000,0000,,All right. Well, we're good. What
Dialogue: 0,0:40:06.00,0:40:08.00,Default,,0000,0000,0000,,I'm gonna give you
Dialogue: 0,0:40:08.00,0:40:10.00,Default,,0000,0000,0000,,is the
Dialogue: 0,0:40:10.00,0:40:11.00,Default,,0000,0000,0000,,eight minute
Dialogue: 0,0:40:11.00,0:40:12.00,Default,,0000,0000,0000,,discussion of recursion
Dialogue: 0,0:40:12.00,0:40:14.00,Default,,0000,0000,0000,,that whets your appetite for
Dialogue: 0,0:40:14.00,0:40:18.00,Default,,0000,0000,0000,,the things we're gonna be doing next week.
Dialogue: 0,0:40:18.00,0:40:21.00,Default,,0000,0000,0000,,So recursion is one of those things I think that when you haven't yet
Dialogue: 0,0:40:21.00,0:40:24.00,Default,,0000,0000,0000,,had a chance to explore it first hand and other people tell you about it, it
Dialogue: 0,0:40:24.00,0:40:30.00,Default,,0000,0000,0000,,has sort of an awe inspiring sort of mystery, some fear, and whatnot.
Dialogue: 0,0:40:30.00,0:40:31.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:40:31.00,0:40:34.00,Default,,0000,0000,0000,,first off, I wanna kinda shake that fear off. It is a little bit
Dialogue: 0,0:40:34.00,0:40:35.00,Default,,0000,0000,0000,,hard to wrap your head around
Dialogue: 0,0:40:35.00,0:40:38.00,Default,,0000,0000,0000,,the first time you see it, but we're gonna have a whole week's worth of time to spend on it, so
Dialogue: 0,0:40:38.00,0:40:41.00,Default,,0000,0000,0000,,we're gonna
Dialogue: 0,0:40:41.00,0:40:42.00,Default,,0000,0000,0000,,try to give you a lot of
Dialogue: 0,0:40:42.00,0:40:46.00,Default,,0000,0000,0000,,different ways to think about it, and different problems to see to kinda help you do it. And I think
Dialogue: 0,0:40:46.00,0:40:48.00,Default,,0000,0000,0000,,once you do get your head around it, it turns out then
Dialogue: 0,0:40:48.00,0:40:53.00,Default,,0000,0000,0000,,you'll discover how infinitely powerful it is, that there is kind of a simple idea in it
Dialogue: 0,0:40:53.00,0:40:57.00,Default,,0000,0000,0000,,that once you kinda fully get your head around, you can explore and solve lots of different
Dialogue: 0,0:40:57.00,0:41:00.00,Default,,0000,0000,0000,,problems using this just one technique again and again.
Dialogue: 0,0:41:00.00,0:41:02.00,Default,,0000,0000,0000,,So in itself, it's
Dialogue: 0,0:41:02.00,0:41:04.00,Default,,0000,0000,0000,,a little bit mysterious at first glance, but then
Dialogue: 0,0:41:04.00,0:41:06.00,Default,,0000,0000,0000,,once you kind of
Dialogue: 0,0:41:06.00,0:41:09.00,Default,,0000,0000,0000,,master it, you'll be amazed at the kind of neat things you can do with it.
Dialogue: 0,0:41:09.00,0:41:15.00,Default,,0000,0000,0000,,So it is certainly what I'd consider an indispensable tool in a programmer's tool kit. The kind of
Dialogue: 0,0:41:15.00,0:41:19.00,Default,,0000,0000,0000,,problems you can solve using the techniques you have so far is fundamentally limited. And
Dialogue: 0,0:41:19.00,0:41:22.00,Default,,0000,0000,0000,,part of what we need to do in this class is expose you to these new ways of solving
Dialogue: 0,0:41:22.00,0:41:26.00,Default,,0000,0000,0000,,harder, more sophisticated problems that the old techniques don't work for. One of the
Dialogue: 0,0:41:26.00,0:41:31.00,Default,,0000,0000,0000,,cool things about recursion is it actually lends very simple, elegant, short solutions
Dialogue: 0,0:41:31.00,0:41:35.00,Default,,0000,0000,0000,,to problems that at first glance seem completely unsolvable.
Dialogue: 0,0:41:35.00,0:41:36.00,Default,,0000,0000,0000,,That if you can
Dialogue: 0,0:41:36.00,0:41:40.00,Default,,0000,0000,0000,,formulate a structure for [inaudible], you will discover that the code is not long
Dialogue: 0,0:41:40.00,0:41:45.00,Default,,0000,0000,0000,,to write. It's not tedious to write. The tricky part is to figure out how
Dialogue: 0,0:41:45.00,0:41:47.00,Default,,0000,0000,0000,,to express it,
Dialogue: 0,0:41:47.00,0:41:50.00,Default,,0000,0000,0000,,so it's more of a thinking puzzle than it is a coding puzzle. I
Dialogue: 0,0:41:50.00,0:41:55.00,Default,,0000,0000,0000,,certainly like thinking puzzles as much as coding puzzles if not more.
Dialogue: 0,0:41:55.00,0:41:58.00,Default,,0000,0000,0000,,The general sort of idea is that
Dialogue: 0,0:41:58.00,0:42:02.00,Default,,0000,0000,0000,,you are going to try to solve a problem
Dialogue: 0,0:42:02.00,0:42:05.00,Default,,0000,0000,0000,,-instead of sort of breaking it down into component tasks like if I need to make dinner, I need
Dialogue: 0,0:42:05.00,0:42:08.00,Default,,0000,0000,0000,,to go to the store and buy things, and I need to come home, and chop them, and get
Dialogue: 0,0:42:08.00,0:42:12.00,Default,,0000,0000,0000,,the recipe. You think of what your standard decomposition is all about
Dialogue: 0,0:42:12.00,0:42:16.00,Default,,0000,0000,0000,,-breaking down your tasks into A, B, and C, and D, and then you add them all together to get
Dialogue: 0,0:42:16.00,0:42:17.00,Default,,0000,0000,0000,,
Dialogue: 0,0:42:17.00,0:42:20.00,Default,,0000,0000,0000,,the whole task done. Recursion has this kind of very different way of thinking about the problem, which is like
Dialogue: 0,0:42:20.00,0:42:22.00,Default,,0000,0000,0000,,well if I needed to get Task A done,
Dialogue: 0,0:42:22.00,0:42:26.00,Default,,0000,0000,0000,,and I had Task A prime, which was somehow a lot like the task I was trying to solve, but it somehow
Dialogue: 0,0:42:26.00,0:42:29.00,Default,,0000,0000,0000,,was a little bit simpler, a little bit easier,
Dialogue: 0,0:42:29.00,0:42:32.00,Default,,0000,0000,0000,,a little bit more manageable than the one I started out to solve,
Dialogue: 0,0:42:32.00,0:42:34.00,Default,,0000,0000,0000,,and if I had that solution
Dialogue: 0,0:42:34.00,0:42:37.00,Default,,0000,0000,0000,,-so if somehow I could delegate it off to some
Dialogue: 0,0:42:37.00,0:42:39.00,Default,,0000,0000,0000,,
Dialogue: 0,0:42:39.00,0:42:43.00,Default,,0000,0000,0000,,minion who works for me, and then I could use that to solve my problem, then my
Dialogue: 0,0:42:43.00,0:42:45.00,Default,,0000,0000,0000,,job would be made much easier by using that result of
Dialogue: 0,0:42:45.00,0:42:48.00,Default,,0000,0000,0000,,solving a similar problem that's a little bit [inaudible].
Dialogue: 0,0:42:48.00,0:42:51.00,Default,,0000,0000,0000,,Okay, that seems a little bit wacky.
Dialogue: 0,0:42:51.00,0:42:55.00,Default,,0000,0000,0000,,Let me give you sort of an example of how this might work.
Dialogue: 0,0:42:55.00,0:42:58.00,Default,,0000,0000,0000,,So your standard problem, I said yeah, it's like you do these dissimilar sub problems.
Dialogue: 0,0:42:58.00,0:43:04.00,Default,,0000,0000,0000,,Let's imagine I had this goal where I wanted to survey the Stanford student body.
Dialogue: 0,0:43:04.00,0:43:06.00,Default,,0000,0000,0000,,I don't want just like a
Dialogue: 0,0:43:06.00,0:43:08.00,Default,,0000,0000,0000,,haphazard
Dialogue: 0,0:43:08.00,0:43:11.00,Default,,0000,0000,0000,,most of the people involved. Let's say I really wanted to get input from every single person
Dialogue: 0,0:43:11.00,0:43:16.00,Default,,0000,0000,0000,,on campus whether they think having cardinal as your mascot is a ridiculous choice or not. So
Dialogue: 0,0:43:16.00,0:43:19.00,Default,,0000,0000,0000,,let's imagine I really wanna hear from all 10,000 students.
Dialogue: 0,0:43:19.00,0:43:21.00,Default,,0000,0000,0000,,Now I can stand out in White Plaza with a big
Dialogue: 0,0:43:21.00,0:43:26.00,Default,,0000,0000,0000,,note pad and try to accost people and sort of work my way down the list.
Dialogue: 0,0:43:26.00,0:43:29.00,Default,,0000,0000,0000,,And then I'd be there for eons and never solve my problem.
Dialogue: 0,0:43:29.00,0:43:31.00,Default,,0000,0000,0000,,Instead, what I decide to do is I say well I'm gonna
Dialogue: 0,0:43:31.00,0:43:32.00,Default,,0000,0000,0000,,recruit some people to help me
Dialogue: 0,0:43:32.00,0:43:34.00,Default,,0000,0000,0000,,because I'm lazy
Dialogue: 0,0:43:34.00,0:43:35.00,Default,,0000,0000,0000,,as we've already established,
Dialogue: 0,0:43:35.00,0:43:37.00,Default,,0000,0000,0000,,and I would like to get
Dialogue: 0,0:43:37.00,0:43:41.00,Default,,0000,0000,0000,,some other people to join in my quest to answer these burning questions and to
Dialogue: 0,0:43:41.00,0:43:43.00,Default,,0000,0000,0000,,solve the survey.
Dialogue: 0,0:43:43.00,0:43:45.00,Default,,0000,0000,0000,,So what I do is I round up ten people let's say,
Dialogue: 0,0:43:45.00,0:43:49.00,Default,,0000,0000,0000,,and I say would you help me, and I decide to divide the campus into kind of ten
Dialogue: 0,0:43:49.00,0:43:51.00,Default,,0000,0000,0000,,partitions. And I say if you
Dialogue: 0,0:43:51.00,0:43:54.00,Default,,0000,0000,0000,,could survey all the people whose names begin with A, B, and C, that would really help.
Dialogue: 0,0:43:54.00,0:43:56.00,Default,,0000,0000,0000,,And if you could do [inaudible] Gs, and
Dialogue: 0,0:43:56.00,0:44:00.00,Default,,0000,0000,0000,,if you would do -and if I divide up the alphabet that way, give each of them two or three letters, and I
Dialogue: 0,0:44:00.00,0:44:02.00,Default,,0000,0000,0000,,say if you would go get the data, it'd be really
Dialogue: 0,0:44:02.00,0:44:05.00,Default,,0000,0000,0000,,easy for me to do my job then. If I just took all their
Dialogue: 0,0:44:05.00,0:44:08.00,Default,,0000,0000,0000,,data [inaudible]. Well, being
Dialogue: 0,0:44:08.00,0:44:12.00,Default,,0000,0000,0000,,the kind of lazy person that I am, it's likely that the ten people I recruit would have similar lazy qualities
Dialogue: 0,0:44:12.00,0:44:15.00,Default,,0000,0000,0000,,because lazy people hang out with other lazy people.
Dialogue: 0,0:44:15.00,0:44:18.00,Default,,0000,0000,0000,,And so the person who was in charge of A, B, C, the first thing they do is turn around and find ten
Dialogue: 0,0:44:18.00,0:44:22.00,Default,,0000,0000,0000,,more friends, and then they divide it up and say could you do the
Dialogue: 0,0:44:22.00,0:44:23.00,Default,,0000,0000,0000,,AA through AM and so on.
Dialogue: 0,0:44:23.00,0:44:25.00,Default,,0000,0000,0000,,If they divide it into these pools of
Dialogue: 0,0:44:25.00,0:44:30.00,Default,,0000,0000,0000,,one tenth of what they were responsible for, and say you can go get the information from these people,
Dialogue: 0,0:44:30.00,0:44:31.00,Default,,0000,0000,0000,,and if they did the same thing
Dialogue: 0,0:44:31.00,0:44:35.00,Default,,0000,0000,0000,,-so if everybody along the road. We started with 10,000. Now each person had 1,000
Dialogue: 0,0:44:35.00,0:44:39.00,Default,,0000,0000,0000,,to survey. They asked their friend to do 100. Their friend asked ten people to do
Dialogue: 0,0:44:39.00,0:44:39.00,Default,,0000,0000,0000,,ten.
Dialogue: 0,0:44:39.00,0:44:43.00,Default,,0000,0000,0000,,And then at some point, the person who has ten says well I just need to ask these ten people.
Dialogue: 0,0:44:43.00,0:44:45.00,Default,,0000,0000,0000,,
Dialogue: 0,0:44:45.00,0:44:47.00,Default,,0000,0000,0000,,Once I get their data, we don't need to do anything further.
Dialogue: 0,0:44:47.00,0:44:50.00,Default,,0000,0000,0000,,So at some point the problem becomes so small, so simple,
Dialogue: 0,0:44:50.00,0:44:55.00,Default,,0000,0000,0000,,even though it was kind of the same problem all along. I just reproduced the same problem we had, but in
Dialogue: 0,0:44:55.00,0:44:58.00,Default,,0000,0000,0000,,a slightly more tractable form, but then I divided it around. Divide and conquer
Dialogue: 0,0:44:58.00,0:45:00.00,Default,,0000,0000,0000,,sometimes they call this to where
Dialogue: 0,0:45:00.00,0:45:01.00,Default,,0000,0000,0000,,I spread out the work
Dialogue: 0,0:45:01.00,0:45:05.00,Default,,0000,0000,0000,,around a bunch of people to where each person's contribution is just a little part of the whole.
Dialogue: 0,0:45:05.00,0:45:09.00,Default,,0000,0000,0000,,You had to find the ten volunteers around underneath you and
Dialogue: 0,0:45:09.00,0:45:11.00,Default,,0000,0000,0000,,get their
Dialogue: 0,0:45:11.00,0:45:14.00,Default,,0000,0000,0000,,help in solving the problem, but nobody had to do much work, and that's kind of a really
Dialogue: 0,0:45:14.00,0:45:18.00,Default,,0000,0000,0000,,interesting way to solve a problem. It sounds like a very big problem of surveying
Dialogue: 0,0:45:18.00,0:45:19.00,Default,,0000,0000,0000,,10,000 people,
Dialogue: 0,0:45:19.00,0:45:23.00,Default,,0000,0000,0000,,but by dividing and conquer, everybody has a little tiny role to play. You leverage a lot
Dialogue: 0,0:45:23.00,0:45:24.00,Default,,0000,0000,0000,,of people getting it done,
Dialogue: 0,0:45:24.00,0:45:29.00,Default,,0000,0000,0000,,and there is this self-similarity to it, which is kind of intriguing that
Dialogue: 0,0:45:29.00,0:45:34.00,Default,,0000,0000,0000,,everybody is trying to solve the same problem but just at different levels of scale.
Dialogue: 0,0:45:34.00,0:45:36.00,Default,,0000,0000,0000,,And so this idea
Dialogue: 0,0:45:36.00,0:45:38.00,Default,,0000,0000,0000,,applies to things like phone trees rather than
Dialogue: 0,0:45:38.00,0:45:42.00,Default,,0000,0000,0000,,trying to get the message out to everybody in my class, it might be that I call two people who call two
Dialogue: 0,0:45:42.00,0:45:45.00,Default,,0000,0000,0000,,friends who call two friends until everybody gets covered.
Dialogue: 0,0:45:45.00,0:45:48.00,Default,,0000,0000,0000,,Nobody does the whole job. Everybody just does a little part of it. Sometimes you'll see these
Dialogue: 0,0:45:48.00,0:45:50.00,Default,,0000,0000,0000,,fractal drawings where
Dialogue: 0,0:45:50.00,0:45:55.00,Default,,0000,0000,0000,,there is a large leaf which when you look closer actually consists of littler leaves,
Dialogue: 0,0:45:55.00,0:45:57.00,Default,,0000,0000,0000,,which themselves are littler leaves, so that at
Dialogue: 0,0:45:57.00,0:45:58.00,Default,,0000,0000,0000,,every level of scale
Dialogue: 0,0:45:58.00,0:46:01.00,Default,,0000,0000,0000,,the same image is being reproduced,
Dialogue: 0,0:46:01.00,0:46:05.00,Default,,0000,0000,0000,,and the result kind of on the outside is something that in itself if you look deeper has the
Dialogue: 0,0:46:05.00,0:46:08.00,Default,,0000,0000,0000,,same problem but smaller embedded in it.
Dialogue: 0,0:46:08.00,0:46:10.00,Default,,0000,0000,0000,,So it's a pretty neat
Dialogue: 0,0:46:10.00,0:46:11.00,Default,,0000,0000,0000,,sort of
Dialogue: 0,0:46:11.00,0:46:13.00,Default,,0000,0000,0000,,way of solving things.
Dialogue: 0,0:46:13.00,0:46:14.00,Default,,0000,0000,0000,,I am
Dialogue: 0,0:46:14.00,0:46:18.00,Default,,0000,0000,0000,,gonna tell you a little bit about how the code looks, and then I really am not gonna be able to show you much code today.
Dialogue: 0,0:46:18.00,0:46:23.00,Default,,0000,0000,0000,,I think it's actually even better to show you this code on Monday when we can come back fresh,
Dialogue: 0,0:46:23.00,0:46:27.00,Default,,0000,0000,0000,,but that it involves taking -So we're looking at functional recursion first,
Dialogue: 0,0:46:27.00,0:46:29.00,Default,,0000,0000,0000,,and functional recursion is
Dialogue: 0,0:46:29.00,0:46:33.00,Default,,0000,0000,0000,,taking some sort of functions, a function that takes an input and returns an answers, returns
Dialogue: 0,0:46:33.00,0:46:36.00,Default,,0000,0000,0000,,non-void thing that comes back.
Dialogue: 0,0:46:36.00,0:46:39.00,Default,,0000,0000,0000,,And we're gonna be looking at problems where you're trying to solve this big problem,
Dialogue: 0,0:46:39.00,0:46:44.00,Default,,0000,0000,0000,,and that if you had the answer to making a call to yourself on a smaller version of
Dialogue: 0,0:46:44.00,0:46:45.00,Default,,0000,0000,0000,,the problem
Dialogue: 0,0:46:45.00,0:46:48.00,Default,,0000,0000,0000,,-maybe one call, maybe two calls, maybe several calls
Dialogue: 0,0:46:48.00,0:46:52.00,Default,,0000,0000,0000,,-that you could add those, or multiply those, or combine those in some way to answer the
Dialogue: 0,0:46:52.00,0:46:53.00,Default,,0000,0000,0000,,bigger problem. So
Dialogue: 0,0:46:53.00,0:46:56.00,Default,,0000,0000,0000,,if I were trying to solve
Dialogue: 0,0:46:56.00,0:47:03.00,Default,,0000,0000,0000,,this campus survey, having the answers to these smaller campus surveys gives me that total result. And
Dialogue: 0,0:47:03.00,0:47:05.00,Default,,0000,0000,0000,,so the -I really should not try to do this in two minutes. What
Dialogue: 0,0:47:05.00,0:47:09.00,Default,,0000,0000,0000,,I should do is try to tell you on Monday. We'll come back and we'll talk about recursion, and it
Dialogue: 0,0:47:09.00,0:47:11.00,Default,,0000,0000,0000,,will be an impressive week. Meanwhile, work on
Dialogue: 0,0:47:11.00,0:47:14.00,Default,,0000,0000,0000,,your ADT homework.