[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:13.00,Default,,0000,0000,0000,, Dialogue: 0,0:00:13.00,0:00:16.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional Dialogue: 0,0:00:16.00,0:00:26.00,Default,,0000,0000,0000,,Development. Dialogue: 0,0:00:26.00,0:00:27.00,Default,,0000,0000,0000,,Hi, there. Dialogue: 0,0:00:27.00,0:00:29.00,Default,,0000,0000,0000,,It's Dialogue: 0,0:00:29.00,0:00:36.00,Default,,0000,0000,0000,,Wednesday. We are coming to the end of this fine quarter. So Dialogue: 0,0:00:36.00,0:00:39.00,Default,,0000,0000,0000,,what I'm going to do today is I Dialogue: 0,0:00:39.00,0:00:43.00,Default,,0000,0000,0000,,brought a cup filled with candy. We'll start with that Dialogue: 0,0:00:43.00,0:00:45.00,Default,,0000,0000,0000,,because that's going to be helpful. What I'd like to do is it's just a couple Dialogue: 0,0:00:45.00,0:00:50.00,Default,,0000,0000,0000,,bits of loose ends, some things that I wanted to touch on that Dialogue: 0,0:00:50.00,0:00:53.00,Default,,0000,0000,0000,,have come and gone this quarter. I maybe wanted to pull them together and reach a bit of closure Dialogue: 0,0:00:53.00,0:00:54.00,Default,,0000,0000,0000,,on. Dialogue: 0,0:00:54.00,0:00:57.00,Default,,0000,0000,0000,,Then hopefully, if we have time, we'll move on to what Dialogue: 0,0:00:57.00,0:01:00.00,Default,,0000,0000,0000,,happens after this. If you liked 106b, what do you do? If you don't like Dialogue: 0,0:01:00.00,0:01:01.00,Default,,0000,0000,0000,,106b, what do you do? Dialogue: 0,0:01:01.00,0:01:02.00,Default,,0000,0000,0000,, Dialogue: 0,0:01:02.00,0:01:06.00,Default,,0000,0000,0000,,What kind of options and future opportunities are there Dialogue: 0,0:01:06.00,0:01:08.00,Default,,0000,0000,0000,,after this Dialogue: 0,0:01:08.00,0:01:10.00,Default,,0000,0000,0000,,ends? I'm going to talk a little about some of the things that Dialogue: 0,0:01:10.00,0:01:12.00,Default,,0000,0000,0000,,[inaudible], but I do want to talk about the final just Dialogue: 0,0:01:12.00,0:01:15.00,Default,,0000,0000,0000,,for a second because it is kind of a Dialogue: 0,0:01:15.00,0:01:17.00,Default,,0000,0000,0000,,last Dialogue: 0,0:01:17.00,0:01:19.00,Default,,0000,0000,0000,,opportunity for you to show us your mastery of the material Dialogue: 0,0:01:19.00,0:01:22.00,Default,,0000,0000,0000,,and get the grade that you've been working hard for all quarter. Dialogue: 0,0:01:22.00,0:01:26.00,Default,,0000,0000,0000,,It does carry a certain amount of weight. 30 percent of the weight in the default Dialogue: 0,0:01:26.00,0:01:27.00,Default,,0000,0000,0000,,system is actually placed on the final, Dialogue: 0,0:01:27.00,0:01:30.00,Default,,0000,0000,0000,,and more of it can move to that if you have a better Dialogue: 0,0:01:30.00,0:01:33.00,Default,,0000,0000,0000,,showing on the final than you did in the midterm. We're happy to move some of that Dialogue: 0,0:01:33.00,0:01:34.00,Default,,0000,0000,0000,,weight over so it could actually Dialogue: 0,0:01:34.00,0:01:36.00,Default,,0000,0000,0000,,account for even more of your total grade. Dialogue: 0,0:01:36.00,0:01:38.00,Default,,0000,0000,0000,,So there's a lot riding on it, and you want to be sure you come Dialogue: 0,0:01:38.00,0:01:40.00,Default,,0000,0000,0000,,ready to show us the Dialogue: 0,0:01:40.00,0:01:44.00,Default,,0000,0000,0000,,things that you know and that you have comprehension and mastery over. Dialogue: 0,0:01:44.00,0:01:47.00,Default,,0000,0000,0000,,To note, though, it is going to look a little bit different than the midterm in terms of its Dialogue: 0,0:01:47.00,0:01:51.00,Default,,0000,0000,0000,,emphasis. We are going to see a lot more of this nitty gritty dynamic data Dialogue: 0,0:01:51.00,0:01:52.00,Default,,0000,0000,0000,,structure, Dialogue: 0,0:01:52.00,0:01:53.00,Default,,0000,0000,0000,,Linklis, trees, Dialogue: 0,0:01:53.00,0:01:56.00,Default,,0000,0000,0000,,graphs, pointer-based Dialogue: 0,0:01:56.00,0:01:58.00,Default,,0000,0000,0000,,structures with the Dialogue: 0,0:01:58.00,0:02:01.00,Default,,0000,0000,0000,,inherent complications in dealing with that kind of dynamic structure. So bringing Dialogue: 0,0:02:01.00,0:02:03.00,Default,,0000,0000,0000,,your best game to this exam Dialogue: 0,0:02:03.00,0:02:05.00,Default,,0000,0000,0000,,is certainly going to pay off here. The Dialogue: 0,0:02:05.00,0:02:08.00,Default,,0000,0000,0000,,coding that you will see will look a lot like what's in the assignments. If you already had a Dialogue: 0,0:02:08.00,0:02:11.00,Default,,0000,0000,0000,,chance to look at the practice exam, you'll see that there are Dialogue: 0,0:02:11.00,0:02:13.00,Default,,0000,0000,0000,,themes there that echo the things you did on the work. You want to try to make sure Dialogue: 0,0:02:13.00,0:02:15.00,Default,,0000,0000,0000,,that's we're connecting to the Dialogue: 0,0:02:15.00,0:02:16.00,Default,,0000,0000,0000,, Dialogue: 0,0:02:16.00,0:02:17.00,Default,,0000,0000,0000,,effort you've put in all along. Dialogue: 0,0:02:17.00,0:02:20.00,Default,,0000,0000,0000,,There will actually be some opportunity to think a little bit at a higher level Dialogue: 0,0:02:20.00,0:02:23.00,Default,,0000,0000,0000,,about making and analyzing choices for design and implementation. I'm going to talk a Dialogue: 0,0:02:23.00,0:02:25.00,Default,,0000,0000,0000,,little bit about that today because I feel like Dialogue: 0,0:02:25.00,0:02:26.00,Default,,0000,0000,0000,,at any given moment, we're talking about Dialogue: 0,0:02:26.00,0:02:30.00,Default,,0000,0000,0000,,how we might implement a stack and how we might implement a queue. Sometimes it helps to Dialogue: 0,0:02:30.00,0:02:32.00,Default,,0000,0000,0000,,step back a level and think a little bit about the choices for Dialogue: 0,0:02:32.00,0:02:37.00,Default,,0000,0000,0000,,the bigger picture of when to use a stack and queue and how to make Dialogue: 0,0:02:37.00,0:02:40.00,Default,,0000,0000,0000,,decisions in the large about those tradeoffs that are intelligent and Dialogue: 0,0:02:40.00,0:02:42.00,Default,,0000,0000,0000,,grounded. So I'll do a little bit of that today, and then Dialogue: 0,0:02:42.00,0:02:45.00,Default,,0000,0000,0000,,some of that has been built up all quarter long. Dialogue: 0,0:02:45.00,0:02:48.00,Default,,0000,0000,0000,,It is open book and open notes. You can bring all your printouts, your readers, Dialogue: 0,0:02:48.00,0:02:50.00,Default,,0000,0000,0000,,sections, all those sort of things. Dialogue: 0,0:02:50.00,0:02:53.00,Default,,0000,0000,0000,,For some people, that translates to this idea that, well, I don't need to Dialogue: 0,0:02:53.00,0:02:56.00,Default,,0000,0000,0000,,prepare because I'll have all my stuff there. If I need to know something Dialogue: 0,0:02:56.00,0:02:59.00,Default,,0000,0000,0000,,in the exam, I'll just go look it up. That's certainly true for looking up details. You want to remember how Dialogue: 0,0:02:59.00,0:03:02.00,Default,,0000,0000,0000,,this works or you had a piece of code that you think was similar. It could help Dialogue: 0,0:03:02.00,0:03:05.00,Default,,0000,0000,0000,,you to brainstorm what you're trying to do this time. But Dialogue: 0,0:03:05.00,0:03:08.00,Default,,0000,0000,0000,,you're not likely to have time to learn new things n the exam. So if there's Dialogue: 0,0:03:08.00,0:03:11.00,Default,,0000,0000,0000,,something that you really feel you have not Dialogue: 0,0:03:11.00,0:03:12.00,Default,,0000,0000,0000,,gotten your head around, Dialogue: 0,0:03:12.00,0:03:17.00,Default,,0000,0000,0000,,the investment upfront before you get into the exam is where to get that Dialogue: 0,0:03:17.00,0:03:19.00,Default,,0000,0000,0000,,understanding in place rather than trying, in the exam, to be flipping Dialogue: 0,0:03:19.00,0:03:22.00,Default,,0000,0000,0000,,through chapter ten, trying to learn something. It Dialogue: 0,0:03:22.00,0:03:23.00,Default,,0000,0000,0000,,may not really play out. Dialogue: 0,0:03:23.00,0:03:27.00,Default,,0000,0000,0000,,I highly recommend practicing on paper in an exam-like environment. So really Dialogue: 0,0:03:27.00,0:03:28.00,Default,,0000,0000,0000,,working Dialogue: 0,0:03:28.00,0:03:31.00,Default,,0000,0000,0000,,the way you will be working in the exam to give yourself Dialogue: 0,0:03:31.00,0:03:33.00,Default,,0000,0000,0000,,the best, Dialogue: 0,0:03:33.00,0:03:35.00,Default,,0000,0000,0000,,consistent prep for what's happening there. Dialogue: 0,0:03:35.00,0:03:39.00,Default,,0000,0000,0000,,Then some people have asked about extra problems, just wanting more of them to work on. I'll give you a Dialogue: 0,0:03:39.00,0:03:41.00,Default,,0000,0000,0000,,couple places where you can look for things. One is that cs106 is Dialogue: 0,0:03:41.00,0:03:44.00,Default,,0000,0000,0000,,being offered this same quarter, and they are just the honors version of our class. Dialogue: 0,0:03:44.00,0:03:45.00,Default,,0000,0000,0000,,So they have some Dialogue: 0,0:03:45.00,0:03:49.00,Default,,0000,0000,0000,,slightly notched up problems. But their practice and real midterm are posted on their Dialogue: 0,0:03:49.00,0:03:51.00,Default,,0000,0000,0000,,website as well as their practice final. Dialogue: 0,0:03:51.00,0:03:52.00,Default,,0000,0000,0000,, Dialogue: 0,0:03:52.00,0:03:55.00,Default,,0000,0000,0000,,They have very similar coverage. They did some assignments that were like Dialogue: 0,0:03:55.00,0:03:58.00,Default,,0000,0000,0000,,ours, some that were a little bit different, but still go places to kind of Dialogue: 0,0:03:58.00,0:03:59.00,Default,,0000,0000,0000,,just grab Dialogue: 0,0:03:59.00,0:04:00.00,Default,,0000,0000,0000,,actual exam problems with their solution. Dialogue: 0,0:04:00.00,0:04:04.00,Default,,0000,0000,0000,,The chapter exercises and section problems often are old Dialogue: 0,0:04:04.00,0:04:05.00,Default,,0000,0000,0000,,exam problems or Dialogue: 0,0:04:05.00,0:04:08.00,Default,,0000,0000,0000,,eventually became exam problems. So they kind of come and go in terms of being used as Dialogue: 0,0:04:08.00,0:04:12.00,Default,,0000,0000,0000,,examples or used as exam problems. So they're definitely places to Dialogue: 0,0:04:12.00,0:04:17.00,Default,,0000,0000,0000,,pick up extra mileage. Okay. So let me tell Dialogue: 0,0:04:17.00,0:04:18.00,Default,,0000,0000,0000,,you a little bit about Dialogue: 0,0:04:18.00,0:04:21.00,Default,,0000,0000,0000,,- any questions about the final? Okay. Let me talk about Dialogue: 0,0:04:21.00,0:04:26.00,Default,,0000,0000,0000,,this line Dialogue: 0,0:04:26.00,0:04:28.00,Default,,0000,0000,0000,,just for a second because I feel like we have Dialogue: 0,0:04:28.00,0:04:31.00,Default,,0000,0000,0000,,touched on these themes again and again, but maybe it's good to have Dialogue: 0,0:04:31.00,0:04:32.00,Default,,0000,0000,0000,,at least one Dialogue: 0,0:04:32.00,0:04:35.00,Default,,0000,0000,0000,,moment of trying to pull this together and think a little bit about Dialogue: 0,0:04:35.00,0:04:38.00,Default,,0000,0000,0000,,the closure and the big picture of all these things. Dialogue: 0,0:04:38.00,0:04:41.00,Default,,0000,0000,0000,,A lot of what we're talking about in the beginning was we Dialogue: 0,0:04:41.00,0:04:44.00,Default,,0000,0000,0000,,were giving you these abstractions, these cool things to do stuff with, a map, a Dialogue: 0,0:04:44.00,0:04:45.00,Default,,0000,0000,0000,,stack, a queue, a vector, Dialogue: 0,0:04:45.00,0:04:49.00,Default,,0000,0000,0000,,and problems to solve where those abstractions have a role to play. Dialogue: 0,0:04:49.00,0:04:50.00,Default,,0000,0000,0000,,Then we spent a long time saying, Dialogue: 0,0:04:50.00,0:04:53.00,Default,,0000,0000,0000,,okay, now that it's our job to make those abstractions work, Dialogue: 0,0:04:53.00,0:04:56.00,Default,,0000,0000,0000,,what techniques can we use? What algorithms Dialogue: 0,0:04:56.00,0:04:59.00,Default,,0000,0000,0000,,and data structures will help us manipulate and Dialogue: 0,0:04:59.00,0:05:02.00,Default,,0000,0000,0000,,model those structures in efficient ways. We Dialogue: 0,0:05:02.00,0:05:05.00,Default,,0000,0000,0000,,certainly spent a lot of time talking about runtime performance as though that Dialogue: 0,0:05:05.00,0:05:08.00,Default,,0000,0000,0000,,was maybe a little too much in your mind to think that was the only thing Dialogue: 0,0:05:08.00,0:05:11.00,Default,,0000,0000,0000,,that really mattered. How fast can we make something? O of N is better Dialogue: 0,0:05:11.00,0:05:12.00,Default,,0000,0000,0000,,than N squared. Dialogue: 0,0:05:12.00,0:05:15.00,Default,,0000,0000,0000,,Log N is better than N, driving to these holy grails of Dialogue: 0,0:05:15.00,0:05:16.00,Default,,0000,0000,0000,,bringing the time down. Dialogue: 0,0:05:16.00,0:05:19.00,Default,,0000,0000,0000,,It's certainly a very important factor Dialogue: 0,0:05:19.00,0:05:20.00,Default,,0000,0000,0000,,that often - Dialogue: 0,0:05:20.00,0:05:23.00,Default,,0000,0000,0000,,the difference between something being linear and something being quadratic is a Dialogue: 0,0:05:23.00,0:05:27.00,Default,,0000,0000,0000,,matter of it being tractable at all for the problem at hand. You cannot sort a Dialogue: 0,0:05:27.00,0:05:32.00,Default,,0000,0000,0000,,million numbers in a quadratic sort in nearly Dialogue: 0,0:05:32.00,0:05:35.00,Default,,0000,0000,0000,,the same time. For large enough data sets, it'd Dialogue: 0,0:05:35.00,0:05:37.00,Default,,0000,0000,0000,,be completely unfeasible. Dialogue: 0,0:05:37.00,0:05:40.00,Default,,0000,0000,0000,,So it is important to have that big picture, to be thinking about it and know about Dialogue: 0,0:05:40.00,0:05:42.00,Default,,0000,0000,0000,,those tradeoffs, to understand issues Dialogue: 0,0:05:42.00,0:05:44.00,Default,,0000,0000,0000,,of scale here. Dialogue: 0,0:05:44.00,0:05:47.00,Default,,0000,0000,0000,,But we also did some stuff on the homework about actual empirical time Dialogue: 0,0:05:47.00,0:05:50.00,Default,,0000,0000,0000,,results, which is another way to bolster our understanding. The big O Dialogue: 0,0:05:50.00,0:05:51.00,Default,,0000,0000,0000,,tells us these things, but Dialogue: 0,0:05:51.00,0:05:53.00,Default,,0000,0000,0000,,what really happens in real life Dialogue: 0,0:05:53.00,0:05:57.00,Default,,0000,0000,0000,,matches it, but not precisely. Those constant factors, we threw away, Dialogue: 0,0:05:57.00,0:06:00.00,Default,,0000,0000,0000,,and other artifacts that are Dialogue: 0,0:06:00.00,0:06:03.00,Default,,0000,0000,0000,,happening in the real world often give us new insights about things and Dialogue: 0,0:06:03.00,0:06:06.00,Default,,0000,0000,0000,,challenges that we're facing. Dialogue: 0,0:06:06.00,0:06:09.00,Default,,0000,0000,0000,,We also need to think about things like mix of expected operations, having some be Dialogue: 0,0:06:09.00,0:06:11.00,Default,,0000,0000,0000,,slow Dialogue: 0,0:06:11.00,0:06:14.00,Default,,0000,0000,0000,,at the consequence of other operations being fast. It's often a tradeoff we're Dialogue: 0,0:06:14.00,0:06:16.00,Default,,0000,0000,0000,,willing to make. Dialogue: 0,0:06:16.00,0:06:20.00,Default,,0000,0000,0000,,On the editor rougher, we drove toward getting all the operations to be Dialogue: 0,0:06:20.00,0:06:23.00,Default,,0000,0000,0000,,fast. In an ideal world, that's certainly the best place to be, but Dialogue: 0,0:06:23.00,0:06:26.00,Default,,0000,0000,0000,,it's also a matter at what cost Dialogue: 0,0:06:26.00,0:06:29.00,Default,,0000,0000,0000,,in terms of code complexity and memory used Dialogue: 0,0:06:29.00,0:06:33.00,Default,,0000,0000,0000,,and effort put into it. It may be that we're willing to tolerate some operations Dialogue: 0,0:06:33.00,0:06:34.00,Default,,0000,0000,0000,,being less efficient Dialogue: 0,0:06:34.00,0:06:39.00,Default,,0000,0000,0000,,as long as the most commonly used ones are very streamlined. Dialogue: 0,0:06:39.00,0:06:42.00,Default,,0000,0000,0000,,We talked about these worst cases and degenerates about Dialogue: 0,0:06:42.00,0:06:45.00,Default,,0000,0000,0000,,knowing when we can expect our algorithms to degrade and whether we Dialogue: 0,0:06:45.00,0:06:47.00,Default,,0000,0000,0000,,want to do something about that Dialogue: 0,0:06:47.00,0:06:50.00,Default,,0000,0000,0000,,or choose a different algorithm or provide some Dialogue: 0,0:06:50.00,0:06:54.00,Default,,0000,0000,0000,,protection against those kind of cases coming through. To a lesser Dialogue: 0,0:06:54.00,0:06:58.00,Default,,0000,0000,0000,,extent, we already talked about memory used, how much overhead Dialogue: 0,0:06:58.00,0:07:01.00,Default,,0000,0000,0000,,there is. Seeing that we went to a pointer-based Linklis structure, we added Dialogue: 0,0:07:01.00,0:07:03.00,Default,,0000,0000,0000,,the four byte overhead Dialogue: 0,0:07:03.00,0:07:06.00,Default,,0000,0000,0000,,for every element. We went to an eight byte overhead once we got minor Dialogue: 0,0:07:06.00,0:07:10.00,Default,,0000,0000,0000,,[inaudible] and maybe even a little bit more if we had balance factors included. Dialogue: 0,0:07:10.00,0:07:13.00,Default,,0000,0000,0000,,Those things ride along with our data, Dialogue: 0,0:07:13.00,0:07:17.00,Default,,0000,0000,0000,,increasing the size and the memory footprint of it. Dialogue: 0,0:07:17.00,0:07:18.00,Default,,0000,0000,0000,,So there's a certain amount of Dialogue: 0,0:07:18.00,0:07:21.00,Default,,0000,0000,0000,,overhead built into this system. There's also this notion of excess capacity. To what Dialogue: 0,0:07:21.00,0:07:24.00,Default,,0000,0000,0000,,extent do we over allocate our Dialogue: 0,0:07:24.00,0:07:27.00,Default,,0000,0000,0000,,data structures early, planning for future growth. In some senses, save Dialogue: 0,0:07:27.00,0:07:32.00,Default,,0000,0000,0000,,ourselves that trouble of enlarging on demand. It's preparing for Dialogue: 0,0:07:32.00,0:07:33.00,Default,,0000,0000,0000,, Dialogue: 0,0:07:33.00,0:07:34.00,Default,,0000,0000,0000,,a large Dialogue: 0,0:07:34.00,0:07:36.00,Default,,0000,0000,0000,,allotment and then using it up when we find it. Dialogue: 0,0:07:36.00,0:07:39.00,Default,,0000,0000,0000,,Then when we do exceed that capacity, having you do it again. So where Dialogue: 0,0:07:39.00,0:07:42.00,Default,,0000,0000,0000,,do we make those tradeoffs about how much excess capacity and when to do Dialogue: 0,0:07:42.00,0:07:44.00,Default,,0000,0000,0000,,the enlarging? Dialogue: 0,0:07:44.00,0:07:48.00,Default,,0000,0000,0000,,It has a lot to do with what our general memory constraints are. Dialogue: 0,0:07:48.00,0:07:51.00,Default,,0000,0000,0000,,I would say that memory has gotten to be quite Dialogue: 0,0:07:51.00,0:07:53.00,Default,,0000,0000,0000,,free Dialogue: 0,0:07:53.00,0:07:56.00,Default,,0000,0000,0000,,in recent processors and Dialogue: 0,0:07:56.00,0:07:58.00,Default,,0000,0000,0000,,computer systems. You don't really think about Dialogue: 0,0:07:58.00,0:08:01.00,Default,,0000,0000,0000,,100 bytes here, 200 bytes there, 1,000 bytes there. Even Dialogue: 0,0:08:01.00,0:08:05.00,Default,,0000,0000,0000,,megabytes, you can talk about as thought it's a drop in the bucket. Dialogue: 0,0:08:05.00,0:08:06.00,Default,,0000,0000,0000,, Dialogue: 0,0:08:06.00,0:08:09.00,Default,,0000,0000,0000,,So this is something that isn't given as much weight Dialogue: 0,0:08:09.00,0:08:12.00,Default,,0000,0000,0000,,nowadays as it was ten years ago when there were a lot more constraints. But with Dialogue: 0,0:08:12.00,0:08:14.00,Default,,0000,0000,0000,,the move for a lot more imbedded device programming, and looking the Dialogue: 0,0:08:14.00,0:08:16.00,Default,,0000,0000,0000,,iPhone or Dialogue: 0,0:08:16.00,0:08:19.00,Default,,0000,0000,0000,,cell phones or things like that where they don't have that same liberty Dialogue: 0,0:08:19.00,0:08:23.00,Default,,0000,0000,0000,,to be wanton about memory, it's come back to being a little more careful and keeping Dialogue: 0,0:08:23.00,0:08:25.00,Default,,0000,0000,0000,,an eye on it. Dialogue: 0,0:08:25.00,0:08:28.00,Default,,0000,0000,0000,,There's also and issue here which trades off a lot with Dialogue: 0,0:08:28.00,0:08:31.00,Default,,0000,0000,0000,,runtime, which is redundancy versus sharing. Having Dialogue: 0,0:08:31.00,0:08:33.00,Default,,0000,0000,0000,,two different ways to get at the same piece of data Dialogue: 0,0:08:33.00,0:08:38.00,Default,,0000,0000,0000,,often will provide you with quick access. For example, if you have a Dialogue: 0,0:08:38.00,0:08:42.00,Default,,0000,0000,0000,,card catalogue for a library where you can look up by author, you can look up by title, you Dialogue: 0,0:08:42.00,0:08:44.00,Default,,0000,0000,0000,,probably are maintaining two data structures. Dialogue: 0,0:08:44.00,0:08:46.00,Default,,0000,0000,0000,,One that manipulates them, Dialogue: 0,0:08:46.00,0:08:49.00,Default,,0000,0000,0000,,sorted by title, one that manipulates them sorted by author. They're both kind Dialogue: 0,0:08:49.00,0:08:52.00,Default,,0000,0000,0000,,of looking at the same books in the end. Dialogue: 0,0:08:52.00,0:08:55.00,Default,,0000,0000,0000,,So maybe there's this set of pointers in one map over here, Dialogue: 0,0:08:55.00,0:08:58.00,Default,,0000,0000,0000,,indexed by author, another Dialogue: 0,0:08:58.00,0:09:00.00,Default,,0000,0000,0000,,keyed by title over there. Dialogue: 0,0:09:00.00,0:09:03.00,Default,,0000,0000,0000,,That means that I'm repeating all my data. Dialogue: 0,0:09:03.00,0:09:06.00,Default,,0000,0000,0000,,Hopefully I'm sharing it with a pointer, so I'm not actually really repeating all the Dialogue: 0,0:09:06.00,0:09:10.00,Default,,0000,0000,0000,,data, but I actually have two pointers or potentially two or more Dialogue: 0,0:09:10.00,0:09:11.00,Default,,0000,0000,0000,,pointers to the same book, Dialogue: 0,0:09:11.00,0:09:15.00,Default,,0000,0000,0000,,depending on the different ways you can get to it. That gives me that fast Dialogue: 0,0:09:15.00,0:09:17.00,Default,,0000,0000,0000,,access. I want to know all the books written by Leo Dialogue: 0,0:09:17.00,0:09:22.00,Default,,0000,0000,0000,,Lionni, I can find them easily, as well as finding all the books that have King in the Dialogue: 0,0:09:22.00,0:09:26.00,Default,,0000,0000,0000,,title. I don't have to do searches on a data set that's been optimized for only Dialogue: 0,0:09:26.00,0:09:27.00,Default,,0000,0000,0000,,one Dialogue: 0,0:09:27.00,0:09:28.00,Default,,0000,0000,0000,,access. Definitely, Dialogue: 0,0:09:28.00,0:09:32.00,Default,,0000,0000,0000,,tradeoffs were more space thrown at it to get at that fast access for Dialogue: 0,0:09:32.00,0:09:34.00,Default,,0000,0000,0000,,different ways. Dialogue: 0,0:09:34.00,0:09:40.00,Default,,0000,0000,0000,,Then this last one is one that I had mentioned along the way, but I think it's one that's easy to overlook, Dialogue: 0,0:09:40.00,0:09:42.00,Default,,0000,0000,0000,,which is to get very excited about how fast you can make it, how small you can Dialogue: 0,0:09:42.00,0:09:43.00,Default,,0000,0000,0000,,make it, Dialogue: 0,0:09:43.00,0:09:46.00,Default,,0000,0000,0000,,how fancy it is. It Dialogue: 0,0:09:46.00,0:09:50.00,Default,,0000,0000,0000,,has a real downside in terms of how hard it was to Dialogue: 0,0:09:50.00,0:09:53.00,Default,,0000,0000,0000,,write. Typically, when you go to these fancier strategies Dialogue: 0,0:09:53.00,0:09:54.00,Default,,0000,0000,0000,,that are Dialogue: 0,0:09:54.00,0:09:58.00,Default,,0000,0000,0000,,space efficient and time efficient, you had to pay for it somewhere. Dialogue: 0,0:09:58.00,0:10:01.00,Default,,0000,0000,0000,,It wasn't for free that the easy, obvious code would do that. It tends to Dialogue: 0,0:10:01.00,0:10:05.00,Default,,0000,0000,0000,,actually be complicated code that may use bid operations, that probably uses Dialogue: 0,0:10:05.00,0:10:06.00,Default,,0000,0000,0000,,more pointers Dialogue: 0,0:10:06.00,0:10:10.00,Default,,0000,0000,0000,,that has kind of a density to it that means it's going to take you longer to get it Dialogue: 0,0:10:10.00,0:10:12.00,Default,,0000,0000,0000,,right. It's going to take you more time to debug it. It's going to be more likely to Dialogue: 0,0:10:12.00,0:10:15.00,Default,,0000,0000,0000,,have lurking bugs. It's going to be harder to maintain. Dialogue: 0,0:10:15.00,0:10:18.00,Default,,0000,0000,0000,,If somebody comes along and wants to add a new operation, Dialogue: 0,0:10:18.00,0:10:21.00,Default,,0000,0000,0000,,they open up your code, and they're frightened away. It might be that that Dialogue: 0,0:10:21.00,0:10:23.00,Default,,0000,0000,0000,,code will never get Dialogue: 0,0:10:23.00,0:10:25.00,Default,,0000,0000,0000,,moved forward. Everybody will just open it Dialogue: 0,0:10:25.00,0:10:29.00,Default,,0000,0000,0000,,and close it immediately and say, whatever. We'll make it work the way it is, Dialogue: 0,0:10:29.00,0:10:33.00,Default,,0000,0000,0000,,rather than trying to improve it or move it forward because it actually is kind of scary Dialogue: 0,0:10:33.00,0:10:34.00,Default,,0000,0000,0000,,to look at. Dialogue: 0,0:10:34.00,0:10:35.00,Default,,0000,0000,0000,,So thinking about Dialogue: 0,0:10:35.00,0:10:37.00,Default,,0000,0000,0000,,what's the simplest thing that could work. Dialogue: 0,0:10:37.00,0:10:40.00,Default,,0000,0000,0000,,There's this movement that I think is pretty neat to think about. Dialogue: 0,0:10:40.00,0:10:43.00,Default,,0000,0000,0000,,There's this idea of the agile programming methodology. Dialogue: 0,0:10:43.00,0:10:44.00,Default,,0000,0000,0000,, Dialogue: 0,0:10:44.00,0:10:45.00,Default,,0000,0000,0000,,It's based on the idea that Dialogue: 0,0:10:45.00,0:10:49.00,Default,,0000,0000,0000,,rather than planning for building the most super stellar Dialogue: 0,0:10:49.00,0:10:51.00,Default,,0000,0000,0000,,infrastructure for solving all the worlds problems. You're about to write a chess Dialogue: 0,0:10:51.00,0:10:53.00,Default,,0000,0000,0000,,program. Dialogue: 0,0:10:53.00,0:10:55.00,Default,,0000,0000,0000,,Actually, something that's even simpler. You're going to write a checkers program. You say, Dialogue: 0,0:10:55.00,0:10:59.00,Default,,0000,0000,0000,,I'm going to sit down, and I'm going to design the pieces and the board. Then you think, hey, Dialogue: 0,0:10:59.00,0:11:02.00,Default,,0000,0000,0000,,checkers is just one embodiment of this. Why don't I try to make the Dialogue: 0,0:11:02.00,0:11:07.00,Default,,0000,0000,0000,,uber board that can be used for strategic conquest or for chess or Chinese Dialogue: 0,0:11:07.00,0:11:11.00,Default,,0000,0000,0000,,checkers. You could have these hexagonal things. You start building this crazy Dialogue: 0,0:11:11.00,0:11:12.00,Default,,0000,0000,0000,,infrastructure that Dialogue: 0,0:11:12.00,0:11:15.00,Default,,0000,0000,0000,,could handle all of these cases equally well, even though all you really needed Dialogue: 0,0:11:15.00,0:11:18.00,Default,,0000,0000,0000,,was checkers, a very simple, 2D grid. Dialogue: 0,0:11:18.00,0:11:19.00,Default,,0000,0000,0000,,But you imagine Dialogue: 0,0:11:19.00,0:11:23.00,Default,,0000,0000,0000,,the future needs way in advance of having them, and then you design something Dialogue: 0,0:11:23.00,0:11:26.00,Default,,0000,0000,0000,,overly complicated. Then what happens is you get bogged out of that. Dialogue: 0,0:11:26.00,0:11:28.00,Default,,0000,0000,0000,,It never happens, and the project dies. Dialogue: 0,0:11:28.00,0:11:29.00,Default,,0000,0000,0000,,You Dialogue: 0,0:11:29.00,0:11:31.00,Default,,0000,0000,0000,,lead a lonely life Dialogue: 0,0:11:31.00,0:11:35.00,Default,,0000,0000,0000,,by yourself, eating oatmeal. Dialogue: 0,0:11:35.00,0:11:37.00,Default,,0000,0000,0000,,I like Dialogue: 0,0:11:37.00,0:11:39.00,Default,,0000,0000,0000,,oatmeal. So one of the mottos is Dialogue: 0,0:11:39.00,0:11:42.00,Default,,0000,0000,0000,,design the simplest thing that could possibly work. Dialogue: 0,0:11:42.00,0:11:46.00,Default,,0000,0000,0000,,I think that's a neat gift to yourself to realize that Dialogue: 0,0:11:46.00,0:11:48.00,Default,,0000,0000,0000,,this simplest thing that could possibly work, that meets the needs that Dialogue: 0,0:11:48.00,0:11:52.00,Default,,0000,0000,0000,,you have, that has a decent enough [inaudible] and memory constraint right there. Dialogue: 0,0:11:52.00,0:11:54.00,Default,,0000,0000,0000,,Meets your needs in the simplest form of that. Dialogue: 0,0:11:54.00,0:11:57.00,Default,,0000,0000,0000,,It's going to be the easiest thing to get working and running. If you later decide you want to Dialogue: 0,0:11:57.00,0:11:58.00,Default,,0000,0000,0000,,go fancy, Dialogue: 0,0:11:58.00,0:12:01.00,Default,,0000,0000,0000,,you can swap it out Dialogue: 0,0:12:01.00,0:12:06.00,Default,,0000,0000,0000,,using the principles of distraction and [inaudible]. It should be that it's independent Dialogue: 0,0:12:06.00,0:12:10.00,Default,,0000,0000,0000,,when you decide you need that fancier thing. I've got a Dialogue: 0,0:12:10.00,0:12:13.00,Default,,0000,0000,0000,,couple questions here because I thought this would just help us frame a little Dialogue: 0,0:12:13.00,0:12:14.00,Default,,0000,0000,0000,,bit of thinking about these things. Dialogue: 0,0:12:14.00,0:12:17.00,Default,,0000,0000,0000,,These are questions that I'm hoping you can answer for me. That's why I Dialogue: 0,0:12:17.00,0:12:18.00,Default,,0000,0000,0000,,brought Dialogue: 0,0:12:18.00,0:12:22.00,Default,,0000,0000,0000,,cup full of candy. I'm prepared to offer bribery for people who help Dialogue: 0,0:12:22.00,0:12:24.00,Default,,0000,0000,0000,,me answer these questions. Dialogue: 0,0:12:24.00,0:12:26.00,Default,,0000,0000,0000,,So let's talk about array Dialogue: 0,0:12:26.00,0:12:28.00,Default,,0000,0000,0000,,versus vector. Dialogue: 0,0:12:28.00,0:12:31.00,Default,,0000,0000,0000,,So the sequels [inaudible] builds and Dialogue: 0,0:12:31.00,0:12:35.00,Default,,0000,0000,0000,,array is what is behind the scenes of a vector. Then the vector adds Dialogue: 0,0:12:35.00,0:12:38.00,Default,,0000,0000,0000,,convenience on the outside of it. Dialogue: 0,0:12:38.00,0:12:40.00,Default,,0000,0000,0000,,Early on, I had said, once I tell Dialogue: 0,0:12:40.00,0:12:43.00,Default,,0000,0000,0000,,you about arrays, Dialogue: 0,0:12:43.00,0:12:46.00,Default,,0000,0000,0000,,put that back in your memory, and just use vector instead because everything array Dialogue: 0,0:12:46.00,0:12:48.00,Default,,0000,0000,0000,,does, vector does Dialogue: 0,0:12:48.00,0:12:53.00,Default,,0000,0000,0000,,nicely and cleanly and adds all sorts of features. Somebody give me a list Dialogue: 0,0:12:53.00,0:12:55.00,Default,,0000,0000,0000,,of things that vector does much better than Dialogue: 0,0:12:55.00,0:12:58.00,Default,,0000,0000,0000,,array. Dialogue: 0,0:12:58.00,0:12:59.00,Default,,0000,0000,0000,,Way in the back. Bounce Dialogue: 0,0:12:59.00,0:13:00.00,Default,,0000,0000,0000,,checking. Dialogue: 0,0:13:00.00,0:13:03.00,Default,,0000,0000,0000,,Bounce checking. What else? Come on. A Dialogue: 0,0:13:03.00,0:13:06.00,Default,,0000,0000,0000,,blow pop is on the line. Dialogue: 0,0:13:06.00,0:13:09.00,Default,,0000,0000,0000,,I need to interrupt your - help us Dialogue: 0,0:13:09.00,0:13:10.00,Default,,0000,0000,0000,,out. Dialogue: 0,0:13:10.00,0:13:11.00,Default,,0000,0000,0000,,You've got bounce checking. What Dialogue: 0,0:13:11.00,0:13:14.00,Default,,0000,0000,0000,,else? More? I want more. You've got nothing else for Dialogue: 0,0:13:14.00,0:13:17.00,Default,,0000,0000,0000,,me? I don't even want a blow pop. You don't want Dialogue: 0,0:13:17.00,0:13:21.00,Default,,0000,0000,0000,,a blow Dialogue: 0,0:13:21.00,0:13:23.00,Default,,0000,0000,0000,,pop? All right. I'm going to give your blow pop to somebody else. Right Dialogue: 0,0:13:23.00,0:13:27.00,Default,,0000,0000,0000,,here. I'm going to give the blow pop to you. Tell me what makes vector good. It has operations that Dialogue: 0,0:13:27.00,0:13:27.00,Default,,0000,0000,0000,,shuffle Dialogue: 0,0:13:27.00,0:13:31.00,Default,,0000,0000,0000,,elements for you. Yeah, it does the insert, delete, moving stuff down. Dialogue: 0,0:13:31.00,0:13:32.00,Default,,0000,0000,0000,,Also, it does the growing. Dialogue: 0,0:13:32.00,0:13:34.00,Default,,0000,0000,0000,,You keep adding, and it just grows. [Inaudible] don't do that. You Dialogue: 0,0:13:34.00,0:13:37.00,Default,,0000,0000,0000,,want a [inaudible] to grow, you grow it. Dialogue: 0,0:13:37.00,0:13:40.00,Default,,0000,0000,0000,,You take the pointer, you copy stuff over, you delete the old one, you Dialogue: 0,0:13:40.00,0:13:43.00,Default,,0000,0000,0000,,rearrange things. You do all the work. So Dialogue: 0,0:13:43.00,0:13:44.00,Default,,0000,0000,0000,,vector buys you kind of Dialogue: 0,0:13:44.00,0:13:46.00,Default,,0000,0000,0000,,array with benefits. Dialogue: 0,0:13:46.00,0:13:48.00,Default,,0000,0000,0000,,So it seems like, then, Dialogue: 0,0:13:48.00,0:13:50.00,Default,,0000,0000,0000,,you could kind of take away - the naive point would be like, well, Dialogue: 0,0:13:50.00,0:13:53.00,Default,,0000,0000,0000,,just use vector. Always use vector. Dialogue: 0,0:13:53.00,0:13:56.00,Default,,0000,0000,0000,,Vector's always better than array. Is there ever a situation where array still Dialogue: 0,0:13:56.00,0:13:57.00,Default,,0000,0000,0000,,is a pretty valid choice? Dialogue: 0,0:13:57.00,0:14:00.00,Default,,0000,0000,0000,,What is it array has that vector maybe doesn't? Dialogue: 0,0:14:00.00,0:14:05.00,Default,,0000,0000,0000,,Well, when you add things dynamically to the vector, it actually doubles the size [inaudible] Dialogue: 0,0:14:05.00,0:14:06.00,Default,,0000,0000,0000,,increasing it by one. If you know Dialogue: 0,0:14:06.00,0:14:10.00,Default,,0000,0000,0000,,the exact size, and you know it's not going to change, you're using [inaudible]. That's it exactly. Dialogue: 0,0:14:10.00,0:14:14.00,Default,,0000,0000,0000,,One of its big advantages. If you know you only have Dialogue: 0,0:14:14.00,0:14:17.00,Default,,0000,0000,0000,,- let's say you have a very small array Dialogue: 0,0:14:17.00,0:14:21.00,Default,,0000,0000,0000,,planned for. The one on the practice exam was, if you're doing a calendar Dialogue: 0,0:14:21.00,0:14:23.00,Default,,0000,0000,0000,,where you had 365 days in a year, Dialogue: 0,0:14:23.00,0:14:26.00,Default,,0000,0000,0000,,and you're keeping track of the events on a particular day, you know Dialogue: 0,0:14:26.00,0:14:30.00,Default,,0000,0000,0000,,how many days in the year. There's never going to be any change in that. Well, leap Dialogue: 0,0:14:30.00,0:14:31.00,Default,,0000,0000,0000,, Dialogue: 0,0:14:31.00,0:14:33.00,Default,,0000,0000,0000,,year. Dialogue: 0,0:14:33.00,0:14:36.00,Default,,0000,0000,0000,,But you know that, and you know that in advance. So why fuss with a data structure that does all Dialogue: 0,0:14:36.00,0:14:39.00,Default,,0000,0000,0000,,this growing and shrinking and has some overhead associated with that Dialogue: 0,0:14:39.00,0:14:43.00,Default,,0000,0000,0000,,when, in fact, you know there's exactly this number. That's all you need. Dialogue: 0,0:14:43.00,0:14:46.00,Default,,0000,0000,0000,,In fact, it's almost a little bit more convenient to set up. You can Dialogue: 0,0:14:46.00,0:14:48.00,Default,,0000,0000,0000,,just declare it that size, and it's ready to go. With Dialogue: 0,0:14:48.00,0:14:52.00,Default,,0000,0000,0000,,the vector, you have to go through and add all the elements and stuff like that. Dialogue: 0,0:14:52.00,0:14:54.00,Default,,0000,0000,0000,,So there are a few situations where you might just say, Dialogue: 0,0:14:54.00,0:14:57.00,Default,,0000,0000,0000,,I don't need the advantages. Dialogue: 0,0:14:57.00,0:15:00.00,Default,,0000,0000,0000,,It adds some overhead that I don't want to pay, Dialogue: 0,0:15:00.00,0:15:04.00,Default,,0000,0000,0000,,and I'm perfectly happy making it a small fixed Dialogue: 0,0:15:04.00,0:15:07.00,Default,,0000,0000,0000,,array. You'll still lose bounce checking, Dialogue: 0,0:15:07.00,0:15:08.00,Default,,0000,0000,0000,,but Dialogue: 0,0:15:08.00,0:15:11.00,Default,,0000,0000,0000,,if you are being careful, maybe you're Dialogue: 0,0:15:11.00,0:15:12.00,Default,,0000,0000,0000,,comfortable with Dialogue: 0,0:15:12.00,0:15:15.00,Default,,0000,0000,0000,,making that tradeoff. By losing bounce checking, you actually are getting a little bit Dialogue: 0,0:15:15.00,0:15:18.00,Default,,0000,0000,0000,,of the speed improvement back. The bounce check does actually cost you Dialogue: 0,0:15:18.00,0:15:20.00,Default,,0000,0000,0000,,a little bit on every Dialogue: 0,0:15:20.00,0:15:23.00,Default,,0000,0000,0000,,vector access that an array would not actually pay. Dialogue: 0,0:15:23.00,0:15:26.00,Default,,0000,0000,0000,,That's really in the noise for most programs. I hesitate to Dialogue: 0,0:15:26.00,0:15:28.00,Default,,0000,0000,0000,,even mention it, to get you to think it matters, Dialogue: 0,0:15:28.00,0:15:31.00,Default,,0000,0000,0000,,but it is part of the thinking of a Dialogue: 0,0:15:31.00,0:15:34.00,Default,,0000,0000,0000,,professional program. Sometimes that may be the thing it comes down to, Dialogue: 0,0:15:34.00,0:15:36.00,Default,,0000,0000,0000,, Dialogue: 0,0:15:36.00,0:15:37.00,Default,,0000,0000,0000,,making your operation Dialogue: 0,0:15:37.00,0:15:41.00,Default,,0000,0000,0000,,constant factors streamline enough for the operation you need. So I put here Dialogue: 0,0:15:41.00,0:15:44.00,Default,,0000,0000,0000,,stack and queue versus vector. Dialogue: 0,0:15:44.00,0:15:48.00,Default,,0000,0000,0000,,Given that stack and queue are really just vectors in disguise, and they're Dialogue: 0,0:15:48.00,0:15:50.00,Default,,0000,0000,0000,,vectors with less features, vectors Dialogue: 0,0:15:50.00,0:15:53.00,Default,,0000,0000,0000,,that can't do as much. Dialogue: 0,0:15:53.00,0:15:55.00,Default,,0000,0000,0000,,One of the implementations for stack and vector Dialogue: 0,0:15:55.00,0:15:58.00,Default,,0000,0000,0000,,could easily be just layered on top of a vector. Dialogue: 0,0:15:58.00,0:16:02.00,Default,,0000,0000,0000,,Why is it good to take away things? Dialogue: 0,0:16:02.00,0:16:06.00,Default,,0000,0000,0000,,[Inaudible] Dialogue: 0,0:16:06.00,0:16:08.00,Default,,0000,0000,0000,,tampering with contents of [inaudible]. Yeah. So it's enforcing discipline Dialogue: 0,0:16:08.00,0:16:11.00,Default,,0000,0000,0000,,on how you use it. Stacks are Dialogue: 0,0:16:11.00,0:16:12.00,Default,,0000,0000,0000,, Dialogue: 0,0:16:12.00,0:16:14.00,Default,,0000,0000,0000,,lifo, queues are fifo. Dialogue: 0,0:16:14.00,0:16:15.00,Default,,0000,0000,0000,,The way things go out, they way they go out Dialogue: 0,0:16:15.00,0:16:17.00,Default,,0000,0000,0000,,are very Dialogue: 0,0:16:17.00,0:16:19.00,Default,,0000,0000,0000,,rigid. By using stack and queue, Dialogue: 0,0:16:19.00,0:16:22.00,Default,,0000,0000,0000,,you are guaranteeing that you won't go in and accidentally put something at the head Dialogue: 0,0:16:22.00,0:16:25.00,Default,,0000,0000,0000,,of the line or remove something out of the middle of the stack because you just don't Dialogue: 0,0:16:25.00,0:16:26.00,Default,,0000,0000,0000,,have access to that. Dialogue: 0,0:16:26.00,0:16:27.00,Default,,0000,0000,0000,,It's been tidied up and Dialogue: 0,0:16:27.00,0:16:29.00,Default,,0000,0000,0000,,packaged up into stack, which has push and pop. Dialogue: 0,0:16:29.00,0:16:31.00,Default,,0000,0000,0000,,queue, which has MQDQ. Dialogue: 0,0:16:31.00,0:16:34.00,Default,,0000,0000,0000,,No other access implied or given, Dialogue: 0,0:16:34.00,0:16:37.00,Default,,0000,0000,0000,,totally encapsulated from you. So in fact, it allows you to Dialogue: 0,0:16:37.00,0:16:39.00,Default,,0000,0000,0000,,maintain on a discipline Dialogue: 0,0:16:39.00,0:16:45.00,Default,,0000,0000,0000,,that otherwise the vector didn't strongly provide for you. Question? [Inaudible]. Another Dialogue: 0,0:16:45.00,0:16:48.00,Default,,0000,0000,0000,,thing you could do is you could optimize a stack or a Dialogue: 0,0:16:48.00,0:16:51.00,Default,,0000,0000,0000,,queue to be very good at the only active things you're doing, which Dialogue: 0,0:16:51.00,0:16:55.00,Default,,0000,0000,0000,,is pushing and popping or RQDQ. I think that's worth a smartie, don't you? Dialogue: 0,0:16:55.00,0:16:57.00,Default,,0000,0000,0000,,I think that is. Dialogue: 0,0:16:57.00,0:16:58.00,Default,,0000,0000,0000,,Exactly. Dialogue: 0,0:16:58.00,0:17:02.00,Default,,0000,0000,0000,,So by restricting what you have available, Dialogue: 0,0:17:02.00,0:17:05.00,Default,,0000,0000,0000,,it actually gives you choices in the implementation that wouldn't have worked out as well, [inaudible] full array Dialogue: 0,0:17:05.00,0:17:08.00,Default,,0000,0000,0000,,of operations. It's exactly true. Stack and queue only adding from one end Dialogue: 0,0:17:08.00,0:17:11.00,Default,,0000,0000,0000,,mean that things like a Linklis, which isn't a good choice for implementing the Dialogue: 0,0:17:11.00,0:17:13.00,Default,,0000,0000,0000,,general case of vector, Dialogue: 0,0:17:13.00,0:17:17.00,Default,,0000,0000,0000,,are perfectly good choices for the stack and queue case. So giving ourselves Dialogue: 0,0:17:17.00,0:17:22.00,Default,,0000,0000,0000,,some freedom as the implementer. So information about how it's being used Dialogue: 0,0:17:22.00,0:17:24.00,Default,,0000,0000,0000,,can pay off. It also Dialogue: 0,0:17:24.00,0:17:25.00,Default,,0000,0000,0000,,means when you read code - if you see Dialogue: 0,0:17:25.00,0:17:27.00,Default,,0000,0000,0000,,code that's using something, call the stack Dialogue: 0,0:17:27.00,0:17:31.00,Default,,0000,0000,0000,,or using a queue, you immediately know how it works. You could Dialogue: 0,0:17:31.00,0:17:34.00,Default,,0000,0000,0000,,say, here's this search that's actually stuffing a bunch of things into Dialogue: 0,0:17:34.00,0:17:37.00,Default,,0000,0000,0000,,a stack. I know they're last and first [inaudible]. Dialogue: 0,0:17:37.00,0:17:39.00,Default,,0000,0000,0000,,If you see them using a vector, Dialogue: 0,0:17:39.00,0:17:42.00,Default,,0000,0000,0000,,you have to verify where they put them in the vector. Where do Dialogue: 0,0:17:42.00,0:17:46.00,Default,,0000,0000,0000,,they pull them out? The code doesn't tell you the same things. It doesn't tell you the same story Dialogue: 0,0:17:46.00,0:17:49.00,Default,,0000,0000,0000,,as it does when you see a word that has a strong meaning to it, like Dialogue: 0,0:17:49.00,0:17:52.00,Default,,0000,0000,0000,,stack and queue. Dialogue: 0,0:17:52.00,0:17:55.00,Default,,0000,0000,0000,,Generally, these [inaudible] to make about sorting things or not sorting things. We spent a Dialogue: 0,0:17:55.00,0:17:57.00,Default,,0000,0000,0000,,long time talking about sorting Dialogue: 0,0:17:57.00,0:18:01.00,Default,,0000,0000,0000,,and how various algorithms approach the sorting problem and what Dialogue: 0,0:18:01.00,0:18:02.00,Default,,0000,0000,0000,,they come up with. Dialogue: 0,0:18:02.00,0:18:05.00,Default,,0000,0000,0000,,I have a question here. What sorting algorithm is best? Is Dialogue: 0,0:18:05.00,0:18:09.00,Default,,0000,0000,0000,,there an Dialogue: 0,0:18:09.00,0:18:12.00,Default,,0000,0000,0000,,answer to that question? Why would I ask a question that has no answer? It depends on what you expect it Dialogue: 0,0:18:12.00,0:18:16.00,Default,,0000,0000,0000,,to be giving you. It depends. That's a great thing. It depends on Dialogue: 0,0:18:16.00,0:18:18.00,Default,,0000,0000,0000,,what you expect it to give you. How big is it? Dialogue: 0,0:18:18.00,0:18:21.00,Default,,0000,0000,0000,,What are the contents of it? Is it random? Is it sorted? Is it almost Dialogue: 0,0:18:21.00,0:18:24.00,Default,,0000,0000,0000,,sorted? Is it reverse sorted? Is it Dialogue: 0,0:18:24.00,0:18:28.00,Default,,0000,0000,0000,,drawn from a range of one to 1,000 values, or is it drawn from one to three Dialogue: 0,0:18:28.00,0:18:31.00,Default,,0000,0000,0000,,values? Huge array that has just one, two, three in it Dialogue: 0,0:18:31.00,0:18:34.00,Default,,0000,0000,0000,,might necessitate a different approach than one that has Dialogue: 0,0:18:34.00,0:18:36.00,Default,,0000,0000,0000,,one to max sine in it. Dialogue: 0,0:18:36.00,0:18:37.00,Default,,0000,0000,0000,,So Dialogue: 0,0:18:37.00,0:18:39.00,Default,,0000,0000,0000,,there is no answer to that. It is depends. What do you know? If you don't Dialogue: 0,0:18:39.00,0:18:41.00,Default,,0000,0000,0000,,know anything, give Dialogue: 0,0:18:41.00,0:18:43.00,Default,,0000,0000,0000,,it to someone else. Dialogue: 0,0:18:43.00,0:18:45.00,Default,,0000,0000,0000,, Dialogue: 0,0:18:45.00,0:18:49.00,Default,,0000,0000,0000,,If you don't know, there's certain things that perform well. You know in the Dialogue: 0,0:18:49.00,0:18:52.00,Default,,0000,0000,0000,,average case, you don't have degenerate behaviors. For example, [inaudible] is a Dialogue: 0,0:18:52.00,0:18:56.00,Default,,0000,0000,0000,,great sort for the general case of an N log N that doesn't use any space Dialogue: 0,0:18:56.00,0:18:56.00,Default,,0000,0000,0000,, Dialogue: 0,0:18:56.00,0:19:01.00,Default,,0000,0000,0000,,or any extra space the way word sort does. It doesn't have any degenerate cases. Dialogue: 0,0:19:01.00,0:19:02.00,Default,,0000,0000,0000,,For an Dialogue: 0,0:19:02.00,0:19:05.00,Default,,0000,0000,0000,,unknown set of inputs, it works pretty well. Dialogue: 0,0:19:05.00,0:19:08.00,Default,,0000,0000,0000,,If you happen to have a little bit of data, it's almost sorted. Dialogue: 0,0:19:08.00,0:19:09.00,Default,,0000,0000,0000,, Dialogue: 0,0:19:09.00,0:19:10.00,Default,,0000,0000,0000,,Even Dialogue: 0,0:19:10.00,0:19:11.00,Default,,0000,0000,0000,,Barack Obama's Dialogue: 0,0:19:11.00,0:19:13.00,Default,,0000,0000,0000,,not favorite bubble sort Dialogue: 0,0:19:13.00,0:19:14.00,Default,,0000,0000,0000,,has a Dialogue: 0,0:19:14.00,0:19:17.00,Default,,0000,0000,0000,,chance of being in the run because it's already sorted. Is it worth sorting? Calculating the payoff, we had a problem on Dialogue: 0,0:19:17.00,0:19:20.00,Default,,0000,0000,0000,,one of the section Dialogue: 0,0:19:20.00,0:19:24.00,Default,,0000,0000,0000,,exercises once. I think it's a really good Dialogue: 0,0:19:24.00,0:19:25.00,Default,,0000,0000,0000,,one to Dialogue: 0,0:19:25.00,0:19:27.00,Default,,0000,0000,0000,,think through and revisit. This idea of Dialogue: 0,0:19:27.00,0:19:31.00,Default,,0000,0000,0000,,certain operations, many operations are much more Dialogue: 0,0:19:31.00,0:19:34.00,Default,,0000,0000,0000,,efficiently implemented if the data's sorted. Dialogue: 0,0:19:34.00,0:19:37.00,Default,,0000,0000,0000,,You can think of them off the top of your head. Oh, you want to have the minimum? If Dialogue: 0,0:19:37.00,0:19:41.00,Default,,0000,0000,0000,,it's sorted, it's very easy. You want the maximum? Very easy if it's sorted. You want to find the median. Dialogue: 0,0:19:41.00,0:19:43.00,Default,,0000,0000,0000,,Also very easy if it's sorted. You want to Dialogue: 0,0:19:43.00,0:19:44.00,Default,,0000,0000,0000,, Dialogue: 0,0:19:44.00,0:19:48.00,Default,,0000,0000,0000,,find duplicates. Once they're sorted, they're all lined up together. You want to find the Dialogue: 0,0:19:48.00,0:19:49.00,Default,,0000,0000,0000,,mode, which is the most Dialogue: 0,0:19:49.00,0:19:50.00,Default,,0000,0000,0000,,frequent element. Dialogue: 0,0:19:50.00,0:19:53.00,Default,,0000,0000,0000,,Also easier if it's sorted because they'll all be groups together in a run. So you Dialogue: 0,0:19:53.00,0:19:57.00,Default,,0000,0000,0000,,can do a linear pass, counting what you see to find the longest run. Dialogue: 0,0:19:57.00,0:20:00.00,Default,,0000,0000,0000,,If you had two arrays and you wanted to merge them or intersect them to find Dialogue: 0,0:20:00.00,0:20:04.00,Default,,0000,0000,0000,,their common elements, it's much easier if they're sorted. All these things Dialogue: 0,0:20:04.00,0:20:07.00,Default,,0000,0000,0000,,that are hard to do when the data's in Dialogue: 0,0:20:07.00,0:20:08.00,Default,,0000,0000,0000,,a random order Dialogue: 0,0:20:08.00,0:20:12.00,Default,,0000,0000,0000,,actually have much more streamlined algorithms once you invest in sorting it. Dialogue: 0,0:20:12.00,0:20:13.00,Default,,0000,0000,0000,,So there was a problem that was like, Dialogue: 0,0:20:13.00,0:20:15.00,Default,,0000,0000,0000,,how do you know it's worth doing that? Dialogue: 0,0:20:15.00,0:20:18.00,Default,,0000,0000,0000,,If you only plan on writing one merge, and Dialogue: 0,0:20:18.00,0:20:19.00,Default,,0000,0000,0000,,you could do it in N squared, Dialogue: 0,0:20:19.00,0:20:21.00,Default,,0000,0000,0000,,is it worth it to Dialogue: 0,0:20:21.00,0:20:24.00,Default,,0000,0000,0000,,sort it, N log N, so you can get an O out of merge? So it has a lot to do Dialogue: 0,0:20:24.00,0:20:26.00,Default,,0000,0000,0000,,with how often you plan on doing the merge. Dialogue: 0,0:20:26.00,0:20:29.00,Default,,0000,0000,0000,,How big is your data set? Dialogue: 0,0:20:29.00,0:20:30.00,Default,,0000,0000,0000,,What are your Dialogue: 0,0:20:30.00,0:20:32.00,Default,,0000,0000,0000,,constraints on the times there. It Dialogue: 0,0:20:32.00,0:20:35.00,Default,,0000,0000,0000,,is interesting to think about that relationship. It isn't for free, but Dialogue: 0,0:20:35.00,0:20:37.00,Default,,0000,0000,0000,, Dialogue: 0,0:20:37.00,0:20:41.00,Default,,0000,0000,0000,,potentially, it's an investment by sorting it so you can do a lot of fast searches Dialogue: 0,0:20:41.00,0:20:44.00,Default,,0000,0000,0000,,later. Dialogue: 0,0:20:44.00,0:20:47.00,Default,,0000,0000,0000,,This one actually is interesting because they actually solve a lot of the Dialogue: 0,0:20:47.00,0:20:50.00,Default,,0000,0000,0000,,same problems, and they differ in one small way. If you had a Dialogue: 0,0:20:50.00,0:20:51.00,Default,,0000,0000,0000,,set - Dialogue: 0,0:20:51.00,0:20:55.00,Default,,0000,0000,0000,,so set is being backed by a balance by a [inaudible] string that actually is a sorted data Dialogue: 0,0:20:55.00,0:20:56.00,Default,,0000,0000,0000,,structure internally - versus a Dialogue: 0,0:20:56.00,0:20:58.00,Default,,0000,0000,0000,,sorted vector. Dialogue: 0,0:20:58.00,0:21:03.00,Default,,0000,0000,0000,,So if your goal were to keep track of all the Dialogue: 0,0:21:03.00,0:21:07.00,Default,,0000,0000,0000,,students at Stanford, and you wanted to be able to look up people by name, Dialogue: 0,0:21:07.00,0:21:08.00,Default,,0000,0000,0000,, Dialogue: 0,0:21:08.00,0:21:11.00,Default,,0000,0000,0000,,then the contains operation of the set Dialogue: 0,0:21:11.00,0:21:15.00,Default,,0000,0000,0000,,is actually doing these minor ray Dialogue: 0,0:21:15.00,0:21:16.00,Default,,0000,0000,0000,,search on assorted vectors Dialogue: 0,0:21:16.00,0:21:18.00,Default,,0000,0000,0000,,using the same path, but working through a vector. Dialogue: 0,0:21:18.00,0:21:21.00,Default,,0000,0000,0000,,So we can make the searching operations, like contains Dialogue: 0,0:21:21.00,0:21:23.00,Default,,0000,0000,0000,, Dialogue: 0,0:21:23.00,0:21:24.00,Default,,0000,0000,0000,,and Dialogue: 0,0:21:24.00,0:21:26.00,Default,,0000,0000,0000,,other look-up based things, Dialogue: 0,0:21:26.00,0:21:29.00,Default,,0000,0000,0000,,algorithmic in both cases. Dialogue: 0,0:21:29.00,0:21:33.00,Default,,0000,0000,0000,,So what advantage - this sort Dialogue: 0,0:21:33.00,0:21:36.00,Default,,0000,0000,0000,,of vector, where I just used the interchangeably, is there something one Dialogue: 0,0:21:36.00,0:21:41.00,Default,,0000,0000,0000,,can do that the other can't or some advantage or disadvantage that's Dialogue: 0,0:21:41.00,0:21:43.00,Default,,0000,0000,0000,,assumed in that decision? Dialogue: 0,0:21:43.00,0:21:47.00,Default,,0000,0000,0000,,You don't have duplicates in a set, but you can have duplicates in your sorted vector. Yeah, Dialogue: 0,0:21:47.00,0:21:51.00,Default,,0000,0000,0000,,so the set has another concern with just how it operates. You can't put duplicates Dialogue: 0,0:21:51.00,0:21:54.00,Default,,0000,0000,0000,,in, so if you have two students with the same name, then Dialogue: 0,0:21:54.00,0:21:57.00,Default,,0000,0000,0000,,in the set, it turns out you're all coalesced down to one. Your transcripts all get Dialogue: 0,0:21:57.00,0:21:59.00,Default,,0000,0000,0000,,merged to your advantage or not. What Dialogue: 0,0:21:59.00,0:22:01.00,Default,,0000,0000,0000,,else Dialogue: 0,0:22:01.00,0:22:05.00,Default,,0000,0000,0000,,does set buy you that vector doesn't? How hard is it to Dialogue: 0,0:22:05.00,0:22:09.00,Default,,0000,0000,0000,,edit a sorted vector? You Dialogue: 0,0:22:09.00,0:22:11.00,Default,,0000,0000,0000,,want to put something new in there? Dialogue: 0,0:22:11.00,0:22:12.00,Default,,0000,0000,0000,,You're shuffling. You want to Dialogue: 0,0:22:12.00,0:22:13.00,Default,,0000,0000,0000,,take something out? You're shuffling. Dialogue: 0,0:22:13.00,0:22:18.00,Default,,0000,0000,0000,,The movement to the pointer-based structure there, the research Dialogue: 0,0:22:18.00,0:22:18.00,Default,,0000,0000,0000,,stream behind this, Dialogue: 0,0:22:18.00,0:22:21.00,Default,,0000,0000,0000,,is giving us this editability of the data structure. Dialogue: 0,0:22:21.00,0:22:25.00,Default,,0000,0000,0000,,The convenient logarithmic time to remove and add elements using the Dialogue: 0,0:22:25.00,0:22:28.00,Default,,0000,0000,0000,,pointer wiring to do that, Dialogue: 0,0:22:28.00,0:22:30.00,Default,,0000,0000,0000,,that vector doesn't have. That tradeoff Dialogue: 0,0:22:30.00,0:22:35.00,Default,,0000,0000,0000,,is actually one that Dialogue: 0,0:22:35.00,0:22:39.00,Default,,0000,0000,0000,,situation may be that you just don't do a lot of edits. That's actually a very common Dialogue: 0,0:22:39.00,0:22:42.00,Default,,0000,0000,0000,,situation. The sorted vector happens to be a very underutilized Dialogue: 0,0:22:42.00,0:22:45.00,Default,,0000,0000,0000,,or under appreciated arrangement Dialogue: 0,0:22:45.00,0:22:48.00,Default,,0000,0000,0000,,for data because for most things that are getting a lot of Dialogue: 0,0:22:48.00,0:22:49.00,Default,,0000,0000,0000,,edits, having a Dialogue: 0,0:22:49.00,0:22:53.00,Default,,0000,0000,0000,,linear time edit isn't going to be a painful Dialogue: 0,0:22:53.00,0:22:53.00,Default,,0000,0000,0000,,consequence. Dialogue: 0,0:22:53.00,0:22:56.00,Default,,0000,0000,0000,,You're doing a lot of searches, and you're getting the finer research there, Dialogue: 0,0:22:56.00,0:22:57.00,Default,,0000,0000,0000,,where you really care about it, Dialogue: 0,0:22:57.00,0:23:01.00,Default,,0000,0000,0000,,with no overhead. Very little overhead. A little bit of excess capacity, Dialogue: 0,0:23:01.00,0:23:03.00,Default,,0000,0000,0000,,but none of the pointer-based Dialogue: 0,0:23:03.00,0:23:06.00,Default,,0000,0000,0000,,trouble that came with the set. So the set actually adding onto that another eight Dialogue: 0,0:23:06.00,0:23:08.00,Default,,0000,0000,0000,,bytes, potentially even a little bit more, Dialogue: 0,0:23:08.00,0:23:12.00,Default,,0000,0000,0000,,of overhead on every element to give us that editability that maybe isn't Dialogue: 0,0:23:12.00,0:23:14.00,Default,,0000,0000,0000,,that important to us. Dialogue: 0,0:23:14.00,0:23:17.00,Default,,0000,0000,0000,,So if you're looking at that thing and saying, I'd like to be able to have Dialogue: 0,0:23:17.00,0:23:21.00,Default,,0000,0000,0000,,a sorted structure for both the set and the sorted vector, let you Dialogue: 0,0:23:21.00,0:23:24.00,Default,,0000,0000,0000,,access the elements in order. The interrater of the set goes in sort order, Dialogue: 0,0:23:24.00,0:23:27.00,Default,,0000,0000,0000,,going from zero to the end. The vector gives me order. Dialogue: 0,0:23:27.00,0:23:30.00,Default,,0000,0000,0000,,I can browse them in sort order. I can search them using sorted. Dialogue: 0,0:23:30.00,0:23:33.00,Default,,0000,0000,0000,,Where they differ is where does it take to edit one? Dialogue: 0,0:23:33.00,0:23:37.00,Default,,0000,0000,0000,,The one that invested more in the memory had faster Dialogue: 0,0:23:37.00,0:23:39.00,Default,,0000,0000,0000,, Dialogue: 0,0:23:39.00,0:23:44.00,Default,,0000,0000,0000,,editing. The P-queue. This is kind of interesting. The P-queue is also a sorted structure, but not quite. Dialogue: 0,0:23:44.00,0:23:46.00,Default,,0000,0000,0000,, Dialogue: 0,0:23:46.00,0:23:46.00,Default,,0000,0000,0000,, Dialogue: 0,0:23:46.00,0:23:48.00,Default,,0000,0000,0000,,It's a much more weakly Dialogue: 0,0:23:48.00,0:23:52.00,Default,,0000,0000,0000,,sorted structure. So if you're using the [inaudible] heap like we did on the Dialogue: 0,0:23:52.00,0:23:53.00,Default,,0000,0000,0000,,P-queue Dialogue: 0,0:23:53.00,0:23:55.00,Default,,0000,0000,0000,,[inaudible], it does give you this access to the maximum value, Dialogue: 0,0:23:55.00,0:23:59.00,Default,,0000,0000,0000,,and then kind of a quick reshuffling [inaudible] the next Dialogue: 0,0:23:59.00,0:24:00.00,Default,,0000,0000,0000,,and so on. Dialogue: 0,0:24:00.00,0:24:02.00,Default,,0000,0000,0000,,But it doesn't really give you the full range. For example, if you Dialogue: 0,0:24:02.00,0:24:10.00,Default,,0000,0000,0000,,were looking for the minimum in a P-queue, where is it? Dialogue: 0,0:24:10.00,0:24:11.00,Default,,0000,0000,0000,,It's somewhere in the Dialogue: 0,0:24:11.00,0:24:14.00,Default,,0000,0000,0000,,bottom. It's in the bottom-most level, but where across the bottom, Dialogue: 0,0:24:14.00,0:24:16.00,Default,,0000,0000,0000,,no knowledge, right? It could be Dialogue: 0,0:24:16.00,0:24:20.00,Default,,0000,0000,0000,,at any of the nodes that are at the bottom of the heap. So in fact it Dialogue: 0,0:24:20.00,0:24:21.00,Default,,0000,0000,0000,,gives you this access to Dialogue: 0,0:24:21.00,0:24:23.00,Default,,0000,0000,0000,,a partial Dialogue: 0,0:24:23.00,0:24:26.00,Default,,0000,0000,0000,,ordering of the data. In this case, it's relative Dialogue: 0,0:24:26.00,0:24:28.00,Default,,0000,0000,0000,,to the prioritization, but not Dialogue: 0,0:24:28.00,0:24:31.00,Default,,0000,0000,0000,,the fluid form of sorting the way a vector is. For example, Dialogue: 0,0:24:31.00,0:24:33.00,Default,,0000,0000,0000,,if P-queue doesn't give you things for Dialogue: 0,0:24:33.00,0:24:35.00,Default,,0000,0000,0000,,finding duplicates or finding the minimum or Dialogue: 0,0:24:35.00,0:24:39.00,Default,,0000,0000,0000,,doing the mode it's not actually an easy operation because you have Dialogue: 0,0:24:39.00,0:24:42.00,Default,,0000,0000,0000,,it in a heap form. I can get to the max Dialogue: 0,0:24:42.00,0:24:42.00,Default,,0000,0000,0000,,quickly. Dialogue: 0,0:24:42.00,0:24:46.00,Default,,0000,0000,0000,,So if I cared about pulling them out in sorted order Dialogue: 0,0:24:46.00,0:24:47.00,Default,,0000,0000,0000,,to browse them, Dialogue: 0,0:24:47.00,0:24:51.00,Default,,0000,0000,0000,,I could stuff things into a P-queue and then pull them out, but what's interesting about that is Dialogue: 0,0:24:51.00,0:24:54.00,Default,,0000,0000,0000,,it requires destroying the P-queue. Dialogue: 0,0:24:54.00,0:24:57.00,Default,,0000,0000,0000,,The P-queue isn't really a place you store things and plan on using them again. It's Dialogue: 0,0:24:57.00,0:25:00.00,Default,,0000,0000,0000,,the place you stick things in order to get them out Dialogue: 0,0:25:00.00,0:25:02.00,Default,,0000,0000,0000,,in an order that's only Dialogue: 0,0:25:02.00,0:25:05.00,Default,,0000,0000,0000,,value is in the de-queuing of them, pulling them out. Dialogue: 0,0:25:05.00,0:25:10.00,Default,,0000,0000,0000,,So finding the most promising option to look at in a search or finding the most Dialogue: 0,0:25:10.00,0:25:13.00,Default,,0000,0000,0000,,high-priority activity to take on or something. Dialogue: 0,0:25:13.00,0:25:16.00,Default,,0000,0000,0000,,But it doesn't really have the - if I wanted to be able to look at all Dialogue: 0,0:25:16.00,0:25:18.00,Default,,0000,0000,0000,,the students in my class in sorted order, Dialogue: 0,0:25:18.00,0:25:20.00,Default,,0000,0000,0000,,it's like, well, I could stick them in a P-queue and then pull them out, but it's sort of Dialogue: 0,0:25:20.00,0:25:25.00,Default,,0000,0000,0000,,funny. I have to put them in the P-queue just to pull them back out. It wasn't a good way to store them for that Dialogue: 0,0:25:25.00,0:25:27.00,Default,,0000,0000,0000,,browsing operation to be easily repeated. Dialogue: 0,0:25:27.00,0:25:29.00,Default,,0000,0000,0000,,If I put them into a sorted vector, I could just keep Dialogue: 0,0:25:29.00,0:25:33.00,Default,,0000,0000,0000,,iterating over it whenever I need to see it again. Dialogue: 0,0:25:33.00,0:25:37.00,Default,,0000,0000,0000,,So a lot of the things that it comes down to is having a pretty good Dialogue: 0,0:25:37.00,0:25:41.00,Default,,0000,0000,0000,,visualization of what it is that going to a pointer-based data structure buys you, and Dialogue: 0,0:25:41.00,0:25:44.00,Default,,0000,0000,0000,,what it costs you, relative to the continuous memory. That's one of the Dialogue: 0,0:25:44.00,0:25:45.00,Default,,0000,0000,0000,, Dialogue: 0,0:25:45.00,0:25:48.00,Default,,0000,0000,0000,,tensions underneath most of these things. It's like, Dialogue: 0,0:25:48.00,0:25:50.00,Default,,0000,0000,0000,,putting more memory into it Dialogue: 0,0:25:50.00,0:25:54.00,Default,,0000,0000,0000,,by virtue of having a pointer wire as opposed to a Dialogue: 0,0:25:54.00,0:25:55.00,Default,,0000,0000,0000,,location Dialogue: 0,0:25:55.00,0:25:57.00,Default,,0000,0000,0000,,arrangement. Dialogue: 0,0:25:57.00,0:26:00.00,Default,,0000,0000,0000,,There's no information that's stored to get you from a race of zero to a Dialogue: 0,0:26:00.00,0:26:04.00,Default,,0000,0000,0000,,race of two. They're just continuous in memory. So it saves you space because you only Dialogue: 0,0:26:04.00,0:26:07.00,Default,,0000,0000,0000,,have to know where it starts and access continuously for that. This pointer means Dialogue: 0,0:26:07.00,0:26:11.00,Default,,0000,0000,0000,,there's more kerversals. There's more memory. There's more opportunity Dialogue: 0,0:26:11.00,0:26:12.00,Default,,0000,0000,0000,,to air, but it gave Dialogue: 0,0:26:12.00,0:26:16.00,Default,,0000,0000,0000,,you this flexibility. It broke down this continuous block, that's kind Dialogue: 0,0:26:16.00,0:26:17.00,Default,,0000,0000,0000,,of a monolith, Dialogue: 0,0:26:17.00,0:26:21.00,Default,,0000,0000,0000,,into these pieces that are more flexible in how you can rearrange Dialogue: 0,0:26:21.00,0:26:25.00,Default,,0000,0000,0000,,them. So thinking about these things is Dialogue: 0,0:26:25.00,0:26:28.00,Default,,0000,0000,0000,,an important skill to come away from 106b with that, Dialogue: 0,0:26:28.00,0:26:30.00,Default,,0000,0000,0000,,yeah, there's never Dialogue: 0,0:26:30.00,0:26:31.00,Default,,0000,0000,0000,,one right answer. Dialogue: 0,0:26:31.00,0:26:33.00,Default,,0000,0000,0000,, Dialogue: 0,0:26:33.00,0:26:36.00,Default,,0000,0000,0000,,You're investing to solve this other problem, and Dialogue: 0,0:26:36.00,0:26:40.00,Default,,0000,0000,0000,,there's going to be downsides. There's no Dialogue: 0,0:26:40.00,0:26:41.00,Default,,0000,0000,0000,,obvious Dialogue: 0,0:26:41.00,0:26:43.00,Default,,0000,0000,0000,,triumph over all. Dialogue: 0,0:26:43.00,0:26:47.00,Default,,0000,0000,0000,,It's fast, it's cheap and it's small and easy to write Dialogue: 0,0:26:47.00,0:26:51.00,Default,,0000,0000,0000,,solutions out there. Dialogue: 0,0:26:51.00,0:26:53.00,Default,,0000,0000,0000,,So I put up here - I had to Dialogue: 0,0:26:53.00,0:26:54.00,Default,,0000,0000,0000,,whittle Dialogue: 0,0:26:54.00,0:26:57.00,Default,,0000,0000,0000,,this down to the five or six things that, at Dialogue: 0,0:26:57.00,0:27:02.00,Default,,0000,0000,0000,,the end of 106b, I want you to feel like, that's what I got. Dialogue: 0,0:27:02.00,0:27:04.00,Default,,0000,0000,0000,,That's the heart of Dialogue: 0,0:27:04.00,0:27:05.00,Default,,0000,0000,0000,, Dialogue: 0,0:27:05.00,0:27:06.00,Default,,0000,0000,0000,,the Dialogue: 0,0:27:06.00,0:27:10.00,Default,,0000,0000,0000,,goal. The MVPs - the most valuable players of the Dialogue: 0,0:27:10.00,0:27:12.00,Default,,0000,0000,0000,,106b curriculum here. Dialogue: 0,0:27:12.00,0:27:15.00,Default,,0000,0000,0000,,You're looking back at it, and you go, where did I start, where did I end up, Dialogue: 0,0:27:15.00,0:27:18.00,Default,,0000,0000,0000,,and how did my knowledge grow? Dialogue: 0,0:27:18.00,0:27:21.00,Default,,0000,0000,0000,,I'm hoping these are the things that stand out for you. That was a Dialogue: 0,0:27:21.00,0:27:23.00,Default,,0000,0000,0000,,real Dialogue: 0,0:27:23.00,0:27:24.00,Default,,0000,0000,0000,,growth area for me. One Dialogue: 0,0:27:24.00,0:27:27.00,Default,,0000,0000,0000,,is this idea of abstraction. Dialogue: 0,0:27:27.00,0:27:32.00,Default,,0000,0000,0000,,That was stressed early on. Here's a stack, here's a queue, here's a set. They Dialogue: 0,0:27:32.00,0:27:33.00,Default,,0000,0000,0000,,do things for you. We don't know how Dialogue: 0,0:27:33.00,0:27:34.00,Default,,0000,0000,0000,,they work yet, Dialogue: 0,0:27:34.00,0:27:38.00,Default,,0000,0000,0000,,but you make cool things happen with them. So you solve maze problems and Dialogue: 0,0:27:38.00,0:27:40.00,Default,,0000,0000,0000,,random writers and Dialogue: 0,0:27:40.00,0:27:43.00,Default,,0000,0000,0000,,do neat things with Dialogue: 0,0:27:43.00,0:27:47.00,Default,,0000,0000,0000,,dictionaries without knowing how they work. So you're leveraging existing Dialogue: 0,0:27:47.00,0:27:48.00,Default,,0000,0000,0000,,material without knowledge of how it works. Dialogue: 0,0:27:48.00,0:27:52.00,Default,,0000,0000,0000,,It helps to keep the complexity down. You can solve much more interesting problems Dialogue: 0,0:27:52.00,0:27:56.00,Default,,0000,0000,0000,,than you could without them. Try to go back and imagine the Markov random writer Dialogue: 0,0:27:56.00,0:27:57.00,Default,,0000,0000,0000,,problem. Dialogue: 0,0:27:57.00,0:27:58.00,Default,,0000,0000,0000,,Now imagine doing it Dialogue: 0,0:27:58.00,0:28:00.00,Default,,0000,0000,0000,, Dialogue: 0,0:28:00.00,0:28:02.00,Default,,0000,0000,0000,,without the map in play. So Dialogue: 0,0:28:02.00,0:28:04.00,Default,,0000,0000,0000,,you had to figure out that Dialogue: 0,0:28:04.00,0:28:08.00,Default,,0000,0000,0000,,given this character, go look it up and find a place to store it, and Dialogue: 0,0:28:08.00,0:28:11.00,Default,,0000,0000,0000,,then store the character in some other array that was growing on Dialogue: 0,0:28:11.00,0:28:14.00,Default,,0000,0000,0000,,demand, as you put stuff in there. You would never have completed that Dialogue: 0,0:28:14.00,0:28:18.00,Default,,0000,0000,0000,,program. You would still be writing it today, having pointer errors and whatnot Dialogue: 0,0:28:18.00,0:28:19.00,Default,,0000,0000,0000,,behind the scenes. Dialogue: 0,0:28:19.00,0:28:22.00,Default,,0000,0000,0000,,Having those tools already there, it's like having Dialogue: 0,0:28:22.00,0:28:25.00,Default,,0000,0000,0000,,the microwave and the food processor, and you're about to cook instead Dialogue: 0,0:28:25.00,0:28:26.00,Default,,0000,0000,0000,,of having a Dialogue: 0,0:28:26.00,0:28:27.00,Default,,0000,0000,0000,,dull knife Dialogue: 0,0:28:27.00,0:28:31.00,Default,,0000,0000,0000,,and doing all your work with a Dialogue: 0,0:28:31.00,0:28:31.00,Default,,0000,0000,0000,,dull Dialogue: 0,0:28:31.00,0:28:34.00,Default,,0000,0000,0000,,knife and a fire. You actually have Dialogue: 0,0:28:34.00,0:28:36.00,Default,,0000,0000,0000,,some real power Dialogue: 0,0:28:36.00,0:28:39.00,Default,,0000,0000,0000,,there. Recursion's a big theme in the weeks that followed that. Dialogue: 0,0:28:39.00,0:28:41.00,Default,,0000,0000,0000,,How to solve these problems that Dialogue: 0,0:28:41.00,0:28:43.00,Default,,0000,0000,0000,,have this similar structure, Dialogue: 0,0:28:43.00,0:28:47.00,Default,,0000,0000,0000,,looking at these exhaustive traversals and choice problems that can Dialogue: 0,0:28:47.00,0:28:51.00,Default,,0000,0000,0000,,be solved with backtracking. Having this idea of how to think about thing [inaudible] Dialogue: 0,0:28:51.00,0:28:53.00,Default,,0000,0000,0000,,using the recursive problem solving Dialogue: 0,0:28:53.00,0:28:55.00,Default,,0000,0000,0000,,and how to model Dialogue: 0,0:28:55.00,0:28:56.00,Default,,0000,0000,0000,,that Dialogue: 0,0:28:56.00,0:28:59.00,Default,,0000,0000,0000,,process using the computer was a Dialogue: 0,0:28:59.00,0:29:02.00,Default,,0000,0000,0000,,very important thing that comes back. We look at algorithm Dialogue: 0,0:29:02.00,0:29:05.00,Default,,0000,0000,0000,,analysis, this idea of making this Dialogue: 0,0:29:05.00,0:29:08.00,Default,,0000,0000,0000,,sloppy map that computer scientists are Dialogue: 0,0:29:08.00,0:29:11.00,Default,,0000,0000,0000,,fond of, talking about the scalability and growth, knowing about curves and Dialogue: 0,0:29:11.00,0:29:13.00,Default,,0000,0000,0000,,the relationships and how to Dialogue: 0,0:29:13.00,0:29:16.00,Default,,0000,0000,0000,,look at algorithms. The more formal analysis. Dialogue: 0,0:29:16.00,0:29:17.00,Default,,0000,0000,0000,,Still, in this case, there's still quite Dialogue: 0,0:29:17.00,0:29:21.00,Default,,0000,0000,0000,,a bit more formulas to this than we really went into. If you Dialogue: 0,0:29:21.00,0:29:23.00,Default,,0000,0000,0000,,were go on in CS and look at it, you will see there's quite a lot Dialogue: 0,0:29:23.00,0:29:26.00,Default,,0000,0000,0000,,of rigor that can be Dialogue: 0,0:29:26.00,0:29:27.00,Default,,0000,0000,0000,,looked at in that area. Dialogue: 0,0:29:27.00,0:29:31.00,Default,,0000,0000,0000,,We were getting more an intuition for how to gauge things about algorithms and Dialogue: 0,0:29:31.00,0:29:33.00,Default,,0000,0000,0000,,their growth. Dialogue: 0,0:29:33.00,0:29:36.00,Default,,0000,0000,0000,,Then this backside, all about implementation strategies and tradeoffs. Dialogue: 0,0:29:36.00,0:29:38.00,Default,,0000,0000,0000,,So now that we've Dialogue: 0,0:29:38.00,0:29:40.00,Default,,0000,0000,0000,,benefited from those abstractions, and we've Dialogue: 0,0:29:40.00,0:29:43.00,Default,,0000,0000,0000,,solved some cool problems, what's it like to actually be the person building them? What Dialogue: 0,0:29:43.00,0:29:46.00,Default,,0000,0000,0000,,are the techniques? What does it take to Dialogue: 0,0:29:46.00,0:29:50.00,Default,,0000,0000,0000,,wrestle a pointer or a Linklis or a tree, heap graph into doing something really cool for you. How Dialogue: 0,0:29:50.00,0:29:52.00,Default,,0000,0000,0000,,does that Dialogue: 0,0:29:52.00,0:29:57.00,Default,,0000,0000,0000,,inform your information, what you expect about it and the Dialogue: 0,0:29:57.00,0:30:00.00,Default,,0000,0000,0000,,coding complexity that was inherent in achieving that result? Dialogue: 0,0:30:00.00,0:30:04.00,Default,,0000,0000,0000,,Hopefully in continuing with the theme that 106a started you on was this Dialogue: 0,0:30:04.00,0:30:07.00,Default,,0000,0000,0000,,appreciation for [inaudible]. In the Dialogue: 0,0:30:07.00,0:30:11.00,Default,,0000,0000,0000,,end, getting code that works, that's ugly, just Dialogue: 0,0:30:11.00,0:30:14.00,Default,,0000,0000,0000,,isn't, hopefully, what you're satisfied with. You want to Dialogue: 0,0:30:14.00,0:30:17.00,Default,,0000,0000,0000,,approach problem solving to produce beautiful, elegant, Dialogue: 0,0:30:17.00,0:30:19.00,Default,,0000,0000,0000,,unified, clean, Dialogue: 0,0:30:19.00,0:30:20.00,Default,,0000,0000,0000,,readable code Dialogue: 0,0:30:20.00,0:30:24.00,Default,,0000,0000,0000,,that you would be happy to show to other people and be proud of and Dialogue: 0,0:30:24.00,0:30:25.00,Default,,0000,0000,0000,,maintain and live with. Dialogue: 0,0:30:25.00,0:30:27.00,Default,,0000,0000,0000,,The kind of work that Dialogue: 0,0:30:27.00,0:30:29.00,Default,,0000,0000,0000,,other people you work with would appreciate Dialogue: 0,0:30:29.00,0:30:32.00,Default,,0000,0000,0000,,being involved with. Dialogue: 0,0:30:32.00,0:30:34.00,Default,,0000,0000,0000,,Things that are not so much Dialogue: 0,0:30:34.00,0:30:37.00,Default,,0000,0000,0000,,- I don't think these are the most valuable pointers, but what Dialogue: 0,0:30:37.00,0:30:38.00,Default,,0000,0000,0000,,came along the way, Dialogue: 0,0:30:38.00,0:30:39.00,Default,,0000,0000,0000,, Dialogue: 0,0:30:39.00,0:30:42.00,Default,,0000,0000,0000,,the idea of pointers and C++ being part of the - Dialogue: 0,0:30:42.00,0:30:45.00,Default,,0000,0000,0000,,C++ and its pointers, they're one and the same. We choose [inaudible] for a Dialogue: 0,0:30:45.00,0:30:48.00,Default,,0000,0000,0000,,language, so as a result, we get to learn some C++ Dialogue: 0,0:30:48.00,0:30:51.00,Default,,0000,0000,0000,,because it's so heavily Dialogue: 0,0:30:51.00,0:30:53.00,Default,,0000,0000,0000,,invested with pointers. We also have to do some practice with the pointers to Dialogue: 0,0:30:53.00,0:30:55.00,Default,,0000,0000,0000,,get our jobs done. Dialogue: 0,0:30:55.00,0:30:58.00,Default,,0000,0000,0000,,I think of those as being off to the side. I don't think of those being the Dialogue: 0,0:30:58.00,0:31:01.00,Default,,0000,0000,0000,,platform of things I worship. They are Dialogue: 0,0:31:01.00,0:31:05.00,Default,,0000,0000,0000,,things we need to get our job done. I Dialogue: 0,0:31:05.00,0:31:08.00,Default,,0000,0000,0000,,did put a little note about pointers here because there were quite a lot of comments on Dialogue: 0,0:31:08.00,0:31:12.00,Default,,0000,0000,0000,,the mid-quarter evals that said, pointers, pointers still scare me. They make me crazy. Dialogue: 0,0:31:12.00,0:31:14.00,Default,,0000,0000,0000,,I don't know enough about Dialogue: 0,0:31:14.00,0:31:15.00,Default,,0000,0000,0000,,pointers. Here's a fact for you. Dialogue: 0,0:31:15.00,0:31:18.00,Default,,0000,0000,0000,,You'll probably never feel like you know enough about pointers. Dialogue: 0,0:31:18.00,0:31:21.00,Default,,0000,0000,0000,,Today, tomorrow, ten years from now, you'll still kind of feel like Dialogue: 0,0:31:21.00,0:31:24.00,Default,,0000,0000,0000,,there's some real subtlety and trickiness in there. Dialogue: 0,0:31:24.00,0:31:27.00,Default,,0000,0000,0000,,They're an extremely powerful facility that gives you that Dialogue: 0,0:31:27.00,0:31:31.00,Default,,0000,0000,0000,,direct control over allocation and deallocation and all the wiring and Dialogue: 0,0:31:31.00,0:31:32.00,Default,,0000,0000,0000,,sharing Dialogue: 0,0:31:32.00,0:31:34.00,Default,,0000,0000,0000,,that Dialogue: 0,0:31:34.00,0:31:37.00,Default,,0000,0000,0000,,is important to building these complicated data structures. Dialogue: 0,0:31:37.00,0:31:40.00,Default,,0000,0000,0000,,But there are so many pitfalls. I'm sure you've run into Dialogue: 0,0:31:40.00,0:31:43.00,Default,,0000,0000,0000,,most of these, if not all of them at some point, where you Dialogue: 0,0:31:43.00,0:31:46.00,Default,,0000,0000,0000,,mishandled a pointer, failed the allocator, deallocate, Dialogue: 0,0:31:46.00,0:31:49.00,Default,,0000,0000,0000,,and Dialogue: 0,0:31:49.00,0:31:52.00,Default,,0000,0000,0000,,the way it gets reported, whether the compiler or the runtime error that Dialogue: 0,0:31:52.00,0:31:56.00,Default,,0000,0000,0000,,you see is helpful in sorting it out is a real cause for Dialogue: 0,0:31:56.00,0:31:58.00,Default,,0000,0000,0000,,long hours to disappear Dialogue: 0,0:31:58.00,0:32:01.00,Default,,0000,0000,0000,,in the name of mastery of this. Dialogue: 0,0:32:01.00,0:32:02.00,Default,,0000,0000,0000,,If you're still wary of pointers, you Dialogue: 0,0:32:02.00,0:32:04.00,Default,,0000,0000,0000,,probably should be. Dialogue: 0,0:32:04.00,0:32:06.00,Default,,0000,0000,0000,,Think of this as your first go-around. Dialogue: 0,0:32:06.00,0:32:07.00,Default,,0000,0000,0000,,We're still Dialogue: 0,0:32:07.00,0:32:10.00,Default,,0000,0000,0000,,at the journeyman's stage for programming here. Dialogue: 0,0:32:10.00,0:32:14.00,Default,,0000,0000,0000,,So although there were pointers in 106a, they were very hidden. This Dialogue: 0,0:32:14.00,0:32:17.00,Default,,0000,0000,0000,,is the first time you really see it and are exposed to it and trying to get your head Dialogue: 0,0:32:17.00,0:32:18.00,Default,,0000,0000,0000,,around it. Dialogue: 0,0:32:18.00,0:32:20.00,Default,,0000,0000,0000,,If you go on to 107 and 108, you'll just Dialogue: 0,0:32:20.00,0:32:23.00,Default,,0000,0000,0000,,get more and more practice. It will Dialogue: 0,0:32:23.00,0:32:26.00,Default,,0000,0000,0000,,become more solid as you keep working your way through it, but Dialogue: 0,0:32:26.00,0:32:30.00,Default,,0000,0000,0000,,at this stage, it's okay Dialogue: 0,0:32:30.00,0:32:31.00,Default,,0000,0000,0000,,and Dialogue: 0,0:32:31.00,0:32:35.00,Default,,0000,0000,0000,,commonplace to feel still, a little bit - you see the star, and you take a Dialogue: 0,0:32:35.00,0:32:37.00,Default,,0000,0000,0000,,double take. That's just where you should be. Dialogue: 0,0:32:37.00,0:32:40.00,Default,,0000,0000,0000,,It's just like in the Dialogue: 0,0:32:40.00,0:32:43.00,Default,,0000,0000,0000,,Chinese restaurants. They put the little red star by food you want to be Dialogue: 0,0:32:43.00,0:32:49.00,Default,,0000,0000,0000,,careful of. That's why they put the star for the Dialogue: 0,0:32:49.00,0:32:52.00,Default,,0000,0000,0000,,pointer. I also wanted to Dialogue: 0,0:32:52.00,0:32:54.00,Default,,0000,0000,0000,,zoom out farther, Dialogue: 0,0:32:54.00,0:32:56.00,Default,,0000,0000,0000,,a decade from Dialogue: 0,0:32:56.00,0:32:59.00,Default,,0000,0000,0000,,now, when you are Dialogue: 0,0:32:59.00,0:33:01.00,Default,,0000,0000,0000,,thinking back on the Dialogue: 0,0:33:01.00,0:33:04.00,Default,,0000,0000,0000,,whole of your education and what you learned. Do I want to really Dialogue: 0,0:33:04.00,0:33:06.00,Default,,0000,0000,0000,,remember how to Dialogue: 0,0:33:06.00,0:33:08.00,Default,,0000,0000,0000,,type in keyword and the sequel plus generic Dialogue: 0,0:33:08.00,0:33:10.00,Default,,0000,0000,0000,,template facility? No. Dialogue: 0,0:33:10.00,0:33:13.00,Default,,0000,0000,0000,,If you code in C++ every day, you'll know that. If you don't, you Dialogue: 0,0:33:13.00,0:33:14.00,Default,,0000,0000,0000,,can forget it. It's long gone. Dialogue: 0,0:33:14.00,0:33:16.00,Default,,0000,0000,0000,,What I hope you'll carry away from you Dialogue: 0,0:33:16.00,0:33:18.00,Default,,0000,0000,0000,,is a couple Dialogue: 0,0:33:18.00,0:33:19.00,Default,,0000,0000,0000,,concepts that Dialogue: 0,0:33:19.00,0:33:21.00,Default,,0000,0000,0000,,broaden Dialogue: 0,0:33:21.00,0:33:23.00,Default,,0000,0000,0000,,outside of CS. One is this idea of algorithmic thinking, Dialogue: 0,0:33:23.00,0:33:27.00,Default,,0000,0000,0000,,how you approach something logically and step-wise and draw pictures and analyze it to understand Dialogue: 0,0:33:27.00,0:33:29.00,Default,,0000,0000,0000,,the cases Dialogue: 0,0:33:29.00,0:33:32.00,Default,,0000,0000,0000,,and to debug when things aren't working well. I think that's a skill that Dialogue: 0,0:33:32.00,0:33:33.00,Default,,0000,0000,0000,,transcends Dialogue: 0,0:33:33.00,0:33:37.00,Default,,0000,0000,0000,,the art of computer programming into other domains, any kind of thinking Dialogue: 0,0:33:37.00,0:33:39.00,Default,,0000,0000,0000,,logically and problem solving and analyzing in that Dialogue: 0,0:33:39.00,0:33:43.00,Default,,0000,0000,0000,,way. I also hope that some of the experimental things we did with the sort Dialogue: 0,0:33:43.00,0:33:45.00,Default,,0000,0000,0000,,lab and the P-queue Dialogue: 0,0:33:45.00,0:33:48.00,Default,,0000,0000,0000,,and some of the big O and thing we tried to do in class together help Dialogue: 0,0:33:48.00,0:33:51.00,Default,,0000,0000,0000,,you to [inaudible] back of the envelope calculations. This is something I'm Dialogue: 0,0:33:51.00,0:33:53.00,Default,,0000,0000,0000,,a little bit of a - Dialogue: 0,0:33:53.00,0:33:55.00,Default,,0000,0000,0000,,it's a pet issue of mine, which is, Dialogue: 0,0:33:55.00,0:33:57.00,Default,,0000,0000,0000,,I think, in the era of computers Dialogue: 0,0:33:57.00,0:34:00.00,Default,,0000,0000,0000,,and whatnot, really easy to get distanced from numbers and start Dialogue: 0,0:34:00.00,0:34:03.00,Default,,0000,0000,0000,,thinking, I just punch numbers into formulas and one comes out. It must be Dialogue: 0,0:34:03.00,0:34:06.00,Default,,0000,0000,0000,,the truth. Not having any intuition as to whether that's the right Dialogue: 0,0:34:06.00,0:34:10.00,Default,,0000,0000,0000,,number, whether that number makes sense, whether it's grounded, Dialogue: 0,0:34:10.00,0:34:14.00,Default,,0000,0000,0000,,and whether you actually are [inaudible] or so off because you've Dialogue: 0,0:34:14.00,0:34:17.00,Default,,0000,0000,0000,,actually made an entry error, and you don't even notice it. Dialogue: 0,0:34:17.00,0:34:20.00,Default,,0000,0000,0000,,So becoming comfortable with this idea of using numbers to drive things, Dialogue: 0,0:34:20.00,0:34:21.00,Default,,0000,0000,0000,,being able to Dialogue: 0,0:34:21.00,0:34:26.00,Default,,0000,0000,0000,,take some time trials, do some predictions, do some more time trials, Dialogue: 0,0:34:26.00,0:34:28.00,Default,,0000,0000,0000,,match those things up, do a little sketching on your numbers and see the Dialogue: 0,0:34:28.00,0:34:32.00,Default,,0000,0000,0000,,things that are working out. So being comfortable having the math and the theory Dialogue: 0,0:34:32.00,0:34:34.00,Default,,0000,0000,0000,,reinforce each other Dialogue: 0,0:34:34.00,0:34:34.00,Default,,0000,0000,0000,,and Dialogue: 0,0:34:34.00,0:34:36.00,Default,,0000,0000,0000,,not get too Dialogue: 0,0:34:36.00,0:34:39.00,Default,,0000,0000,0000,,distanced from the fact that those numbers do play out in Dialogue: 0,0:34:39.00,0:34:42.00,Default,,0000,0000,0000,,the real world in ways that are interesting. Don't just let the numbers themselves Dialogue: 0,0:34:42.00,0:34:44.00,Default,,0000,0000,0000,,tell the story. There really is more Dialogue: 0,0:34:44.00,0:34:47.00,Default,,0000,0000,0000,,to connect it up with. Dialogue: 0,0:34:47.00,0:34:49.00,Default,,0000,0000,0000,,This idea of tradeoffs. Dialogue: 0,0:34:49.00,0:34:51.00,Default,,0000,0000,0000,,You may not remember Dialogue: 0,0:34:51.00,0:34:54.00,Default,,0000,0000,0000,,how you can write a Linklis or how the hash table does Dialogue: 0,0:34:54.00,0:34:56.00,Default,,0000,0000,0000,,the things it does Dialogue: 0,0:34:56.00,0:35:00.00,Default,,0000,0000,0000,,and how to get one working, but hopefully you will take away this idea that Dialogue: 0,0:35:00.00,0:35:03.00,Default,,0000,0000,0000,,the answer to most questions begins with the phrase, it depends. Dialogue: 0,0:35:03.00,0:35:05.00,Default,,0000,0000,0000,,If I say, is it better to use a hash table or [inaudible] search tree, the answer Dialogue: 0,0:35:05.00,0:35:09.00,Default,,0000,0000,0000,,will be, it depends. There's no, Dialogue: 0,0:35:09.00,0:35:12.00,Default,,0000,0000,0000,,it's always better to use this sort. It's always Dialogue: 0,0:35:12.00,0:35:14.00,Default,,0000,0000,0000,,wrong to use this approach. Dialogue: 0,0:35:14.00,0:35:15.00,Default,,0000,0000,0000,,It's, it depends. Do Dialogue: 0,0:35:15.00,0:35:18.00,Default,,0000,0000,0000,,you have the code written for that, and it works well, and you don't care how Dialogue: 0,0:35:18.00,0:35:19.00,Default,,0000,0000,0000,,long it takes? Dialogue: 0,0:35:19.00,0:35:23.00,Default,,0000,0000,0000,,Then bubble sort actually could be the right answer. Dialogue: 0,0:35:23.00,0:35:25.00,Default,,0000,0000,0000,,Barack Obama not withstanding. Dialogue: 0,0:35:25.00,0:35:27.00,Default,,0000,0000,0000,,But knowing whether memory is Dialogue: 0,0:35:27.00,0:35:32.00,Default,,0000,0000,0000,,at premium, time is at premium, what your mix of operations are, Dialogue: 0,0:35:32.00,0:35:33.00,Default,,0000,0000,0000,,what Dialogue: 0,0:35:33.00,0:35:34.00,Default,,0000,0000,0000,,language you're working with, what Dialogue: 0,0:35:34.00,0:35:38.00,Default,,0000,0000,0000,,program expertise you have, what timeline you have for developing it all Dialogue: 0,0:35:38.00,0:35:42.00,Default,,0000,0000,0000,,can play a role in deciding what choices to make and what strategy to pursue. Dialogue: 0,0:35:42.00,0:35:45.00,Default,,0000,0000,0000,,So being very comfortable with this idea that it's about gathering information Dialogue: 0,0:35:45.00,0:35:46.00,Default,,0000,0000,0000,,before you Dialogue: 0,0:35:46.00,0:35:49.00,Default,,0000,0000,0000,,can commit to one strategy as opposed to it's always going to be Dialogue: 0,0:35:49.00,0:35:52.00,Default,,0000,0000,0000,,this or that. Dialogue: 0,0:35:52.00,0:35:54.00,Default,,0000,0000,0000,,So that's the 106b thing. Dialogue: 0,0:35:54.00,0:35:57.00,Default,,0000,0000,0000,,I have a couple slides here on Dialogue: 0,0:35:57.00,0:35:59.00,Default,,0000,0000,0000,,things that happen after 106b. I'm Dialogue: 0,0:35:59.00,0:36:01.00,Default,,0000,0000,0000,,just going to go ahead and show you. Dialogue: 0,0:36:01.00,0:36:03.00,Default,,0000,0000,0000,, Dialogue: 0,0:36:03.00,0:36:06.00,Default,,0000,0000,0000,,This would be a great time to ask questions. In particular, if there's anything you're Dialogue: 0,0:36:06.00,0:36:07.00,Default,,0000,0000,0000,,curious about. Dialogue: 0,0:36:07.00,0:36:10.00,Default,,0000,0000,0000,,Where do we go from here, and Dialogue: 0,0:36:10.00,0:36:13.00,Default,,0000,0000,0000,,how do we make good decisions about things that follow? The Dialogue: 0,0:36:13.00,0:36:17.00,Default,,0000,0000,0000,,most obvious following courses from CS - if you took 106b Dialogue: 0,0:36:17.00,0:36:19.00,Default,,0000,0000,0000,,and you hated it, I'm very sorry. Dialogue: 0,0:36:19.00,0:36:23.00,Default,,0000,0000,0000,,Hopefully Dialogue: 0,0:36:23.00,0:36:25.00,Default,,0000,0000,0000,,the scarring Dialogue: 0,0:36:25.00,0:36:26.00,Default,,0000,0000,0000,,will heal over and you'll lead a Dialogue: 0,0:36:26.00,0:36:28.00,Default,,0000,0000,0000,,productive and happy life Dialogue: 0,0:36:28.00,0:36:30.00,Default,,0000,0000,0000,,elsewhere. If you did like it and you think, Dialogue: 0,0:36:30.00,0:36:33.00,Default,,0000,0000,0000,,I'm kind of interested in this. What do I do next to explore further? Dialogue: 0,0:36:33.00,0:36:35.00,Default,,0000,0000,0000,,Where else can I go with this? Dialogue: 0,0:36:35.00,0:36:38.00,Default,,0000,0000,0000,,I put up the intro Dialogue: 0,0:36:38.00,0:36:40.00,Default,,0000,0000,0000,,courses with their numbers and names, and I'll talk a little bit Dialogue: 0,0:36:40.00,0:36:44.00,Default,,0000,0000,0000,,about what each of these does to give you an idea of what opportunity it Dialogue: 0,0:36:44.00,0:36:45.00,Default,,0000,0000,0000,,offers to you. Dialogue: 0,0:36:45.00,0:36:49.00,Default,,0000,0000,0000,,The obvious follow onto the programming side - 106a and b Dialogue: 0,0:36:49.00,0:36:51.00,Default,,0000,0000,0000,,are programming courses, building your programming mastery. Dialogue: 0,0:36:51.00,0:36:54.00,Default,,0000,0000,0000,,107 follow in the same vein. We typically call those systems Dialogue: 0,0:36:54.00,0:36:56.00,Default,,0000,0000,0000,,courses in CS nomenclature. Dialogue: 0,0:36:56.00,0:36:59.00,Default,,0000,0000,0000,,That means practical, hands on programming, getting more exposure Dialogue: 0,0:36:59.00,0:37:00.00,Default,,0000,0000,0000,,to the system. Dialogue: 0,0:37:00.00,0:37:05.00,Default,,0000,0000,0000,,So 107 builds on 106b's knowledge in a class called programming paradigms. Dialogue: 0,0:37:05.00,0:37:08.00,Default,,0000,0000,0000,,Part of what it's trying to explore is different languages. Dialogue: 0,0:37:08.00,0:37:11.00,Default,,0000,0000,0000,,So you actually look at the language, C, kind of stepping back to old school. Dialogue: 0,0:37:11.00,0:37:15.00,Default,,0000,0000,0000,,You look at the language scheme, which is a functional language that Dialogue: 0,0:37:15.00,0:37:17.00,Default,,0000,0000,0000,,was developed for AI purposes Dialogue: 0,0:37:17.00,0:37:17.00,Default,,0000,0000,0000,,that Dialogue: 0,0:37:17.00,0:37:21.00,Default,,0000,0000,0000,,has a long history coming from the math side of things. Probably looking at some Dialogue: 0,0:37:21.00,0:37:25.00,Default,,0000,0000,0000,,scripting and flexible [inaudible] like Python. We kind of mix them up a Dialogue: 0,0:37:25.00,0:37:28.00,Default,,0000,0000,0000,,little bit, so it's not exactly the same things, but looking at other Dialogue: 0,0:37:28.00,0:37:30.00,Default,,0000,0000,0000,,languages, other ways of doing things. Dialogue: 0,0:37:30.00,0:37:33.00,Default,,0000,0000,0000,,The other component of 107 is also looking at Dialogue: 0,0:37:33.00,0:37:35.00,Default,,0000,0000,0000,,some more low-level things. Dialogue: 0,0:37:35.00,0:37:37.00,Default,,0000,0000,0000,,What happens? When you Dialogue: 0,0:37:37.00,0:37:41.00,Default,,0000,0000,0000,,pass your code off to the compiler, what is it doing? What kind of analysis does do of your Dialogue: 0,0:37:41.00,0:37:44.00,Default,,0000,0000,0000,,code? How does it actually generate machine code? What happens in the machine layer, Dialogue: 0,0:37:44.00,0:37:47.00,Default,,0000,0000,0000,,understanding some more of the performance implications Dialogue: 0,0:37:47.00,0:37:50.00,Default,,0000,0000,0000,,and how things are expressed. Getting a better understanding of pointers actually Dialogue: 0,0:37:50.00,0:37:53.00,Default,,0000,0000,0000,,comes up because there is a certain amount of low-level coding that's being Dialogue: 0,0:37:53.00,0:37:54.00,Default,,0000,0000,0000,,explored in this class. Dialogue: 0,0:37:54.00,0:37:58.00,Default,,0000,0000,0000,,So building on the programming skill as we move toward a Unix Dialogue: 0,0:37:58.00,0:38:00.00,Default,,0000,0000,0000,,Linux-based Dialogue: 0,0:38:00.00,0:38:02.00,Default,,0000,0000,0000,,environment. So away from the Mac and Windows. Dialogue: 0,0:38:02.00,0:38:03.00,Default,,0000,0000,0000,, Dialogue: 0,0:38:03.00,0:38:08.00,Default,,0000,0000,0000,,Just continue building larger programs with complicated Dialogue: 0,0:38:08.00,0:38:10.00,Default,,0000,0000,0000,,features to grow your mastery. Dialogue: 0,0:38:10.00,0:38:13.00,Default,,0000,0000,0000,,Internally, we call this class programming maturity, even though Dialogue: 0,0:38:13.00,0:38:14.00,Default,,0000,0000,0000,,it's not its title. Dialogue: 0,0:38:14.00,0:38:18.00,Default,,0000,0000,0000,,We see it that way in the sequence in terms of just growing you into Dialogue: 0,0:38:18.00,0:38:19.00,Default,,0000,0000,0000,,a Dialogue: 0,0:38:19.00,0:38:22.00,Default,,0000,0000,0000,,more versatile programmer, seeing different languages, different things Dialogue: 0,0:38:22.00,0:38:25.00,Default,,0000,0000,0000,,and getting more understanding of what happens under the hood. Dialogue: 0,0:38:25.00,0:38:29.00,Default,,0000,0000,0000,,It is a five-unit class. It's typically offered fall and spring. Most Dialogue: 0,0:38:29.00,0:38:30.00,Default,,0000,0000,0000,,people thing it is Dialogue: 0,0:38:30.00,0:38:33.00,Default,,0000,0000,0000,,about as much work as 106b. Some a Dialogue: 0,0:38:33.00,0:38:37.00,Default,,0000,0000,0000,,little more or a little less in different parts of the quarter, depending on what your Dialogue: 0,0:38:37.00,0:38:38.00,Default,,0000,0000,0000,,background is and Dialogue: 0,0:38:38.00,0:38:39.00,Default,,0000,0000,0000,, Dialogue: 0,0:38:39.00,0:38:41.00,Default,,0000,0000,0000,,how 106b worked for you. Dialogue: 0,0:38:41.00,0:38:44.00,Default,,0000,0000,0000,,In a model, I think most people think of it as being - would you guys Dialogue: 0,0:38:44.00,0:38:45.00,Default,,0000,0000,0000,,say 107 Dialogue: 0,0:38:45.00,0:38:48.00,Default,,0000,0000,0000,,about as hard as 106b? Dialogue: 0,0:38:48.00,0:38:51.00,Default,,0000,0000,0000,,Some ways, it's harder. Some ways, it's not. Maybe that's Dialogue: 0,0:38:51.00,0:38:55.00,Default,,0000,0000,0000,,the deal. The 108 class which follows onto 107, but that Dialogue: 0,0:38:55.00,0:38:57.00,Default,,0000,0000,0000,,prerequisite is particularly strong. It's a Java class. Dialogue: 0,0:38:57.00,0:39:00.00,Default,,0000,0000,0000,,So moving in the other direction. Rather than moving down an extraction, moving Dialogue: 0,0:39:00.00,0:39:02.00,Default,,0000,0000,0000,,up on the extraction, Dialogue: 0,0:39:02.00,0:39:05.00,Default,,0000,0000,0000,,looking at more large-scale design, modern programming technique, Dialogue: 0,0:39:05.00,0:39:06.00,Default,,0000,0000,0000,,using Dialogue: 0,0:39:06.00,0:39:10.00,Default,,0000,0000,0000,,object-oriented facilities, thinking about large-scale programming. You do a Dialogue: 0,0:39:10.00,0:39:11.00,Default,,0000,0000,0000,,big team project in the Dialogue: 0,0:39:11.00,0:39:13.00,Default,,0000,0000,0000,,end, so a three week, Dialogue: 0,0:39:13.00,0:39:15.00,Default,,0000,0000,0000,,three person, massive effort Dialogue: 0,0:39:15.00,0:39:17.00,Default,,0000,0000,0000,,that is the first Dialogue: 0,0:39:17.00,0:39:26.00,Default,,0000,0000,0000,,really big scale thing that you'll be exposed to in the lower-division Dialogue: 0,0:39:26.00,0:39:30.00,Default,,0000,0000,0000,,curriculum. [Inaudible]. Sometimes in 107l, which has some relationship to the Dialogue: 0,0:39:30.00,0:39:33.00,Default,,0000,0000,0000,,106l in the way that it's more hands-on, more Dialogue: 0,0:39:33.00,0:39:34.00,Default,,0000,0000,0000,,C++, Dialogue: 0,0:39:34.00,0:39:37.00,Default,,0000,0000,0000,,I don't know whether it will be offered this spring or not, Dialogue: 0,0:39:37.00,0:39:38.00,Default,,0000,0000,0000,,but Dialogue: 0,0:39:38.00,0:39:41.00,Default,,0000,0000,0000,,if you look in Access, it will tell you at least whether we have it tentatively on Dialogue: 0,0:39:41.00,0:39:42.00,Default,,0000,0000,0000,,the schedule. Dialogue: 0,0:39:42.00,0:39:46.00,Default,,0000,0000,0000,,I think that comes and goes with the interest from the students and the Dialogue: 0,0:39:46.00,0:39:51.00,Default,,0000,0000,0000,,availability of someone to teach Dialogue: 0,0:39:51.00,0:39:52.00,Default,,0000,0000,0000,,it. Dialogue: 0,0:39:52.00,0:39:55.00,Default,,0000,0000,0000,,[Inaudible] can we watch [inaudible]? Dialogue: 0,0:39:55.00,0:39:58.00,Default,,0000,0000,0000,,Yeah, 107 and 108 are offered on TV usually Dialogue: 0,0:39:58.00,0:40:02.00,Default,,0000,0000,0000,,once a year. 107 is offered on TV this spring. The one in fall is Dialogue: 0,0:40:02.00,0:40:03.00,Default,,0000,0000,0000,,not taped. Dialogue: 0,0:40:03.00,0:40:06.00,Default,,0000,0000,0000,,It might be that the old lectures from spring are somewhere that Dialogue: 0,0:40:06.00,0:40:09.00,Default,,0000,0000,0000,,you could dig them out, but I actually don't happen to know for sure. Dialogue: 0,0:40:09.00,0:40:11.00,Default,,0000,0000,0000,,108 is on TV, I think, Dialogue: 0,0:40:11.00,0:40:13.00,Default,,0000,0000,0000,,in the fall, not in the winter. So the fall lectures are probably still around for Dialogue: 0,0:40:13.00,0:40:16.00,Default,,0000,0000,0000,,108, so you could take a look at them. You Dialogue: 0,0:40:16.00,0:40:19.00,Default,,0000,0000,0000,,could certainly look at their websites, and Dialogue: 0,0:40:19.00,0:40:23.00,Default,,0000,0000,0000,,there's often a lot of old materials and handouts Dialogue: 0,0:40:23.00,0:40:26.00,Default,,0000,0000,0000,,and stuff that gives you at least some idea of things that have been Dialogue: 0,0:40:26.00,0:40:29.00,Default,,0000,0000,0000,,covered in the most recent offering of it. Dialogue: 0,0:40:29.00,0:40:34.00,Default,,0000,0000,0000,,Certainly showing up in the first week is one way to get an Dialogue: 0,0:40:34.00,0:40:36.00,Default,,0000,0000,0000,,idea of what you're in for. Dialogue: 0,0:40:36.00,0:40:38.00,Default,,0000,0000,0000,,108 is a four-unit class. Dialogue: 0,0:40:38.00,0:40:41.00,Default,,0000,0000,0000,,Because it's in Java, there's certain things about Java, Dialogue: 0,0:40:41.00,0:40:44.00,Default,,0000,0000,0000,,the safety and Dialogue: 0,0:40:44.00,0:40:48.00,Default,,0000,0000,0000,,the attentiveness of the compiler, makes the error handing a little Dialogue: 0,0:40:48.00,0:40:52.00,Default,,0000,0000,0000,,bit easier. So I don't think most people think of 108 as quite as intense as Dialogue: 0,0:40:52.00,0:40:55.00,Default,,0000,0000,0000,,107 or 106b, but that project at the end has quite a reputation Dialogue: 0,0:40:55.00,0:40:58.00,Default,,0000,0000,0000,,as being a Dialogue: 0,0:40:58.00,0:41:02.00,Default,,0000,0000,0000,,real time suck. So it has lots to do with being Dialogue: 0,0:41:02.00,0:41:04.00,Default,,0000,0000,0000,,scheduled and motivated and working through that team project at Dialogue: 0,0:41:04.00,0:41:05.00,Default,,0000,0000,0000,,the end. Dialogue: 0,0:41:05.00,0:41:09.00,Default,,0000,0000,0000,,I think that's where most people find the big challenge of Dialogue: 0,0:41:09.00,0:41:12.00,Default,,0000,0000,0000,,108. Then on the math side, in the Dialogue: 0,0:41:12.00,0:41:15.00,Default,,0000,0000,0000,,nomenclature for CS, we have this idea of theory, introducing you to more Dialogue: 0,0:41:15.00,0:41:16.00,Default,,0000,0000,0000,, Dialogue: 0,0:41:16.00,0:41:19.00,Default,,0000,0000,0000,,the formalism for big O and discrete structures and doing proofs and Dialogue: 0,0:41:19.00,0:41:21.00,Default,,0000,0000,0000,,thinking about logic. Dialogue: 0,0:41:21.00,0:41:25.00,Default,,0000,0000,0000,,So we have a 103 a and b and a 103x, which is a combined, Dialogue: 0,0:41:25.00,0:41:28.00,Default,,0000,0000,0000,,accelerated form of a and b, which serves as math classes. They are math classes Dialogue: 0,0:41:28.00,0:41:29.00,Default,,0000,0000,0000,,for introducing Dialogue: 0,0:41:29.00,0:41:33.00,Default,,0000,0000,0000,,the kind of mathematics that are important for computer scientists. Dialogue: 0,0:41:33.00,0:41:34.00,Default,,0000,0000,0000,,So that is Dialogue: 0,0:41:34.00,0:41:38.00,Default,,0000,0000,0000,,for people who are thinking about a CS major, another good course to get in Dialogue: 0,0:41:38.00,0:41:39.00,Default,,0000,0000,0000,,early. Pretty Dialogue: 0,0:41:39.00,0:41:43.00,Default,,0000,0000,0000,,much everything in the upper division of the CS major has Dialogue: 0,0:41:43.00,0:41:47.00,Default,,0000,0000,0000,,these things layered down as prereqs. So these are the intro courses that serve as the Dialogue: 0,0:41:47.00,0:41:50.00,Default,,0000,0000,0000,,gateway to prepping you to go on, and then looking at things in a more topical Dialogue: 0,0:41:50.00,0:41:51.00,Default,,0000,0000,0000,,way. Dialogue: 0,0:41:51.00,0:41:53.00,Default,,0000,0000,0000,,Looking at networks or security, Dialogue: 0,0:41:53.00,0:41:54.00,Default,,0000,0000,0000,,HCI or Dialogue: 0,0:41:54.00,0:41:59.00,Default,,0000,0000,0000,,artificial intelligence layers on a grounding in theory and programming Dialogue: 0,0:41:59.00,0:42:03.00,Default,,0000,0000,0000,,that came from the intro courses. So Dialogue: 0,0:42:03.00,0:42:07.00,Default,,0000,0000,0000,,that said, we're in the Dialogue: 0,0:42:07.00,0:42:08.00,Default,,0000,0000,0000,,midst of a really Dialogue: 0,0:42:08.00,0:42:10.00,Default,,0000,0000,0000,,serious curriculum revision, Dialogue: 0,0:42:10.00,0:42:13.00,Default,,0000,0000,0000,,which is Dialogue: 0,0:42:13.00,0:42:15.00,Default,,0000,0000,0000,,on the table and being designed right now, Dialogue: 0,0:42:15.00,0:42:18.00,Default,,0000,0000,0000,,and was voted on by our faculty and improved and has to go Dialogue: 0,0:42:18.00,0:42:22.00,Default,,0000,0000,0000,,through the school of engineering and get approval. Then there's going to be a little bit of Dialogue: 0,0:42:22.00,0:42:23.00,Default,,0000,0000,0000,,jostling as everything gets worked out. Dialogue: 0,0:42:23.00,0:42:27.00,Default,,0000,0000,0000,,But started next year, you're going to see some changes in the Dialogue: 0,0:42:27.00,0:42:29.00,Default,,0000,0000,0000,,department. Some of these courses are going to Dialogue: 0,0:42:29.00,0:42:33.00,Default,,0000,0000,0000,,get morphed, and Dialogue: 0,0:42:33.00,0:42:36.00,Default,,0000,0000,0000,,they won't be exactly the way they are today. Dialogue: 0,0:42:36.00,0:42:39.00,Default,,0000,0000,0000,,As a Stanford undergrad, you actually have the option of graduating under any set of Dialogue: 0,0:42:39.00,0:42:42.00,Default,,0000,0000,0000,,requirements that are in play any time you're an undergrad. So you could graduate under this year's Dialogue: 0,0:42:42.00,0:42:43.00,Default,,0000,0000,0000,,requirements, Dialogue: 0,0:42:43.00,0:42:45.00,Default,,0000,0000,0000,,or you could wait. Dialogue: 0,0:42:45.00,0:42:48.00,Default,,0000,0000,0000,,I think for most, the right answer's going to be wait because I think the new Dialogue: 0,0:42:48.00,0:42:51.00,Default,,0000,0000,0000,,arrangement is very much more student-friendly. Dialogue: 0,0:42:51.00,0:42:53.00,Default,,0000,0000,0000,,It has more flexibility Dialogue: 0,0:42:53.00,0:42:57.00,Default,,0000,0000,0000,,in the program. If you look at the CS program as it is, it has a lot of pick Dialogue: 0,0:42:57.00,0:43:00.00,Default,,0000,0000,0000,,one of two, pick one of three, pick one of two, Dialogue: 0,0:43:00.00,0:43:04.00,Default,,0000,0000,0000,,where you're very constrained on what you can choose. The new program is going to be Dialogue: 0,0:43:04.00,0:43:07.00,Default,,0000,0000,0000,,more track-based where you pick an area of interest. You say, I'm really interested in the Dialogue: 0,0:43:07.00,0:43:08.00,Default,,0000,0000,0000,,graphics. You do a little Dialogue: 0,0:43:08.00,0:43:12.00,Default,,0000,0000,0000,,depth concentration in that, and then just have room for a Dialogue: 0,0:43:12.00,0:43:15.00,Default,,0000,0000,0000,,very wide selection of electives to fill up the program as opposed to Dialogue: 0,0:43:15.00,0:43:19.00,Default,,0000,0000,0000,,a smorgasbord where we forced you to pick through a bunch of different areas. Dialogue: 0,0:43:19.00,0:43:24.00,Default,,0000,0000,0000,,So for most students, I think it gives you flexibility that actually gives you Dialogue: 0,0:43:24.00,0:43:25.00,Default,,0000,0000,0000,,the options Dialogue: 0,0:43:25.00,0:43:26.00,Default,,0000,0000,0000,,to Dialogue: 0,0:43:26.00,0:43:30.00,Default,,0000,0000,0000,,pick the classes that are most interesting to you and get the material that you want. It's a growing Dialogue: 0,0:43:30.00,0:43:32.00,Default,,0000,0000,0000,,recognition of the fact that CS Dialogue: 0,0:43:32.00,0:43:35.00,Default,,0000,0000,0000,,has really broadened as a field. Some say that our major looks the same way Dialogue: 0,0:43:35.00,0:43:37.00,Default,,0000,0000,0000,,it did ten years ago, Dialogue: 0,0:43:37.00,0:43:40.00,Default,,0000,0000,0000,,a classic definition of here's these Dialogue: 0,0:43:40.00,0:43:42.00,Default,,0000,0000,0000,,seven things that all matter. The Dialogue: 0,0:43:42.00,0:43:45.00,Default,,0000,0000,0000,,things aren't seven anymore. There's no 15 of them, 25 of them. If Dialogue: 0,0:43:45.00,0:43:49.00,Default,,0000,0000,0000,,you look at the spectrum of things that computer science is now Dialogue: 0,0:43:49.00,0:43:52.00,Default,,0000,0000,0000,,embracing, we can't say, you have to take one of all these things without keeping you here Dialogue: 0,0:43:52.00,0:43:53.00,Default,,0000,0000,0000,,for eight years. Dialogue: 0,0:43:53.00,0:43:55.00,Default,,0000,0000,0000,,So we are Dialogue: 0,0:43:55.00,0:43:58.00,Default,,0000,0000,0000,,allowing that our field's footprint has gotten so large that we need to Dialogue: 0,0:43:58.00,0:44:02.00,Default,,0000,0000,0000,,let you pick and choose a little bit to get the slice that seems most Dialogue: 0,0:44:02.00,0:44:03.00,Default,,0000,0000,0000,,appropriate for where you're headed. Dialogue: 0,0:44:03.00,0:44:06.00,Default,,0000,0000,0000,,So you'll see more about that. Dialogue: 0,0:44:06.00,0:44:10.00,Default,,0000,0000,0000,,If you are thinking about being a CS major Dialogue: 0,0:44:10.00,0:44:13.00,Default,,0000,0000,0000,,and have not yet declared, Dialogue: 0,0:44:13.00,0:44:17.00,Default,,0000,0000,0000,,I would advise Dialogue: 0,0:44:17.00,0:44:22.00,Default,,0000,0000,0000,,that you add yourself to what's called the considering CS list, Dialogue: 0,0:44:22.00,0:44:26.00,Default,,0000,0000,0000,,and you can get to this from the CS course advisor's page, Dialogue: 0,0:44:26.00,0:44:27.00,Default,,0000,0000,0000,,which, Dialogue: 0,0:44:27.00,0:44:30.00,Default,,0000,0000,0000,,off the top of my head, I think Dialogue: 0,0:44:30.00,0:44:32.00,Default,,0000,0000,0000,,it might be Dialogue: 0,0:44:32.00,0:44:36.00,Default,,0000,0000,0000,,CSadvising, but I'm not positive. I'll put the link on Dialogue: 0,0:44:36.00,0:44:39.00,Default,,0000,0000,0000,,our webpage, when I remember what it is. Dialogue: 0,0:44:39.00,0:44:42.00,Default,,0000,0000,0000,,It is a mailing list. So we have a mailing list of the declared undergrads, but we Dialogue: 0,0:44:42.00,0:44:45.00,Default,,0000,0000,0000,,also have a list for people who are Dialogue: 0,0:44:45.00,0:44:48.00,Default,,0000,0000,0000,,at least potentially interested in the major and just want to be kept up to date on Dialogue: 0,0:44:48.00,0:44:49.00,Default,,0000,0000,0000,,things that are happening. Dialogue: 0,0:44:49.00,0:44:52.00,Default,,0000,0000,0000,,There's going to be a lot of activity on this list in the Dialogue: 0,0:44:52.00,0:44:55.00,Default,,0000,0000,0000,,upcoming months as we publish the information about the new Dialogue: 0,0:44:55.00,0:44:56.00,Default,,0000,0000,0000,,curriculum. Dialogue: 0,0:44:56.00,0:44:57.00,Default,,0000,0000,0000,,So Dialogue: 0,0:44:57.00,0:45:00.00,Default,,0000,0000,0000,,you'll know what's coming down the pipes so you can make good decisions for Dialogue: 0,0:45:00.00,0:45:01.00,Default,,0000,0000,0000,,preparing for Dialogue: 0,0:45:01.00,0:45:04.00,Default,,0000,0000,0000,,what will be [inaudible], what the transition plan will be as we move into the new Dialogue: 0,0:45:04.00,0:45:05.00,Default,,0000,0000,0000,,courses Dialogue: 0,0:45:05.00,0:45:06.00,Default,,0000,0000,0000,,and how to make sure you Dialogue: 0,0:45:06.00,0:45:09.00,Default,,0000,0000,0000,,land Dialogue: 0,0:45:09.00,0:45:13.00,Default,,0000,0000,0000,,in the right place when all is said Dialogue: 0,0:45:13.00,0:45:14.00,Default,,0000,0000,0000,,and done. Then I put Dialogue: 0,0:45:14.00,0:45:15.00,Default,,0000,0000,0000,,a little note about Dialogue: 0,0:45:15.00,0:45:17.00,Default,,0000,0000,0000,,other majors that exist. Dialogue: 0,0:45:17.00,0:45:19.00,Default,,0000,0000,0000,,CS is Dialogue: 0,0:45:19.00,0:45:20.00,Default,,0000,0000,0000,, Dialogue: 0,0:45:20.00,0:45:22.00,Default,,0000,0000,0000,,the home base for people who are Dialogue: 0,0:45:22.00,0:45:25.00,Default,,0000,0000,0000,,solving problems using computers. It spans a large variety of people Dialogue: 0,0:45:25.00,0:45:27.00,Default,,0000,0000,0000,,doing a lot of different things. Dialogue: 0,0:45:27.00,0:45:30.00,Default,,0000,0000,0000,,Then there's a couple other majors that we participate in, in the interdisciplinary Dialogue: 0,0:45:30.00,0:45:32.00,Default,,0000,0000,0000,,sense, Dialogue: 0,0:45:32.00,0:45:34.00,Default,,0000,0000,0000,,that UCS is part of a larger Dialogue: 0,0:45:34.00,0:45:37.00,Default,,0000,0000,0000,,context for doing things. So computer systems engineering, which is Dialogue: 0,0:45:37.00,0:45:40.00,Default,,0000,0000,0000,,between us and EE, which is a little bit more about hardware. Dialogue: 0,0:45:40.00,0:45:43.00,Default,,0000,0000,0000,,The symbolic systems program, which is Dialogue: 0,0:45:43.00,0:45:47.00,Default,,0000,0000,0000,,run by linguistics and includes cooperation from psychology, philosophy, communications, Dialogue: 0,0:45:47.00,0:45:51.00,Default,,0000,0000,0000,,CS looking at artificial intelligence and modeling human Dialogue: 0,0:45:51.00,0:45:52.00,Default,,0000,0000,0000,,thought and Dialogue: 0,0:45:52.00,0:45:53.00,Default,,0000,0000,0000,,understanding Dialogue: 0,0:45:53.00,0:45:55.00,Default,,0000,0000,0000,, Dialogue: 0,0:45:55.00,0:45:57.00,Default,,0000,0000,0000,,intelligence as expressed in that way. Dialogue: 0,0:45:57.00,0:45:59.00,Default,,0000,0000,0000,,Then there's a mathematical computational science program that's homed Dialogue: 0,0:45:59.00,0:46:03.00,Default,,0000,0000,0000,,in the statistic department that is joint between math, computer science and the Dialogue: 0,0:46:03.00,0:46:06.00,Default,,0000,0000,0000,,MS and E. It's more of an applied math degree. So taking Dialogue: 0,0:46:06.00,0:46:08.00,Default,,0000,0000,0000,,mathematical thinking and Dialogue: 0,0:46:08.00,0:46:09.00,Default,,0000,0000,0000,, Dialogue: 0,0:46:09.00,0:46:12.00,Default,,0000,0000,0000,,using computers and statistical things to analyze and Dialogue: 0,0:46:12.00,0:46:16.00,Default,,0000,0000,0000,,think about things. A lot of financial people end up Dialogue: 0,0:46:16.00,0:46:20.00,Default,,0000,0000,0000,,being drawn to that particular one or people who are doing risk analysis or Dialogue: 0,0:46:20.00,0:46:21.00,Default,,0000,0000,0000,,that sort of Dialogue: 0,0:46:21.00,0:46:24.00,Default,,0000,0000,0000,,combination of things. But where CS has a role to play in all of these because it's a Dialogue: 0,0:46:24.00,0:46:27.00,Default,,0000,0000,0000,,great tool for solving these kind of problems. So Dialogue: 0,0:46:27.00,0:46:29.00,Default,,0000,0000,0000,,different ways to get at Dialogue: 0,0:46:29.00,0:46:30.00,Default,,0000,0000,0000,,different pieces Dialogue: 0,0:46:30.00,0:46:33.00,Default,,0000,0000,0000,,of the major. Dialogue: 0,0:46:33.00,0:46:35.00,Default,,0000,0000,0000,,I've put a couple notes of things that Dialogue: 0,0:46:35.00,0:46:38.00,Default,,0000,0000,0000,,I think are worth Dialogue: 0,0:46:38.00,0:46:39.00,Default,,0000,0000,0000,,looking into Dialogue: 0,0:46:39.00,0:46:40.00,Default,,0000,0000,0000,,in case they, Dialogue: 0,0:46:40.00,0:46:43.00,Default,,0000,0000,0000,,at some point, are the right thing for you to look at. Section leading, Dialogue: 0,0:46:43.00,0:46:45.00,Default,,0000,0000,0000,,so joining the 106 staff Dialogue: 0,0:46:45.00,0:46:46.00,Default,,0000,0000,0000,,and shepherding the next generation Dialogue: 0,0:46:46.00,0:46:49.00,Default,,0000,0000,0000,,of students through the program Dialogue: 0,0:46:49.00,0:46:52.00,Default,,0000,0000,0000,,is a great way to strengthen your own knowledge. There's nothing like Dialogue: 0,0:46:52.00,0:46:54.00,Default,,0000,0000,0000,,making sure you understand recursion as to try and explain it to someone else who Dialogue: 0,0:46:54.00,0:46:55.00,Default,,0000,0000,0000,,doesn't understand it. Dialogue: 0,0:46:55.00,0:46:56.00,Default,,0000,0000,0000,,I Dialogue: 0,0:46:56.00,0:46:59.00,Default,,0000,0000,0000,,can really do a lot for Dialogue: 0,0:46:59.00,0:47:01.00,Default,,0000,0000,0000,,the personal connection to you and your craft Dialogue: 0,0:47:01.00,0:47:04.00,Default,,0000,0000,0000,,as well as just being involved in a great community. The section leaders are a really Dialogue: 0,0:47:04.00,0:47:05.00,Default,,0000,0000,0000,,wonderful, Dialogue: 0,0:47:05.00,0:47:08.00,Default,,0000,0000,0000,,dedicated group of students who are Dialogue: 0,0:47:08.00,0:47:08.00,Default,,0000,0000,0000,, Dialogue: 0,0:47:08.00,0:47:12.00,Default,,0000,0000,0000,,fun to be around and great people to make friends with. So I Dialogue: 0,0:47:12.00,0:47:14.00,Default,,0000,0000,0000,,highly encourage you to take a look at that. Dialogue: 0,0:47:14.00,0:47:16.00,Default,,0000,0000,0000,,We interview for that every quarter, Dialogue: 0,0:47:16.00,0:47:17.00,Default,,0000,0000,0000,,so usually about week six, Dialogue: 0,0:47:17.00,0:47:19.00,Default,,0000,0000,0000,,we put out Dialogue: 0,0:47:19.00,0:47:21.00,Default,,0000,0000,0000,,applications and bring people in for interviews. We're always looking for new people Dialogue: 0,0:47:21.00,0:47:24.00,Default,,0000,0000,0000,,to join on a quarterly basis. Dialogue: 0,0:47:24.00,0:47:27.00,Default,,0000,0000,0000,,There are research opportunities all around the campus. One that the CS Dialogue: 0,0:47:27.00,0:47:30.00,Default,,0000,0000,0000,,department sponsors in particular is their [inaudible] summer institute. Dialogue: 0,0:47:30.00,0:47:33.00,Default,,0000,0000,0000,,So matching professors with undergrads to do work in the summer for Dialogue: 0,0:47:33.00,0:47:35.00,Default,,0000,0000,0000,,slave wages. Dialogue: 0,0:47:35.00,0:47:38.00,Default,,0000,0000,0000,,But great opportunity. You can get started on Dialogue: 0,0:47:38.00,0:47:40.00,Default,,0000,0000,0000,,thinking about how research might be part of your future. Dialogue: 0,0:47:40.00,0:47:43.00,Default,,0000,0000,0000,,One of the best preparations for thinking about grad school. Dialogue: 0,0:47:43.00,0:47:46.00,Default,,0000,0000,0000,,We do have an honors program. Dialogue: 0,0:47:46.00,0:47:50.00,Default,,0000,0000,0000,,Like most, we have a chance to stake out on an independent project and Dialogue: 0,0:47:50.00,0:47:50.00,Default,,0000,0000,0000,,show your mettle. Dialogue: 0,0:47:50.00,0:47:53.00,Default,,0000,0000,0000,,We have a co-terminal masters program Dialogue: 0,0:47:53.00,0:47:54.00,Default,,0000,0000,0000,,where you can Dialogue: 0,0:47:54.00,0:47:57.00,Default,,0000,0000,0000,,get some of the depth Dialogue: 0,0:47:57.00,0:47:58.00,Default,,0000,0000,0000,,before you leave this place. Dialogue: 0,0:47:58.00,0:48:01.00,Default,,0000,0000,0000,,Not to mention, there's a million fabulous Dialogue: 0,0:48:01.00,0:48:03.00,Default,,0000,0000,0000,,things to do with Stanford, getting involved with Dialogue: 0,0:48:03.00,0:48:06.00,Default,,0000,0000,0000,,arts or nonprofit organizations or sports or the student leadership Dialogue: 0,0:48:06.00,0:48:07.00,Default,,0000,0000,0000,,or whatever. Dialogue: 0,0:48:07.00,0:48:10.00,Default,,0000,0000,0000,,Maybe the most important memory I have from my undergrad was that the Dialogue: 0,0:48:10.00,0:48:13.00,Default,,0000,0000,0000,,trickiest part of my undergrad was learning what to say no to. Dialogue: 0,0:48:13.00,0:48:14.00,Default,,0000,0000,0000,,Realizing that there are Dialogue: 0,0:48:14.00,0:48:17.00,Default,,0000,0000,0000,,10,000 fabulous, worthwhile opportunities, Dialogue: 0,0:48:17.00,0:48:21.00,Default,,0000,0000,0000,,and doing all of them only means sacrificing your sanity and Dialogue: 0,0:48:21.00,0:48:23.00,Default,,0000,0000,0000,,the quality of the things you do. Dialogue: 0,0:48:23.00,0:48:24.00,Default,,0000,0000,0000,, Dialogue: 0,0:48:24.00,0:48:29.00,Default,,0000,0000,0000,,So be careful and thoughtful about choosing the things you do and embracing them. Dialogue: 0,0:48:29.00,0:48:32.00,Default,,0000,0000,0000,,Be okay with saying, I won't do this. Even though it's great to go overseas, and I Dialogue: 0,0:48:32.00,0:48:35.00,Default,,0000,0000,0000,,would've liked that opportunity, it's not going to fit, and I'm okay with that. Don't Dialogue: 0,0:48:35.00,0:48:38.00,Default,,0000,0000,0000,,beat yourself up over it and cause Dialogue: 0,0:48:38.00,0:48:41.00,Default,,0000,0000,0000,,yourself too much grief trying to do too many things. Dialogue: 0,0:48:41.00,0:48:44.00,Default,,0000,0000,0000,,I won't be here on Friday. Keith is going to come. He's going to teach you about C++ in the real Dialogue: 0,0:48:44.00,0:48:45.00,Default,,0000,0000,0000,,world. Dialogue: 0,0:48:45.00,0:48:47.00,Default,,0000,0000,0000,,I'm going to see you guys Friday at the final. Dialogue: 0,0:48:47.00,0:48:57.00,Default,,0000,0000,0000,,I think that's all I need to say for today.