0:00:00.000,0:00:13.000


0:00:13.000,0:00:16.000
This presentation is delivered by the Stanford Center for Professional

0:00:16.000,0:00:26.000
Development.

0:00:26.000,0:00:27.000
Hi, there.

0:00:27.000,0:00:29.000
It's

0:00:29.000,0:00:36.000
Wednesday. We are coming to the end of this fine quarter. So

0:00:36.000,0:00:39.000
what I'm going to do today is I

0:00:39.000,0:00:43.000
brought a cup filled with candy. We'll start with that

0:00:43.000,0:00:45.000
because that's going to be helpful. What I'd like to do is it's just a couple

0:00:45.000,0:00:50.000
bits of loose ends, some things that I wanted to touch on that

0:00:50.000,0:00:53.000
have come and gone this quarter. I maybe wanted to pull them together and reach a bit of closure

0:00:53.000,0:00:54.000
on.

0:00:54.000,0:00:57.000
Then hopefully, if we have time, we'll move on to what

0:00:57.000,0:01:00.000
happens after this. If you liked 106b, what do you do? If you don't like

0:01:00.000,0:01:01.000
106b, what do you do?

0:01:01.000,0:01:02.000


0:01:02.000,0:01:06.000
What kind of options and future opportunities are there

0:01:06.000,0:01:08.000
after this

0:01:08.000,0:01:10.000
ends? I'm going to talk a little about some of the things that

0:01:10.000,0:01:12.000
[inaudible], but I do want to talk about the final just

0:01:12.000,0:01:15.000
for a second because it is kind of a

0:01:15.000,0:01:17.000
last

0:01:17.000,0:01:19.000
opportunity for you to show us your mastery of the material

0:01:19.000,0:01:22.000
and get the grade that you've been working hard for all quarter.

0:01:22.000,0:01:26.000
It does carry a certain amount of weight. 30 percent of the weight in the default

0:01:26.000,0:01:27.000
system is actually placed on the final,

0:01:27.000,0:01:30.000
and more of it can move to that if you have a better

0:01:30.000,0:01:33.000
showing on the final than you did in the midterm. We're happy to move some of that

0:01:33.000,0:01:34.000
weight over so it could actually

0:01:34.000,0:01:36.000
account for even more of your total grade.

0:01:36.000,0:01:38.000
So there's a lot riding on it, and you want to be sure you come

0:01:38.000,0:01:40.000
ready to show us the

0:01:40.000,0:01:44.000
things that you know and that you have comprehension and mastery over.

0:01:44.000,0:01:47.000
To note, though, it is going to look a little bit different than the midterm in terms of its

0:01:47.000,0:01:51.000
emphasis. We are going to see a lot more of this nitty gritty dynamic data

0:01:51.000,0:01:52.000
structure,

0:01:52.000,0:01:53.000
Linklis, trees,

0:01:53.000,0:01:56.000
graphs, pointer-based

0:01:56.000,0:01:58.000
structures with the

0:01:58.000,0:02:01.000
inherent complications in dealing with that kind of dynamic structure. So bringing

0:02:01.000,0:02:03.000
your best game to this exam

0:02:03.000,0:02:05.000
is certainly going to pay off here. The

0:02:05.000,0:02:08.000
coding that you will see will look a lot like what's in the assignments. If you already had a

0:02:08.000,0:02:11.000
chance to look at the practice exam, you'll see that there are

0:02:11.000,0:02:13.000
themes there that echo the things you did on the work. You want to try to make sure

0:02:13.000,0:02:15.000
that's we're connecting to the

0:02:15.000,0:02:16.000


0:02:16.000,0:02:17.000
effort you've put in all along.

0:02:17.000,0:02:20.000
There will actually be some opportunity to think a little bit at a higher level

0:02:20.000,0:02:23.000
about making and analyzing choices for design and implementation. I'm going to talk a

0:02:23.000,0:02:25.000
little bit about that today because I feel like

0:02:25.000,0:02:26.000
at any given moment, we're talking about

0:02:26.000,0:02:30.000
how we might implement a stack and how we might implement a queue. Sometimes it helps to

0:02:30.000,0:02:32.000
step back a level and think a little bit about the choices for

0:02:32.000,0:02:37.000
the bigger picture of when to use a stack and queue and how to make

0:02:37.000,0:02:40.000
decisions in the large about those tradeoffs that are intelligent and

0:02:40.000,0:02:42.000
grounded. So I'll do a little bit of that today, and then

0:02:42.000,0:02:45.000
some of that has been built up all quarter long.

0:02:45.000,0:02:48.000
It is open book and open notes. You can bring all your printouts, your readers,

0:02:48.000,0:02:50.000
sections, all those sort of things.

0:02:50.000,0:02:53.000
For some people, that translates to this idea that, well, I don't need to

0:02:53.000,0:02:56.000
prepare because I'll have all my stuff there. If I need to know something

0:02:56.000,0:02:59.000
in the exam, I'll just go look it up. That's certainly true for looking up details. You want to remember how

0:02:59.000,0:03:02.000
this works or you had a piece of code that you think was similar. It could help

0:03:02.000,0:03:05.000
you to brainstorm what you're trying to do this time. But

0:03:05.000,0:03:08.000
you're not likely to have time to learn new things n the exam. So if there's

0:03:08.000,0:03:11.000
something that you really feel you have not

0:03:11.000,0:03:12.000
gotten your head around,

0:03:12.000,0:03:17.000
the investment upfront before you get into the exam is where to get that

0:03:17.000,0:03:19.000
understanding in place rather than trying, in the exam, to be flipping

0:03:19.000,0:03:22.000
through chapter ten, trying to learn something. It

0:03:22.000,0:03:23.000
may not really play out.

0:03:23.000,0:03:27.000
I highly recommend practicing on paper in an exam-like environment. So really

0:03:27.000,0:03:28.000
working

0:03:28.000,0:03:31.000
the way you will be working in the exam to give yourself

0:03:31.000,0:03:33.000
the best,

0:03:33.000,0:03:35.000
consistent prep for what's happening there.

0:03:35.000,0:03:39.000
Then some people have asked about extra problems, just wanting more of them to work on. I'll give you a

0:03:39.000,0:03:41.000
couple places where you can look for things. One is that cs106 is

0:03:41.000,0:03:44.000
being offered this same quarter, and they are just the honors version of our class.

0:03:44.000,0:03:45.000
So they have some

0:03:45.000,0:03:49.000
slightly notched up problems. But their practice and real midterm are posted on their

0:03:49.000,0:03:51.000
website as well as their practice final.

0:03:51.000,0:03:52.000


0:03:52.000,0:03:55.000
They have very similar coverage. They did some assignments that were like

0:03:55.000,0:03:58.000
ours, some that were a little bit different, but still go places to kind of

0:03:58.000,0:03:59.000
just grab

0:03:59.000,0:04:00.000
actual exam problems with their solution.

0:04:00.000,0:04:04.000
The chapter exercises and section problems often are old

0:04:04.000,0:04:05.000
exam problems or

0:04:05.000,0:04:08.000
eventually became exam problems. So they kind of come and go in terms of being used as

0:04:08.000,0:04:12.000
examples or used as exam problems. So they're definitely places to

0:04:12.000,0:04:17.000
pick up extra mileage. Okay. So let me tell

0:04:17.000,0:04:18.000
you a little bit about

0:04:18.000,0:04:21.000
- any questions about the final? Okay. Let me talk about

0:04:21.000,0:04:26.000
this line

0:04:26.000,0:04:28.000
just for a second because I feel like we have

0:04:28.000,0:04:31.000
touched on these themes again and again, but maybe it's good to have

0:04:31.000,0:04:32.000
at least one

0:04:32.000,0:04:35.000
moment of trying to pull this together and think a little bit about

0:04:35.000,0:04:38.000
the closure and the big picture of all these things.

0:04:38.000,0:04:41.000
A lot of what we're talking about in the beginning was we

0:04:41.000,0:04:44.000
were giving you these abstractions, these cool things to do stuff with, a map, a

0:04:44.000,0:04:45.000
stack, a queue, a vector,

0:04:45.000,0:04:49.000
and problems to solve where those abstractions have a role to play.

0:04:49.000,0:04:50.000
Then we spent a long time saying,

0:04:50.000,0:04:53.000
okay, now that it's our job to make those abstractions work,

0:04:53.000,0:04:56.000
what techniques can we use? What algorithms

0:04:56.000,0:04:59.000
and data structures will help us manipulate and

0:04:59.000,0:05:02.000
model those structures in efficient ways. We

0:05:02.000,0:05:05.000
certainly spent a lot of time talking about runtime performance as though that

0:05:05.000,0:05:08.000
was maybe a little too much in your mind to think that was the only thing

0:05:08.000,0:05:11.000
that really mattered. How fast can we make something? O of N is better

0:05:11.000,0:05:12.000
than N squared.

0:05:12.000,0:05:15.000
Log N is better than N, driving to these holy grails of

0:05:15.000,0:05:16.000
bringing the time down.

0:05:16.000,0:05:19.000
It's certainly a very important factor

0:05:19.000,0:05:20.000
that often -

0:05:20.000,0:05:23.000
the difference between something being linear and something being quadratic is a

0:05:23.000,0:05:27.000
matter of it being tractable at all for the problem at hand. You cannot sort a

0:05:27.000,0:05:32.000
million numbers in a quadratic sort in nearly

0:05:32.000,0:05:35.000
the same time. For large enough data sets, it'd

0:05:35.000,0:05:37.000
be completely unfeasible.

0:05:37.000,0:05:40.000
So it is important to have that big picture, to be thinking about it and know about

0:05:40.000,0:05:42.000
those tradeoffs, to understand issues

0:05:42.000,0:05:44.000
of scale here.

0:05:44.000,0:05:47.000
But we also did some stuff on the homework about actual empirical time

0:05:47.000,0:05:50.000
results, which is another way to bolster our understanding. The big O

0:05:50.000,0:05:51.000
tells us these things, but

0:05:51.000,0:05:53.000
what really happens in real life

0:05:53.000,0:05:57.000
matches it, but not precisely. Those constant factors, we threw away,

0:05:57.000,0:06:00.000
and other artifacts that are

0:06:00.000,0:06:03.000
happening in the real world often give us new insights about things and

0:06:03.000,0:06:06.000
challenges that we're facing.

0:06:06.000,0:06:09.000
We also need to think about things like mix of expected operations, having some be

0:06:09.000,0:06:11.000
slow

0:06:11.000,0:06:14.000
at the consequence of other operations being fast. It's often a tradeoff we're

0:06:14.000,0:06:16.000
willing to make.

0:06:16.000,0:06:20.000
On the editor rougher, we drove toward getting all the operations to be

0:06:20.000,0:06:23.000
fast. In an ideal world, that's certainly the best place to be, but

0:06:23.000,0:06:26.000
it's also a matter at what cost

0:06:26.000,0:06:29.000
in terms of code complexity and memory used

0:06:29.000,0:06:33.000
and effort put into it. It may be that we're willing to tolerate some operations

0:06:33.000,0:06:34.000
being less efficient

0:06:34.000,0:06:39.000
as long as the most commonly used ones are very streamlined.

0:06:39.000,0:06:42.000
We talked about these worst cases and degenerates about

0:06:42.000,0:06:45.000
knowing when we can expect our algorithms to degrade and whether we

0:06:45.000,0:06:47.000
want to do something about that

0:06:47.000,0:06:50.000
or choose a different algorithm or provide some

0:06:50.000,0:06:54.000
protection against those kind of cases coming through. To a lesser

0:06:54.000,0:06:58.000
extent, we already talked about memory used, how much overhead

0:06:58.000,0:07:01.000
there is. Seeing that we went to a pointer-based Linklis structure, we added

0:07:01.000,0:07:03.000
the four byte overhead

0:07:03.000,0:07:06.000
for every element. We went to an eight byte overhead once we got minor

0:07:06.000,0:07:10.000
[inaudible] and maybe even a little bit more if we had balance factors included.

0:07:10.000,0:07:13.000
Those things ride along with our data,

0:07:13.000,0:07:17.000
increasing the size and the memory footprint of it.

0:07:17.000,0:07:18.000
So there's a certain amount of

0:07:18.000,0:07:21.000
overhead built into this system. There's also this notion of excess capacity. To what

0:07:21.000,0:07:24.000
extent do we over allocate our

0:07:24.000,0:07:27.000
data structures early, planning for future growth. In some senses, save

0:07:27.000,0:07:32.000
ourselves that trouble of enlarging on demand. It's preparing for

0:07:32.000,0:07:33.000


0:07:33.000,0:07:34.000
a large

0:07:34.000,0:07:36.000
allotment and then using it up when we find it.

0:07:36.000,0:07:39.000
Then when we do exceed that capacity, having you do it again. So where

0:07:39.000,0:07:42.000
do we make those tradeoffs about how much excess capacity and when to do

0:07:42.000,0:07:44.000
the enlarging?

0:07:44.000,0:07:48.000
It has a lot to do with what our general memory constraints are.

0:07:48.000,0:07:51.000
I would say that memory has gotten to be quite

0:07:51.000,0:07:53.000
free

0:07:53.000,0:07:56.000
in recent processors and

0:07:56.000,0:07:58.000
computer systems. You don't really think about

0:07:58.000,0:08:01.000
100 bytes here, 200 bytes there, 1,000 bytes there. Even

0:08:01.000,0:08:05.000
megabytes, you can talk about as thought it's a drop in the bucket.

0:08:05.000,0:08:06.000


0:08:06.000,0:08:09.000
So this is something that isn't given as much weight

0:08:09.000,0:08:12.000
nowadays as it was ten years ago when there were a lot more constraints. But with

0:08:12.000,0:08:14.000
the move for a lot more imbedded device programming, and looking the

0:08:14.000,0:08:16.000
iPhone or

0:08:16.000,0:08:19.000
cell phones or things like that where they don't have that same liberty

0:08:19.000,0:08:23.000
to be wanton about memory, it's come back to being a little more careful and keeping

0:08:23.000,0:08:25.000
an eye on it.

0:08:25.000,0:08:28.000
There's also and issue here which trades off a lot with

0:08:28.000,0:08:31.000
runtime, which is redundancy versus sharing. Having

0:08:31.000,0:08:33.000
two different ways to get at the same piece of data

0:08:33.000,0:08:38.000
often will provide you with quick access. For example, if you have a

0:08:38.000,0:08:42.000
card catalogue for a library where you can look up by author, you can look up by title, you

0:08:42.000,0:08:44.000
probably are maintaining two data structures.

0:08:44.000,0:08:46.000
One that manipulates them,

0:08:46.000,0:08:49.000
sorted by title, one that manipulates them sorted by author. They're both kind

0:08:49.000,0:08:52.000
of looking at the same books in the end.

0:08:52.000,0:08:55.000
So maybe there's this set of pointers in one map over here,

0:08:55.000,0:08:58.000
indexed by author, another

0:08:58.000,0:09:00.000
keyed by title over there.

0:09:00.000,0:09:03.000
That means that I'm repeating all my data.

0:09:03.000,0:09:06.000
Hopefully I'm sharing it with a pointer, so I'm not actually really repeating all the

0:09:06.000,0:09:10.000
data, but I actually have two pointers or potentially two or more

0:09:10.000,0:09:11.000
pointers to the same book,

0:09:11.000,0:09:15.000
depending on the different ways you can get to it. That gives me that fast

0:09:15.000,0:09:17.000
access. I want to know all the books written by Leo

0:09:17.000,0:09:22.000
Lionni, I can find them easily, as well as finding all the books that have King in the

0:09:22.000,0:09:26.000
title. I don't have to do searches on a data set that's been optimized for only

0:09:26.000,0:09:27.000
one

0:09:27.000,0:09:28.000
access. Definitely,

0:09:28.000,0:09:32.000
tradeoffs were more space thrown at it to get at that fast access for

0:09:32.000,0:09:34.000
different ways.

0:09:34.000,0:09:40.000
Then this last one is one that I had mentioned along the way, but I think it's one that's easy to overlook,

0:09:40.000,0:09:42.000
which is to get very excited about how fast you can make it, how small you can

0:09:42.000,0:09:43.000
make it,

0:09:43.000,0:09:46.000
how fancy it is. It

0:09:46.000,0:09:50.000
has a real downside in terms of how hard it was to

0:09:50.000,0:09:53.000
write. Typically, when you go to these fancier strategies

0:09:53.000,0:09:54.000
that are

0:09:54.000,0:09:58.000
space efficient and time efficient, you had to pay for it somewhere.

0:09:58.000,0:10:01.000
It wasn't for free that the easy, obvious code would do that. It tends to

0:10:01.000,0:10:05.000
actually be complicated code that may use bid operations, that probably uses

0:10:05.000,0:10:06.000
more pointers

0:10:06.000,0:10:10.000
that has kind of a density to it that means it's going to take you longer to get it

0:10:10.000,0:10:12.000
right. It's going to take you more time to debug it. It's going to be more likely to

0:10:12.000,0:10:15.000
have lurking bugs. It's going to be harder to maintain.

0:10:15.000,0:10:18.000
If somebody comes along and wants to add a new operation,

0:10:18.000,0:10:21.000
they open up your code, and they're frightened away. It might be that that

0:10:21.000,0:10:23.000
code will never get

0:10:23.000,0:10:25.000
moved forward. Everybody will just open it

0:10:25.000,0:10:29.000
and close it immediately and say, whatever. We'll make it work the way it is,

0:10:29.000,0:10:33.000
rather than trying to improve it or move it forward because it actually is kind of scary

0:10:33.000,0:10:34.000
to look at.

0:10:34.000,0:10:35.000
So thinking about

0:10:35.000,0:10:37.000
what's the simplest thing that could work.

0:10:37.000,0:10:40.000
There's this movement that I think is pretty neat to think about.

0:10:40.000,0:10:43.000
There's this idea of the agile programming methodology.

0:10:43.000,0:10:44.000


0:10:44.000,0:10:45.000
It's based on the idea that

0:10:45.000,0:10:49.000
rather than planning for building the most super stellar

0:10:49.000,0:10:51.000
infrastructure for solving all the worlds problems. You're about to write a chess

0:10:51.000,0:10:53.000
program.

0:10:53.000,0:10:55.000
Actually, something that's even simpler. You're going to write a checkers program. You say,

0:10:55.000,0:10:59.000
I'm going to sit down, and I'm going to design the pieces and the board. Then you think, hey,

0:10:59.000,0:11:02.000
checkers is just one embodiment of this. Why don't I try to make the

0:11:02.000,0:11:07.000
uber board that can be used for strategic conquest or for chess or Chinese

0:11:07.000,0:11:11.000
checkers. You could have these hexagonal things. You start building this crazy

0:11:11.000,0:11:12.000
infrastructure that

0:11:12.000,0:11:15.000
could handle all of these cases equally well, even though all you really needed

0:11:15.000,0:11:18.000
was checkers, a very simple, 2D grid.

0:11:18.000,0:11:19.000
But you imagine

0:11:19.000,0:11:23.000
the future needs way in advance of having them, and then you design something

0:11:23.000,0:11:26.000
overly complicated. Then what happens is you get bogged out of that.

0:11:26.000,0:11:28.000
It never happens, and the project dies.

0:11:28.000,0:11:29.000
You

0:11:29.000,0:11:31.000
lead a lonely life

0:11:31.000,0:11:35.000
by yourself, eating oatmeal.

0:11:35.000,0:11:37.000
I like

0:11:37.000,0:11:39.000
oatmeal. So one of the mottos is

0:11:39.000,0:11:42.000
design the simplest thing that could possibly work.

0:11:42.000,0:11:46.000
I think that's a neat gift to yourself to realize that

0:11:46.000,0:11:48.000
this simplest thing that could possibly work, that meets the needs that

0:11:48.000,0:11:52.000
you have, that has a decent enough [inaudible] and memory constraint right there.

0:11:52.000,0:11:54.000
Meets your needs in the simplest form of that.

0:11:54.000,0:11:57.000
It's going to be the easiest thing to get working and running. If you later decide you want to

0:11:57.000,0:11:58.000
go fancy,

0:11:58.000,0:12:01.000
you can swap it out

0:12:01.000,0:12:06.000
using the principles of distraction and [inaudible]. It should be that it's independent

0:12:06.000,0:12:10.000
when you decide you need that fancier thing. I've got a

0:12:10.000,0:12:13.000
couple questions here because I thought this would just help us frame a little

0:12:13.000,0:12:14.000
bit of thinking about these things.

0:12:14.000,0:12:17.000
These are questions that I'm hoping you can answer for me. That's why I

0:12:17.000,0:12:18.000
brought

0:12:18.000,0:12:22.000
cup full of candy. I'm prepared to offer bribery for people who help

0:12:22.000,0:12:24.000
me answer these questions.

0:12:24.000,0:12:26.000
So let's talk about array

0:12:26.000,0:12:28.000
versus vector.

0:12:28.000,0:12:31.000
So the sequels [inaudible] builds and

0:12:31.000,0:12:35.000
array is what is behind the scenes of a vector. Then the vector adds

0:12:35.000,0:12:38.000
convenience on the outside of it.

0:12:38.000,0:12:40.000
Early on, I had said, once I tell

0:12:40.000,0:12:43.000
you about arrays,

0:12:43.000,0:12:46.000
put that back in your memory, and just use vector instead because everything array

0:12:46.000,0:12:48.000
does, vector does

0:12:48.000,0:12:53.000
nicely and cleanly and adds all sorts of features. Somebody give me a list

0:12:53.000,0:12:55.000
of things that vector does much better than

0:12:55.000,0:12:58.000
array.

0:12:58.000,0:12:59.000
Way in the back. Bounce

0:12:59.000,0:13:00.000
checking.

0:13:00.000,0:13:03.000
Bounce checking. What else? Come on. A

0:13:03.000,0:13:06.000
blow pop is on the line.

0:13:06.000,0:13:09.000
I need to interrupt your - help us

0:13:09.000,0:13:10.000
out.

0:13:10.000,0:13:11.000
You've got bounce checking. What

0:13:11.000,0:13:14.000
else? More? I want more. You've got nothing else for

0:13:14.000,0:13:17.000
me? I don't even want a blow pop. You don't want

0:13:17.000,0:13:21.000
a blow

0:13:21.000,0:13:23.000
pop? All right. I'm going to give your blow pop to somebody else. Right

0:13:23.000,0:13:27.000
here. I'm going to give the blow pop to you. Tell me what makes vector good. It has operations that

0:13:27.000,0:13:27.000
shuffle

0:13:27.000,0:13:31.000
elements for you. Yeah, it does the insert, delete, moving stuff down.

0:13:31.000,0:13:32.000
Also, it does the growing.

0:13:32.000,0:13:34.000
You keep adding, and it just grows. [Inaudible] don't do that. You

0:13:34.000,0:13:37.000
want a [inaudible] to grow, you grow it.

0:13:37.000,0:13:40.000
You take the pointer, you copy stuff over, you delete the old one, you

0:13:40.000,0:13:43.000
rearrange things. You do all the work. So

0:13:43.000,0:13:44.000
vector buys you kind of

0:13:44.000,0:13:46.000
array with benefits.

0:13:46.000,0:13:48.000
So it seems like, then,

0:13:48.000,0:13:50.000
you could kind of take away - the naive point would be like, well,

0:13:50.000,0:13:53.000
just use vector. Always use vector.

0:13:53.000,0:13:56.000
Vector's always better than array. Is there ever a situation where array still

0:13:56.000,0:13:57.000
is a pretty valid choice?

0:13:57.000,0:14:00.000
What is it array has that vector maybe doesn't?

0:14:00.000,0:14:05.000
Well, when you add things dynamically to the vector, it actually doubles the size [inaudible]

0:14:05.000,0:14:06.000
increasing it by one. If you know

0:14:06.000,0:14:10.000
the exact size, and you know it's not going to change, you're using [inaudible]. That's it exactly.

0:14:10.000,0:14:14.000
One of its big advantages. If you know you only have

0:14:14.000,0:14:17.000
- let's say you have a very small array

0:14:17.000,0:14:21.000
planned for. The one on the practice exam was, if you're doing a calendar

0:14:21.000,0:14:23.000
where you had 365 days in a year,

0:14:23.000,0:14:26.000
and you're keeping track of the events on a particular day, you know

0:14:26.000,0:14:30.000
how many days in the year. There's never going to be any change in that. Well, leap

0:14:30.000,0:14:31.000


0:14:31.000,0:14:33.000
year.

0:14:33.000,0:14:36.000
But you know that, and you know that in advance. So why fuss with a data structure that does all

0:14:36.000,0:14:39.000
this growing and shrinking and has some overhead associated with that

0:14:39.000,0:14:43.000
when, in fact, you know there's exactly this number. That's all you need.

0:14:43.000,0:14:46.000
In fact, it's almost a little bit more convenient to set up. You can

0:14:46.000,0:14:48.000
just declare it that size, and it's ready to go. With

0:14:48.000,0:14:52.000
the vector, you have to go through and add all the elements and stuff like that.

0:14:52.000,0:14:54.000
So there are a few situations where you might just say,

0:14:54.000,0:14:57.000
I don't need the advantages.

0:14:57.000,0:15:00.000
It adds some overhead that I don't want to pay,

0:15:00.000,0:15:04.000
and I'm perfectly happy making it a small fixed

0:15:04.000,0:15:07.000
array. You'll still lose bounce checking,

0:15:07.000,0:15:08.000
but

0:15:08.000,0:15:11.000
if you are being careful, maybe you're

0:15:11.000,0:15:12.000
comfortable with

0:15:12.000,0:15:15.000
making that tradeoff. By losing bounce checking, you actually are getting a little bit

0:15:15.000,0:15:18.000
of the speed improvement back. The bounce check does actually cost you

0:15:18.000,0:15:20.000
a little bit on every

0:15:20.000,0:15:23.000
vector access that an array would not actually pay.

0:15:23.000,0:15:26.000
That's really in the noise for most programs. I hesitate to

0:15:26.000,0:15:28.000
even mention it, to get you to think it matters,

0:15:28.000,0:15:31.000
but it is part of the thinking of a

0:15:31.000,0:15:34.000
professional program. Sometimes that may be the thing it comes down to,

0:15:34.000,0:15:36.000


0:15:36.000,0:15:37.000
making your operation

0:15:37.000,0:15:41.000
constant factors streamline enough for the operation you need. So I put here

0:15:41.000,0:15:44.000
stack and queue versus vector.

0:15:44.000,0:15:48.000
Given that stack and queue are really just vectors in disguise, and they're

0:15:48.000,0:15:50.000
vectors with less features, vectors

0:15:50.000,0:15:53.000
that can't do as much.

0:15:53.000,0:15:55.000
One of the implementations for stack and vector

0:15:55.000,0:15:58.000
could easily be just layered on top of a vector.

0:15:58.000,0:16:02.000
Why is it good to take away things?

0:16:02.000,0:16:06.000
[Inaudible]

0:16:06.000,0:16:08.000
tampering with contents of [inaudible]. Yeah. So it's enforcing discipline

0:16:08.000,0:16:11.000
on how you use it. Stacks are

0:16:11.000,0:16:12.000


0:16:12.000,0:16:14.000
lifo, queues are fifo.

0:16:14.000,0:16:15.000
The way things go out, they way they go out

0:16:15.000,0:16:17.000
are very

0:16:17.000,0:16:19.000
rigid. By using stack and queue,

0:16:19.000,0:16:22.000
you are guaranteeing that you won't go in and accidentally put something at the head

0:16:22.000,0:16:25.000
of the line or remove something out of the middle of the stack because you just don't

0:16:25.000,0:16:26.000
have access to that.

0:16:26.000,0:16:27.000
It's been tidied up and

0:16:27.000,0:16:29.000
packaged up into stack, which has push and pop.

0:16:29.000,0:16:31.000
queue, which has MQDQ.

0:16:31.000,0:16:34.000
No other access implied or given,

0:16:34.000,0:16:37.000
totally encapsulated from you. So in fact, it allows you to

0:16:37.000,0:16:39.000
maintain on a discipline

0:16:39.000,0:16:45.000
that otherwise the vector didn't strongly provide for you. Question? [Inaudible]. Another

0:16:45.000,0:16:48.000
thing you could do is you could optimize a stack or a

0:16:48.000,0:16:51.000
queue to be very good at the only active things you're doing, which

0:16:51.000,0:16:55.000
is pushing and popping or RQDQ. I think that's worth a smartie, don't you?

0:16:55.000,0:16:57.000
I think that is.

0:16:57.000,0:16:58.000
Exactly.

0:16:58.000,0:17:02.000
So by restricting what you have available,

0:17:02.000,0:17:05.000
it actually gives you choices in the implementation that wouldn't have worked out as well, [inaudible] full array

0:17:05.000,0:17:08.000
of operations. It's exactly true. Stack and queue only adding from one end

0:17:08.000,0:17:11.000
mean that things like a Linklis, which isn't a good choice for implementing the

0:17:11.000,0:17:13.000
general case of vector,

0:17:13.000,0:17:17.000
are perfectly good choices for the stack and queue case. So giving ourselves

0:17:17.000,0:17:22.000
some freedom as the implementer. So information about how it's being used

0:17:22.000,0:17:24.000
can pay off. It also

0:17:24.000,0:17:25.000
means when you read code - if you see

0:17:25.000,0:17:27.000
code that's using something, call the stack

0:17:27.000,0:17:31.000
or using a queue, you immediately know how it works. You could

0:17:31.000,0:17:34.000
say, here's this search that's actually stuffing a bunch of things into

0:17:34.000,0:17:37.000
a stack. I know they're last and first [inaudible].

0:17:37.000,0:17:39.000
If you see them using a vector,

0:17:39.000,0:17:42.000
you have to verify where they put them in the vector. Where do

0:17:42.000,0:17:46.000
they pull them out? The code doesn't tell you the same things. It doesn't tell you the same story

0:17:46.000,0:17:49.000
as it does when you see a word that has a strong meaning to it, like

0:17:49.000,0:17:52.000
stack and queue.

0:17:52.000,0:17:55.000
Generally, these [inaudible] to make about sorting things or not sorting things. We spent a

0:17:55.000,0:17:57.000
long time talking about sorting

0:17:57.000,0:18:01.000
and how various algorithms approach the sorting problem and what

0:18:01.000,0:18:02.000
they come up with.

0:18:02.000,0:18:05.000
I have a question here. What sorting algorithm is best? Is

0:18:05.000,0:18:09.000
there an

0:18:09.000,0:18:12.000
answer to that question? Why would I ask a question that has no answer? It depends on what you expect it

0:18:12.000,0:18:16.000
to be giving you. It depends. That's a great thing. It depends on

0:18:16.000,0:18:18.000
what you expect it to give you. How big is it?

0:18:18.000,0:18:21.000
What are the contents of it? Is it random? Is it sorted? Is it almost

0:18:21.000,0:18:24.000
sorted? Is it reverse sorted? Is it

0:18:24.000,0:18:28.000
drawn from a range of one to 1,000 values, or is it drawn from one to three

0:18:28.000,0:18:31.000
values? Huge array that has just one, two, three in it

0:18:31.000,0:18:34.000
might necessitate a different approach than one that has

0:18:34.000,0:18:36.000
one to max sine in it.

0:18:36.000,0:18:37.000
So

0:18:37.000,0:18:39.000
there is no answer to that. It is depends. What do you know? If you don't

0:18:39.000,0:18:41.000
know anything, give

0:18:41.000,0:18:43.000
it to someone else.

0:18:43.000,0:18:45.000


0:18:45.000,0:18:49.000
If you don't know, there's certain things that perform well. You know in the

0:18:49.000,0:18:52.000
average case, you don't have degenerate behaviors. For example, [inaudible] is a

0:18:52.000,0:18:56.000
great sort for the general case of an N log N that doesn't use any space

0:18:56.000,0:18:56.000


0:18:56.000,0:19:01.000
or any extra space the way word sort does. It doesn't have any degenerate cases.

0:19:01.000,0:19:02.000
For an

0:19:02.000,0:19:05.000
unknown set of inputs, it works pretty well.

0:19:05.000,0:19:08.000
If you happen to have a little bit of data, it's almost sorted.

0:19:08.000,0:19:09.000


0:19:09.000,0:19:10.000
Even

0:19:10.000,0:19:11.000
Barack Obama's

0:19:11.000,0:19:13.000
not favorite bubble sort

0:19:13.000,0:19:14.000
has a

0:19:14.000,0:19:17.000
chance of being in the run because it's already sorted. Is it worth sorting? Calculating the payoff, we had a problem on

0:19:17.000,0:19:20.000
one of the section

0:19:20.000,0:19:24.000
exercises once. I think it's a really good

0:19:24.000,0:19:25.000
one to

0:19:25.000,0:19:27.000
think through and revisit. This idea of

0:19:27.000,0:19:31.000
certain operations, many operations are much more

0:19:31.000,0:19:34.000
efficiently implemented if the data's sorted.

0:19:34.000,0:19:37.000
You can think of them off the top of your head. Oh, you want to have the minimum? If

0:19:37.000,0:19:41.000
it's sorted, it's very easy. You want the maximum? Very easy if it's sorted. You want to find the median.

0:19:41.000,0:19:43.000
Also very easy if it's sorted. You want to

0:19:43.000,0:19:44.000


0:19:44.000,0:19:48.000
find duplicates. Once they're sorted, they're all lined up together. You want to find the

0:19:48.000,0:19:49.000
mode, which is the most

0:19:49.000,0:19:50.000
frequent element.

0:19:50.000,0:19:53.000
Also easier if it's sorted because they'll all be groups together in a run. So you

0:19:53.000,0:19:57.000
can do a linear pass, counting what you see to find the longest run.

0:19:57.000,0:20:00.000
If you had two arrays and you wanted to merge them or intersect them to find

0:20:00.000,0:20:04.000
their common elements, it's much easier if they're sorted. All these things

0:20:04.000,0:20:07.000
that are hard to do when the data's in

0:20:07.000,0:20:08.000
a random order

0:20:08.000,0:20:12.000
actually have much more streamlined algorithms once you invest in sorting it.

0:20:12.000,0:20:13.000
So there was a problem that was like,

0:20:13.000,0:20:15.000
how do you know it's worth doing that?

0:20:15.000,0:20:18.000
If you only plan on writing one merge, and

0:20:18.000,0:20:19.000
you could do it in N squared,

0:20:19.000,0:20:21.000
is it worth it to

0:20:21.000,0:20:24.000
sort it, N log N, so you can get an O out of merge? So it has a lot to do

0:20:24.000,0:20:26.000
with how often you plan on doing the merge.

0:20:26.000,0:20:29.000
How big is your data set?

0:20:29.000,0:20:30.000
What are your

0:20:30.000,0:20:32.000
constraints on the times there. It

0:20:32.000,0:20:35.000
is interesting to think about that relationship. It isn't for free, but

0:20:35.000,0:20:37.000


0:20:37.000,0:20:41.000
potentially, it's an investment by sorting it so you can do a lot of fast searches

0:20:41.000,0:20:44.000
later.

0:20:44.000,0:20:47.000
This one actually is interesting because they actually solve a lot of the

0:20:47.000,0:20:50.000
same problems, and they differ in one small way. If you had a

0:20:50.000,0:20:51.000
set -

0:20:51.000,0:20:55.000
so set is being backed by a balance by a [inaudible] string that actually is a sorted data

0:20:55.000,0:20:56.000
structure internally - versus a

0:20:56.000,0:20:58.000
sorted vector.

0:20:58.000,0:21:03.000
So if your goal were to keep track of all the

0:21:03.000,0:21:07.000
students at Stanford, and you wanted to be able to look up people by name,

0:21:07.000,0:21:08.000


0:21:08.000,0:21:11.000
then the contains operation of the set

0:21:11.000,0:21:15.000
is actually doing these minor ray

0:21:15.000,0:21:16.000
search on assorted vectors

0:21:16.000,0:21:18.000
using the same path, but working through a vector.

0:21:18.000,0:21:21.000
So we can make the searching operations, like contains

0:21:21.000,0:21:23.000


0:21:23.000,0:21:24.000
and

0:21:24.000,0:21:26.000
other look-up based things,

0:21:26.000,0:21:29.000
algorithmic in both cases.

0:21:29.000,0:21:33.000
So what advantage - this sort

0:21:33.000,0:21:36.000
of vector, where I just used the interchangeably, is there something one

0:21:36.000,0:21:41.000
can do that the other can't or some advantage or disadvantage that's

0:21:41.000,0:21:43.000
assumed in that decision?

0:21:43.000,0:21:47.000
You don't have duplicates in a set, but you can have duplicates in your sorted vector. Yeah,

0:21:47.000,0:21:51.000
so the set has another concern with just how it operates. You can't put duplicates

0:21:51.000,0:21:54.000
in, so if you have two students with the same name, then

0:21:54.000,0:21:57.000
in the set, it turns out you're all coalesced down to one. Your transcripts all get

0:21:57.000,0:21:59.000
merged to your advantage or not. What

0:21:59.000,0:22:01.000
else

0:22:01.000,0:22:05.000
does set buy you that vector doesn't? How hard is it to

0:22:05.000,0:22:09.000
edit a sorted vector? You

0:22:09.000,0:22:11.000
want to put something new in there?

0:22:11.000,0:22:12.000
You're shuffling. You want to

0:22:12.000,0:22:13.000
take something out? You're shuffling.

0:22:13.000,0:22:18.000
The movement to the pointer-based structure there, the research

0:22:18.000,0:22:18.000
stream behind this,

0:22:18.000,0:22:21.000
is giving us this editability of the data structure.

0:22:21.000,0:22:25.000
The convenient logarithmic time to remove and add elements using the

0:22:25.000,0:22:28.000
pointer wiring to do that,

0:22:28.000,0:22:30.000
that vector doesn't have. That tradeoff

0:22:30.000,0:22:35.000
is actually one that

0:22:35.000,0:22:39.000
situation may be that you just don't do a lot of edits. That's actually a very common

0:22:39.000,0:22:42.000
situation. The sorted vector happens to be a very underutilized

0:22:42.000,0:22:45.000
or under appreciated arrangement

0:22:45.000,0:22:48.000
for data because for most things that are getting a lot of

0:22:48.000,0:22:49.000
edits, having a

0:22:49.000,0:22:53.000
linear time edit isn't going to be a painful

0:22:53.000,0:22:53.000
consequence.

0:22:53.000,0:22:56.000
You're doing a lot of searches, and you're getting the finer research there,

0:22:56.000,0:22:57.000
where you really care about it,

0:22:57.000,0:23:01.000
with no overhead. Very little overhead. A little bit of excess capacity,

0:23:01.000,0:23:03.000
but none of the pointer-based

0:23:03.000,0:23:06.000
trouble that came with the set. So the set actually adding onto that another eight

0:23:06.000,0:23:08.000
bytes, potentially even a little bit more,

0:23:08.000,0:23:12.000
of overhead on every element to give us that editability that maybe isn't

0:23:12.000,0:23:14.000
that important to us.

0:23:14.000,0:23:17.000
So if you're looking at that thing and saying, I'd like to be able to have

0:23:17.000,0:23:21.000
a sorted structure for both the set and the sorted vector, let you

0:23:21.000,0:23:24.000
access the elements in order. The interrater of the set goes in sort order,

0:23:24.000,0:23:27.000
going from zero to the end. The vector gives me order.

0:23:27.000,0:23:30.000
I can browse them in sort order. I can search them using sorted.

0:23:30.000,0:23:33.000
Where they differ is where does it take to edit one?

0:23:33.000,0:23:37.000
The one that invested more in the memory had faster

0:23:37.000,0:23:39.000


0:23:39.000,0:23:44.000
editing. The P-queue. This is kind of interesting. The P-queue is also a sorted structure, but not quite.

0:23:44.000,0:23:46.000


0:23:46.000,0:23:46.000


0:23:46.000,0:23:48.000
It's a much more weakly

0:23:48.000,0:23:52.000
sorted structure. So if you're using the [inaudible] heap like we did on the

0:23:52.000,0:23:53.000
P-queue

0:23:53.000,0:23:55.000
[inaudible], it does give you this access to the maximum value,

0:23:55.000,0:23:59.000
and then kind of a quick reshuffling [inaudible] the next

0:23:59.000,0:24:00.000
and so on.

0:24:00.000,0:24:02.000
But it doesn't really give you the full range. For example, if you

0:24:02.000,0:24:10.000
were looking for the minimum in a P-queue, where is it?

0:24:10.000,0:24:11.000
It's somewhere in the

0:24:11.000,0:24:14.000
bottom. It's in the bottom-most level, but where across the bottom,

0:24:14.000,0:24:16.000
no knowledge, right? It could be

0:24:16.000,0:24:20.000
at any of the nodes that are at the bottom of the heap. So in fact it

0:24:20.000,0:24:21.000
gives you this access to

0:24:21.000,0:24:23.000
a partial

0:24:23.000,0:24:26.000
ordering of the data. In this case, it's relative

0:24:26.000,0:24:28.000
to the prioritization, but not

0:24:28.000,0:24:31.000
the fluid form of sorting the way a vector is. For example,

0:24:31.000,0:24:33.000
if P-queue doesn't give you things for

0:24:33.000,0:24:35.000
finding duplicates or finding the minimum or

0:24:35.000,0:24:39.000
doing the mode it's not actually an easy operation because you have

0:24:39.000,0:24:42.000
it in a heap form. I can get to the max

0:24:42.000,0:24:42.000
quickly.

0:24:42.000,0:24:46.000
So if I cared about pulling them out in sorted order

0:24:46.000,0:24:47.000
to browse them,

0:24:47.000,0:24:51.000
I could stuff things into a P-queue and then pull them out, but what's interesting about that is

0:24:51.000,0:24:54.000
it requires destroying the P-queue.

0:24:54.000,0:24:57.000
The P-queue isn't really a place you store things and plan on using them again. It's

0:24:57.000,0:25:00.000
the place you stick things in order to get them out

0:25:00.000,0:25:02.000
in an order that's only

0:25:02.000,0:25:05.000
value is in the de-queuing of them, pulling them out.

0:25:05.000,0:25:10.000
So finding the most promising option to look at in a search or finding the most

0:25:10.000,0:25:13.000
high-priority activity to take on or something.

0:25:13.000,0:25:16.000
But it doesn't really have the - if I wanted to be able to look at all

0:25:16.000,0:25:18.000
the students in my class in sorted order,

0:25:18.000,0:25:20.000
it's like, well, I could stick them in a P-queue and then pull them out, but it's sort of

0:25:20.000,0:25:25.000
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

0:25:25.000,0:25:27.000
browsing operation to be easily repeated.

0:25:27.000,0:25:29.000
If I put them into a sorted vector, I could just keep

0:25:29.000,0:25:33.000
iterating over it whenever I need to see it again.

0:25:33.000,0:25:37.000
So a lot of the things that it comes down to is having a pretty good

0:25:37.000,0:25:41.000
visualization of what it is that going to a pointer-based data structure buys you, and

0:25:41.000,0:25:44.000
what it costs you, relative to the continuous memory. That's one of the

0:25:44.000,0:25:45.000


0:25:45.000,0:25:48.000
tensions underneath most of these things. It's like,

0:25:48.000,0:25:50.000
putting more memory into it

0:25:50.000,0:25:54.000
by virtue of having a pointer wire as opposed to a

0:25:54.000,0:25:55.000
location

0:25:55.000,0:25:57.000
arrangement.

0:25:57.000,0:26:00.000
There's no information that's stored to get you from a race of zero to a

0:26:00.000,0:26:04.000
race of two. They're just continuous in memory. So it saves you space because you only

0:26:04.000,0:26:07.000
have to know where it starts and access continuously for that. This pointer means

0:26:07.000,0:26:11.000
there's more kerversals. There's more memory. There's more opportunity

0:26:11.000,0:26:12.000
to air, but it gave

0:26:12.000,0:26:16.000
you this flexibility. It broke down this continuous block, that's kind

0:26:16.000,0:26:17.000
of a monolith,

0:26:17.000,0:26:21.000
into these pieces that are more flexible in how you can rearrange

0:26:21.000,0:26:25.000
them. So thinking about these things is

0:26:25.000,0:26:28.000
an important skill to come away from 106b with that,

0:26:28.000,0:26:30.000
yeah, there's never

0:26:30.000,0:26:31.000
one right answer.

0:26:31.000,0:26:33.000


0:26:33.000,0:26:36.000
You're investing to solve this other problem, and

0:26:36.000,0:26:40.000
there's going to be downsides. There's no

0:26:40.000,0:26:41.000
obvious

0:26:41.000,0:26:43.000
triumph over all.

0:26:43.000,0:26:47.000
It's fast, it's cheap and it's small and easy to write

0:26:47.000,0:26:51.000
solutions out there.

0:26:51.000,0:26:53.000
So I put up here - I had to

0:26:53.000,0:26:54.000
whittle

0:26:54.000,0:26:57.000
this down to the five or six things that, at

0:26:57.000,0:27:02.000
the end of 106b, I want you to feel like, that's what I got.

0:27:02.000,0:27:04.000
That's the heart of

0:27:04.000,0:27:05.000


0:27:05.000,0:27:06.000
the

0:27:06.000,0:27:10.000
goal. The MVPs - the most valuable players of the

0:27:10.000,0:27:12.000
106b curriculum here.

0:27:12.000,0:27:15.000
You're looking back at it, and you go, where did I start, where did I end up,

0:27:15.000,0:27:18.000
and how did my knowledge grow?

0:27:18.000,0:27:21.000
I'm hoping these are the things that stand out for you. That was a

0:27:21.000,0:27:23.000
real

0:27:23.000,0:27:24.000
growth area for me. One

0:27:24.000,0:27:27.000
is this idea of abstraction.

0:27:27.000,0:27:32.000
That was stressed early on. Here's a stack, here's a queue, here's a set. They

0:27:32.000,0:27:33.000
do things for you. We don't know how

0:27:33.000,0:27:34.000
they work yet,

0:27:34.000,0:27:38.000
but you make cool things happen with them. So you solve maze problems and

0:27:38.000,0:27:40.000
random writers and

0:27:40.000,0:27:43.000
do neat things with

0:27:43.000,0:27:47.000
dictionaries without knowing how they work. So you're leveraging existing

0:27:47.000,0:27:48.000
material without knowledge of how it works.

0:27:48.000,0:27:52.000
It helps to keep the complexity down. You can solve much more interesting problems

0:27:52.000,0:27:56.000
than you could without them. Try to go back and imagine the Markov random writer

0:27:56.000,0:27:57.000
problem.

0:27:57.000,0:27:58.000
Now imagine doing it

0:27:58.000,0:28:00.000


0:28:00.000,0:28:02.000
without the map in play. So

0:28:02.000,0:28:04.000
you had to figure out that

0:28:04.000,0:28:08.000
given this character, go look it up and find a place to store it, and

0:28:08.000,0:28:11.000
then store the character in some other array that was growing on

0:28:11.000,0:28:14.000
demand, as you put stuff in there. You would never have completed that

0:28:14.000,0:28:18.000
program. You would still be writing it today, having pointer errors and whatnot

0:28:18.000,0:28:19.000
behind the scenes.

0:28:19.000,0:28:22.000
Having those tools already there, it's like having

0:28:22.000,0:28:25.000
the microwave and the food processor, and you're about to cook instead

0:28:25.000,0:28:26.000
of having a

0:28:26.000,0:28:27.000
dull knife

0:28:27.000,0:28:31.000
and doing all your work with a

0:28:31.000,0:28:31.000
dull

0:28:31.000,0:28:34.000
knife and a fire. You actually have

0:28:34.000,0:28:36.000
some real power

0:28:36.000,0:28:39.000
there. Recursion's a big theme in the weeks that followed that.

0:28:39.000,0:28:41.000
How to solve these problems that

0:28:41.000,0:28:43.000
have this similar structure,

0:28:43.000,0:28:47.000
looking at these exhaustive traversals and choice problems that can

0:28:47.000,0:28:51.000
be solved with backtracking. Having this idea of how to think about thing [inaudible]

0:28:51.000,0:28:53.000
using the recursive problem solving

0:28:53.000,0:28:55.000
and how to model

0:28:55.000,0:28:56.000
that

0:28:56.000,0:28:59.000
process using the computer was a

0:28:59.000,0:29:02.000
very important thing that comes back. We look at algorithm

0:29:02.000,0:29:05.000
analysis, this idea of making this

0:29:05.000,0:29:08.000
sloppy map that computer scientists are

0:29:08.000,0:29:11.000
fond of, talking about the scalability and growth, knowing about curves and

0:29:11.000,0:29:13.000
the relationships and how to

0:29:13.000,0:29:16.000
look at algorithms. The more formal analysis.

0:29:16.000,0:29:17.000
Still, in this case, there's still quite

0:29:17.000,0:29:21.000
a bit more formulas to this than we really went into. If you

0:29:21.000,0:29:23.000
were go on in CS and look at it, you will see there's quite a lot

0:29:23.000,0:29:26.000
of rigor that can be

0:29:26.000,0:29:27.000
looked at in that area.

0:29:27.000,0:29:31.000
We were getting more an intuition for how to gauge things about algorithms and

0:29:31.000,0:29:33.000
their growth.

0:29:33.000,0:29:36.000
Then this backside, all about implementation strategies and tradeoffs.

0:29:36.000,0:29:38.000
So now that we've

0:29:38.000,0:29:40.000
benefited from those abstractions, and we've

0:29:40.000,0:29:43.000
solved some cool problems, what's it like to actually be the person building them? What

0:29:43.000,0:29:46.000
are the techniques? What does it take to

0:29:46.000,0:29:50.000
wrestle a pointer or a Linklis or a tree, heap graph into doing something really cool for you. How

0:29:50.000,0:29:52.000
does that

0:29:52.000,0:29:57.000
inform your information, what you expect about it and the

0:29:57.000,0:30:00.000
coding complexity that was inherent in achieving that result?

0:30:00.000,0:30:04.000
Hopefully in continuing with the theme that 106a started you on was this

0:30:04.000,0:30:07.000
appreciation for [inaudible]. In the

0:30:07.000,0:30:11.000
end, getting code that works, that's ugly, just

0:30:11.000,0:30:14.000
isn't, hopefully, what you're satisfied with. You want to

0:30:14.000,0:30:17.000
approach problem solving to produce beautiful, elegant,

0:30:17.000,0:30:19.000
unified, clean,

0:30:19.000,0:30:20.000
readable code

0:30:20.000,0:30:24.000
that you would be happy to show to other people and be proud of and

0:30:24.000,0:30:25.000
maintain and live with.

0:30:25.000,0:30:27.000
The kind of work that

0:30:27.000,0:30:29.000
other people you work with would appreciate

0:30:29.000,0:30:32.000
being involved with.

0:30:32.000,0:30:34.000
Things that are not so much

0:30:34.000,0:30:37.000
- I don't think these are the most valuable pointers, but what

0:30:37.000,0:30:38.000
came along the way,

0:30:38.000,0:30:39.000


0:30:39.000,0:30:42.000
the idea of pointers and C++ being part of the -

0:30:42.000,0:30:45.000
C++ and its pointers, they're one and the same. We choose [inaudible] for a

0:30:45.000,0:30:48.000
language, so as a result, we get to learn some C++

0:30:48.000,0:30:51.000
because it's so heavily

0:30:51.000,0:30:53.000
invested with pointers. We also have to do some practice with the pointers to

0:30:53.000,0:30:55.000
get our jobs done.

0:30:55.000,0:30:58.000
I think of those as being off to the side. I don't think of those being the

0:30:58.000,0:31:01.000
platform of things I worship. They are

0:31:01.000,0:31:05.000
things we need to get our job done. I

0:31:05.000,0:31:08.000
did put a little note about pointers here because there were quite a lot of comments on

0:31:08.000,0:31:12.000
the mid-quarter evals that said, pointers, pointers still scare me. They make me crazy.

0:31:12.000,0:31:14.000
I don't know enough about

0:31:14.000,0:31:15.000
pointers. Here's a fact for you.

0:31:15.000,0:31:18.000
You'll probably never feel like you know enough about pointers.

0:31:18.000,0:31:21.000
Today, tomorrow, ten years from now, you'll still kind of feel like

0:31:21.000,0:31:24.000
there's some real subtlety and trickiness in there.

0:31:24.000,0:31:27.000
They're an extremely powerful facility that gives you that

0:31:27.000,0:31:31.000
direct control over allocation and deallocation and all the wiring and

0:31:31.000,0:31:32.000
sharing

0:31:32.000,0:31:34.000
that

0:31:34.000,0:31:37.000
is important to building these complicated data structures.

0:31:37.000,0:31:40.000
But there are so many pitfalls. I'm sure you've run into

0:31:40.000,0:31:43.000
most of these, if not all of them at some point, where you

0:31:43.000,0:31:46.000
mishandled a pointer, failed the allocator, deallocate,

0:31:46.000,0:31:49.000
and

0:31:49.000,0:31:52.000
the way it gets reported, whether the compiler or the runtime error that

0:31:52.000,0:31:56.000
you see is helpful in sorting it out is a real cause for

0:31:56.000,0:31:58.000
long hours to disappear

0:31:58.000,0:32:01.000
in the name of mastery of this.

0:32:01.000,0:32:02.000
If you're still wary of pointers, you

0:32:02.000,0:32:04.000
probably should be.

0:32:04.000,0:32:06.000
Think of this as your first go-around.

0:32:06.000,0:32:07.000
We're still

0:32:07.000,0:32:10.000
at the journeyman's stage for programming here.

0:32:10.000,0:32:14.000
So although there were pointers in 106a, they were very hidden. This

0:32:14.000,0:32:17.000
is the first time you really see it and are exposed to it and trying to get your head

0:32:17.000,0:32:18.000
around it.

0:32:18.000,0:32:20.000
If you go on to 107 and 108, you'll just

0:32:20.000,0:32:23.000
get more and more practice. It will

0:32:23.000,0:32:26.000
become more solid as you keep working your way through it, but

0:32:26.000,0:32:30.000
at this stage, it's okay

0:32:30.000,0:32:31.000
and

0:32:31.000,0:32:35.000
commonplace to feel still, a little bit - you see the star, and you take a

0:32:35.000,0:32:37.000
double take. That's just where you should be.

0:32:37.000,0:32:40.000
It's just like in the

0:32:40.000,0:32:43.000
Chinese restaurants. They put the little red star by food you want to be

0:32:43.000,0:32:49.000
careful of. That's why they put the star for the

0:32:49.000,0:32:52.000
pointer. I also wanted to

0:32:52.000,0:32:54.000
zoom out farther,

0:32:54.000,0:32:56.000
a decade from

0:32:56.000,0:32:59.000
now, when you are

0:32:59.000,0:33:01.000
thinking back on the

0:33:01.000,0:33:04.000
whole of your education and what you learned. Do I want to really

0:33:04.000,0:33:06.000
remember how to

0:33:06.000,0:33:08.000
type in keyword and the sequel plus generic

0:33:08.000,0:33:10.000
template facility? No.

0:33:10.000,0:33:13.000
If you code in C++ every day, you'll know that. If you don't, you

0:33:13.000,0:33:14.000
can forget it. It's long gone.

0:33:14.000,0:33:16.000
What I hope you'll carry away from you

0:33:16.000,0:33:18.000
is a couple

0:33:18.000,0:33:19.000
concepts that

0:33:19.000,0:33:21.000
broaden

0:33:21.000,0:33:23.000
outside of CS. One is this idea of algorithmic thinking,

0:33:23.000,0:33:27.000
how you approach something logically and step-wise and draw pictures and analyze it to understand

0:33:27.000,0:33:29.000
the cases

0:33:29.000,0:33:32.000
and to debug when things aren't working well. I think that's a skill that

0:33:32.000,0:33:33.000
transcends

0:33:33.000,0:33:37.000
the art of computer programming into other domains, any kind of thinking

0:33:37.000,0:33:39.000
logically and problem solving and analyzing in that

0:33:39.000,0:33:43.000
way. I also hope that some of the experimental things we did with the sort

0:33:43.000,0:33:45.000
lab and the P-queue

0:33:45.000,0:33:48.000
and some of the big O and thing we tried to do in class together help

0:33:48.000,0:33:51.000
you to [inaudible] back of the envelope calculations. This is something I'm

0:33:51.000,0:33:53.000
a little bit of a -

0:33:53.000,0:33:55.000
it's a pet issue of mine, which is,

0:33:55.000,0:33:57.000
I think, in the era of computers

0:33:57.000,0:34:00.000
and whatnot, really easy to get distanced from numbers and start

0:34:00.000,0:34:03.000
thinking, I just punch numbers into formulas and one comes out. It must be

0:34:03.000,0:34:06.000
the truth. Not having any intuition as to whether that's the right

0:34:06.000,0:34:10.000
number, whether that number makes sense, whether it's grounded,

0:34:10.000,0:34:14.000
and whether you actually are [inaudible] or so off because you've

0:34:14.000,0:34:17.000
actually made an entry error, and you don't even notice it.

0:34:17.000,0:34:20.000
So becoming comfortable with this idea of using numbers to drive things,

0:34:20.000,0:34:21.000
being able to

0:34:21.000,0:34:26.000
take some time trials, do some predictions, do some more time trials,

0:34:26.000,0:34:28.000
match those things up, do a little sketching on your numbers and see the

0:34:28.000,0:34:32.000
things that are working out. So being comfortable having the math and the theory

0:34:32.000,0:34:34.000
reinforce each other

0:34:34.000,0:34:34.000
and

0:34:34.000,0:34:36.000
not get too

0:34:36.000,0:34:39.000
distanced from the fact that those numbers do play out in

0:34:39.000,0:34:42.000
the real world in ways that are interesting. Don't just let the numbers themselves

0:34:42.000,0:34:44.000
tell the story. There really is more

0:34:44.000,0:34:47.000
to connect it up with.

0:34:47.000,0:34:49.000
This idea of tradeoffs.

0:34:49.000,0:34:51.000
You may not remember

0:34:51.000,0:34:54.000
how you can write a Linklis or how the hash table does

0:34:54.000,0:34:56.000
the things it does

0:34:56.000,0:35:00.000
and how to get one working, but hopefully you will take away this idea that

0:35:00.000,0:35:03.000
the answer to most questions begins with the phrase, it depends.

0:35:03.000,0:35:05.000
If I say, is it better to use a hash table or [inaudible] search tree, the answer

0:35:05.000,0:35:09.000
will be, it depends. There's no,

0:35:09.000,0:35:12.000
it's always better to use this sort. It's always

0:35:12.000,0:35:14.000
wrong to use this approach.

0:35:14.000,0:35:15.000
It's, it depends. Do

0:35:15.000,0:35:18.000
you have the code written for that, and it works well, and you don't care how

0:35:18.000,0:35:19.000
long it takes?

0:35:19.000,0:35:23.000
Then bubble sort actually could be the right answer.

0:35:23.000,0:35:25.000
Barack Obama not withstanding.

0:35:25.000,0:35:27.000
But knowing whether memory is

0:35:27.000,0:35:32.000
at premium, time is at premium, what your mix of operations are,

0:35:32.000,0:35:33.000
what

0:35:33.000,0:35:34.000
language you're working with, what

0:35:34.000,0:35:38.000
program expertise you have, what timeline you have for developing it all

0:35:38.000,0:35:42.000
can play a role in deciding what choices to make and what strategy to pursue.

0:35:42.000,0:35:45.000
So being very comfortable with this idea that it's about gathering information

0:35:45.000,0:35:46.000
before you

0:35:46.000,0:35:49.000
can commit to one strategy as opposed to it's always going to be

0:35:49.000,0:35:52.000
this or that.

0:35:52.000,0:35:54.000
So that's the 106b thing.

0:35:54.000,0:35:57.000
I have a couple slides here on

0:35:57.000,0:35:59.000
things that happen after 106b. I'm

0:35:59.000,0:36:01.000
just going to go ahead and show you.

0:36:01.000,0:36:03.000


0:36:03.000,0:36:06.000
This would be a great time to ask questions. In particular, if there's anything you're

0:36:06.000,0:36:07.000
curious about.

0:36:07.000,0:36:10.000
Where do we go from here, and

0:36:10.000,0:36:13.000
how do we make good decisions about things that follow? The

0:36:13.000,0:36:17.000
most obvious following courses from CS - if you took 106b

0:36:17.000,0:36:19.000
and you hated it, I'm very sorry.

0:36:19.000,0:36:23.000
Hopefully

0:36:23.000,0:36:25.000
the scarring

0:36:25.000,0:36:26.000
will heal over and you'll lead a

0:36:26.000,0:36:28.000
productive and happy life

0:36:28.000,0:36:30.000
elsewhere. If you did like it and you think,

0:36:30.000,0:36:33.000
I'm kind of interested in this. What do I do next to explore further?

0:36:33.000,0:36:35.000
Where else can I go with this?

0:36:35.000,0:36:38.000
I put up the intro

0:36:38.000,0:36:40.000
courses with their numbers and names, and I'll talk a little bit

0:36:40.000,0:36:44.000
about what each of these does to give you an idea of what opportunity it

0:36:44.000,0:36:45.000
offers to you.

0:36:45.000,0:36:49.000
The obvious follow onto the programming side - 106a and b

0:36:49.000,0:36:51.000
are programming courses, building your programming mastery.

0:36:51.000,0:36:54.000
107 follow in the same vein. We typically call those systems

0:36:54.000,0:36:56.000
courses in CS nomenclature.

0:36:56.000,0:36:59.000
That means practical, hands on programming, getting more exposure

0:36:59.000,0:37:00.000
to the system.

0:37:00.000,0:37:05.000
So 107 builds on 106b's knowledge in a class called programming paradigms.

0:37:05.000,0:37:08.000
Part of what it's trying to explore is different languages.

0:37:08.000,0:37:11.000
So you actually look at the language, C, kind of stepping back to old school.

0:37:11.000,0:37:15.000
You look at the language scheme, which is a functional language that

0:37:15.000,0:37:17.000
was developed for AI purposes

0:37:17.000,0:37:17.000
that

0:37:17.000,0:37:21.000
has a long history coming from the math side of things. Probably looking at some

0:37:21.000,0:37:25.000
scripting and flexible [inaudible] like Python. We kind of mix them up a

0:37:25.000,0:37:28.000
little bit, so it's not exactly the same things, but looking at other

0:37:28.000,0:37:30.000
languages, other ways of doing things.

0:37:30.000,0:37:33.000
The other component of 107 is also looking at

0:37:33.000,0:37:35.000
some more low-level things.

0:37:35.000,0:37:37.000
What happens? When you

0:37:37.000,0:37:41.000
pass your code off to the compiler, what is it doing? What kind of analysis does do of your

0:37:41.000,0:37:44.000
code? How does it actually generate machine code? What happens in the machine layer,

0:37:44.000,0:37:47.000
understanding some more of the performance implications

0:37:47.000,0:37:50.000
and how things are expressed. Getting a better understanding of pointers actually

0:37:50.000,0:37:53.000
comes up because there is a certain amount of low-level coding that's being

0:37:53.000,0:37:54.000
explored in this class.

0:37:54.000,0:37:58.000
So building on the programming skill as we move toward a Unix

0:37:58.000,0:38:00.000
Linux-based

0:38:00.000,0:38:02.000
environment. So away from the Mac and Windows.

0:38:02.000,0:38:03.000


0:38:03.000,0:38:08.000
Just continue building larger programs with complicated

0:38:08.000,0:38:10.000
features to grow your mastery.

0:38:10.000,0:38:13.000
Internally, we call this class programming maturity, even though

0:38:13.000,0:38:14.000
it's not its title.

0:38:14.000,0:38:18.000
We see it that way in the sequence in terms of just growing you into

0:38:18.000,0:38:19.000
a

0:38:19.000,0:38:22.000
more versatile programmer, seeing different languages, different things

0:38:22.000,0:38:25.000
and getting more understanding of what happens under the hood.

0:38:25.000,0:38:29.000
It is a five-unit class. It's typically offered fall and spring. Most

0:38:29.000,0:38:30.000
people thing it is

0:38:30.000,0:38:33.000
about as much work as 106b. Some a

0:38:33.000,0:38:37.000
little more or a little less in different parts of the quarter, depending on what your

0:38:37.000,0:38:38.000
background is and

0:38:38.000,0:38:39.000


0:38:39.000,0:38:41.000
how 106b worked for you.

0:38:41.000,0:38:44.000
In a model, I think most people think of it as being - would you guys

0:38:44.000,0:38:45.000
say 107

0:38:45.000,0:38:48.000
about as hard as 106b?

0:38:48.000,0:38:51.000
Some ways, it's harder. Some ways, it's not. Maybe that's

0:38:51.000,0:38:55.000
the deal. The 108 class which follows onto 107, but that

0:38:55.000,0:38:57.000
prerequisite is particularly strong. It's a Java class.

0:38:57.000,0:39:00.000
So moving in the other direction. Rather than moving down an extraction, moving

0:39:00.000,0:39:02.000
up on the extraction,

0:39:02.000,0:39:05.000
looking at more large-scale design, modern programming technique,

0:39:05.000,0:39:06.000
using

0:39:06.000,0:39:10.000
object-oriented facilities, thinking about large-scale programming. You do a

0:39:10.000,0:39:11.000
big team project in the

0:39:11.000,0:39:13.000
end, so a three week,

0:39:13.000,0:39:15.000
three person, massive effort

0:39:15.000,0:39:17.000
that is the first

0:39:17.000,0:39:26.000
really big scale thing that you'll be exposed to in the lower-division

0:39:26.000,0:39:30.000
curriculum. [Inaudible]. Sometimes in 107l, which has some relationship to the

0:39:30.000,0:39:33.000
106l in the way that it's more hands-on, more

0:39:33.000,0:39:34.000
C++,

0:39:34.000,0:39:37.000
I don't know whether it will be offered this spring or not,

0:39:37.000,0:39:38.000
but

0:39:38.000,0:39:41.000
if you look in Access, it will tell you at least whether we have it tentatively on

0:39:41.000,0:39:42.000
the schedule.

0:39:42.000,0:39:46.000
I think that comes and goes with the interest from the students and the

0:39:46.000,0:39:51.000
availability of someone to teach

0:39:51.000,0:39:52.000
it.

0:39:52.000,0:39:55.000
[Inaudible] can we watch [inaudible]?

0:39:55.000,0:39:58.000
Yeah, 107 and 108 are offered on TV usually

0:39:58.000,0:40:02.000
once a year. 107 is offered on TV this spring. The one in fall is

0:40:02.000,0:40:03.000
not taped.

0:40:03.000,0:40:06.000
It might be that the old lectures from spring are somewhere that

0:40:06.000,0:40:09.000
you could dig them out, but I actually don't happen to know for sure.

0:40:09.000,0:40:11.000
108 is on TV, I think,

0:40:11.000,0:40:13.000
in the fall, not in the winter. So the fall lectures are probably still around for

0:40:13.000,0:40:16.000
108, so you could take a look at them. You

0:40:16.000,0:40:19.000
could certainly look at their websites, and

0:40:19.000,0:40:23.000
there's often a lot of old materials and handouts

0:40:23.000,0:40:26.000
and stuff that gives you at least some idea of things that have been

0:40:26.000,0:40:29.000
covered in the most recent offering of it.

0:40:29.000,0:40:34.000
Certainly showing up in the first week is one way to get an

0:40:34.000,0:40:36.000
idea of what you're in for.

0:40:36.000,0:40:38.000
108 is a four-unit class.

0:40:38.000,0:40:41.000
Because it's in Java, there's certain things about Java,

0:40:41.000,0:40:44.000
the safety and

0:40:44.000,0:40:48.000
the attentiveness of the compiler, makes the error handing a little

0:40:48.000,0:40:52.000
bit easier. So I don't think most people think of 108 as quite as intense as

0:40:52.000,0:40:55.000
107 or 106b, but that project at the end has quite a reputation

0:40:55.000,0:40:58.000
as being a

0:40:58.000,0:41:02.000
real time suck. So it has lots to do with being

0:41:02.000,0:41:04.000
scheduled and motivated and working through that team project at

0:41:04.000,0:41:05.000
the end.

0:41:05.000,0:41:09.000
I think that's where most people find the big challenge of

0:41:09.000,0:41:12.000
108. Then on the math side, in the

0:41:12.000,0:41:15.000
nomenclature for CS, we have this idea of theory, introducing you to more

0:41:15.000,0:41:16.000


0:41:16.000,0:41:19.000
the formalism for big O and discrete structures and doing proofs and

0:41:19.000,0:41:21.000
thinking about logic.

0:41:21.000,0:41:25.000
So we have a 103 a and b and a 103x, which is a combined,

0:41:25.000,0:41:28.000
accelerated form of a and b, which serves as math classes. They are math classes

0:41:28.000,0:41:29.000
for introducing

0:41:29.000,0:41:33.000
the kind of mathematics that are important for computer scientists.

0:41:33.000,0:41:34.000
So that is

0:41:34.000,0:41:38.000
for people who are thinking about a CS major, another good course to get in

0:41:38.000,0:41:39.000
early. Pretty

0:41:39.000,0:41:43.000
much everything in the upper division of the CS major has

0:41:43.000,0:41:47.000
these things layered down as prereqs. So these are the intro courses that serve as the

0:41:47.000,0:41:50.000
gateway to prepping you to go on, and then looking at things in a more topical

0:41:50.000,0:41:51.000
way.

0:41:51.000,0:41:53.000
Looking at networks or security,

0:41:53.000,0:41:54.000
HCI or

0:41:54.000,0:41:59.000
artificial intelligence layers on a grounding in theory and programming

0:41:59.000,0:42:03.000
that came from the intro courses. So

0:42:03.000,0:42:07.000
that said, we're in the

0:42:07.000,0:42:08.000
midst of a really

0:42:08.000,0:42:10.000
serious curriculum revision,

0:42:10.000,0:42:13.000
which is

0:42:13.000,0:42:15.000
on the table and being designed right now,

0:42:15.000,0:42:18.000
and was voted on by our faculty and improved and has to go

0:42:18.000,0:42:22.000
through the school of engineering and get approval. Then there's going to be a little bit of

0:42:22.000,0:42:23.000
jostling as everything gets worked out.

0:42:23.000,0:42:27.000
But started next year, you're going to see some changes in the

0:42:27.000,0:42:29.000
department. Some of these courses are going to

0:42:29.000,0:42:33.000
get morphed, and

0:42:33.000,0:42:36.000
they won't be exactly the way they are today.

0:42:36.000,0:42:39.000
As a Stanford undergrad, you actually have the option of graduating under any set of

0:42:39.000,0:42:42.000
requirements that are in play any time you're an undergrad. So you could graduate under this year's

0:42:42.000,0:42:43.000
requirements,

0:42:43.000,0:42:45.000
or you could wait.

0:42:45.000,0:42:48.000
I think for most, the right answer's going to be wait because I think the new

0:42:48.000,0:42:51.000
arrangement is very much more student-friendly.

0:42:51.000,0:42:53.000
It has more flexibility

0:42:53.000,0:42:57.000
in the program. If you look at the CS program as it is, it has a lot of pick

0:42:57.000,0:43:00.000
one of two, pick one of three, pick one of two,

0:43:00.000,0:43:04.000
where you're very constrained on what you can choose. The new program is going to be

0:43:04.000,0:43:07.000
more track-based where you pick an area of interest. You say, I'm really interested in the

0:43:07.000,0:43:08.000
graphics. You do a little

0:43:08.000,0:43:12.000
depth concentration in that, and then just have room for a

0:43:12.000,0:43:15.000
very wide selection of electives to fill up the program as opposed to

0:43:15.000,0:43:19.000
a smorgasbord where we forced you to pick through a bunch of different areas.

0:43:19.000,0:43:24.000
So for most students, I think it gives you flexibility that actually gives you

0:43:24.000,0:43:25.000
the options

0:43:25.000,0:43:26.000
to

0:43:26.000,0:43:30.000
pick the classes that are most interesting to you and get the material that you want. It's a growing

0:43:30.000,0:43:32.000
recognition of the fact that CS

0:43:32.000,0:43:35.000
has really broadened as a field. Some say that our major looks the same way

0:43:35.000,0:43:37.000
it did ten years ago,

0:43:37.000,0:43:40.000
a classic definition of here's these

0:43:40.000,0:43:42.000
seven things that all matter. The

0:43:42.000,0:43:45.000
things aren't seven anymore. There's no 15 of them, 25 of them. If

0:43:45.000,0:43:49.000
you look at the spectrum of things that computer science is now

0:43:49.000,0:43:52.000
embracing, we can't say, you have to take one of all these things without keeping you here

0:43:52.000,0:43:53.000
for eight years.

0:43:53.000,0:43:55.000
So we are

0:43:55.000,0:43:58.000
allowing that our field's footprint has gotten so large that we need to

0:43:58.000,0:44:02.000
let you pick and choose a little bit to get the slice that seems most

0:44:02.000,0:44:03.000
appropriate for where you're headed.

0:44:03.000,0:44:06.000
So you'll see more about that.

0:44:06.000,0:44:10.000
If you are thinking about being a CS major

0:44:10.000,0:44:13.000
and have not yet declared,

0:44:13.000,0:44:17.000
I would advise

0:44:17.000,0:44:22.000
that you add yourself to what's called the considering CS list,

0:44:22.000,0:44:26.000
and you can get to this from the CS course advisor's page,

0:44:26.000,0:44:27.000
which,

0:44:27.000,0:44:30.000
off the top of my head, I think

0:44:30.000,0:44:32.000
it might be

0:44:32.000,0:44:36.000
CSadvising, but I'm not positive. I'll put the link on

0:44:36.000,0:44:39.000
our webpage, when I remember what it is.

0:44:39.000,0:44:42.000
It is a mailing list. So we have a mailing list of the declared undergrads, but we

0:44:42.000,0:44:45.000
also have a list for people who are

0:44:45.000,0:44:48.000
at least potentially interested in the major and just want to be kept up to date on

0:44:48.000,0:44:49.000
things that are happening.

0:44:49.000,0:44:52.000
There's going to be a lot of activity on this list in the

0:44:52.000,0:44:55.000
upcoming months as we publish the information about the new

0:44:55.000,0:44:56.000
curriculum.

0:44:56.000,0:44:57.000
So

0:44:57.000,0:45:00.000
you'll know what's coming down the pipes so you can make good decisions for

0:45:00.000,0:45:01.000
preparing for

0:45:01.000,0:45:04.000
what will be [inaudible], what the transition plan will be as we move into the new

0:45:04.000,0:45:05.000
courses

0:45:05.000,0:45:06.000
and how to make sure you

0:45:06.000,0:45:09.000
land

0:45:09.000,0:45:13.000
in the right place when all is said

0:45:13.000,0:45:14.000
and done. Then I put

0:45:14.000,0:45:15.000
a little note about

0:45:15.000,0:45:17.000
other majors that exist.

0:45:17.000,0:45:19.000
CS is

0:45:19.000,0:45:20.000


0:45:20.000,0:45:22.000
the home base for people who are

0:45:22.000,0:45:25.000
solving problems using computers. It spans a large variety of people

0:45:25.000,0:45:27.000
doing a lot of different things.

0:45:27.000,0:45:30.000
Then there's a couple other majors that we participate in, in the interdisciplinary

0:45:30.000,0:45:32.000
sense,

0:45:32.000,0:45:34.000
that UCS is part of a larger

0:45:34.000,0:45:37.000
context for doing things. So computer systems engineering, which is

0:45:37.000,0:45:40.000
between us and EE, which is a little bit more about hardware.

0:45:40.000,0:45:43.000
The symbolic systems program, which is

0:45:43.000,0:45:47.000
run by linguistics and includes cooperation from psychology, philosophy, communications,

0:45:47.000,0:45:51.000
CS looking at artificial intelligence and modeling human

0:45:51.000,0:45:52.000
thought and

0:45:52.000,0:45:53.000
understanding

0:45:53.000,0:45:55.000


0:45:55.000,0:45:57.000
intelligence as expressed in that way.

0:45:57.000,0:45:59.000
Then there's a mathematical computational science program that's homed

0:45:59.000,0:46:03.000
in the statistic department that is joint between math, computer science and the

0:46:03.000,0:46:06.000
MS and E. It's more of an applied math degree. So taking

0:46:06.000,0:46:08.000
mathematical thinking and

0:46:08.000,0:46:09.000


0:46:09.000,0:46:12.000
using computers and statistical things to analyze and

0:46:12.000,0:46:16.000
think about things. A lot of financial people end up

0:46:16.000,0:46:20.000
being drawn to that particular one or people who are doing risk analysis or

0:46:20.000,0:46:21.000
that sort of

0:46:21.000,0:46:24.000
combination of things. But where CS has a role to play in all of these because it's a

0:46:24.000,0:46:27.000
great tool for solving these kind of problems. So

0:46:27.000,0:46:29.000
different ways to get at

0:46:29.000,0:46:30.000
different pieces

0:46:30.000,0:46:33.000
of the major.

0:46:33.000,0:46:35.000
I've put a couple notes of things that

0:46:35.000,0:46:38.000
I think are worth

0:46:38.000,0:46:39.000
looking into

0:46:39.000,0:46:40.000
in case they,

0:46:40.000,0:46:43.000
at some point, are the right thing for you to look at. Section leading,

0:46:43.000,0:46:45.000
so joining the 106 staff

0:46:45.000,0:46:46.000
and shepherding the next generation

0:46:46.000,0:46:49.000
of students through the program

0:46:49.000,0:46:52.000
is a great way to strengthen your own knowledge. There's nothing like

0:46:52.000,0:46:54.000
making sure you understand recursion as to try and explain it to someone else who

0:46:54.000,0:46:55.000
doesn't understand it.

0:46:55.000,0:46:56.000
I

0:46:56.000,0:46:59.000
can really do a lot for

0:46:59.000,0:47:01.000
the personal connection to you and your craft

0:47:01.000,0:47:04.000
as well as just being involved in a great community. The section leaders are a really

0:47:04.000,0:47:05.000
wonderful,

0:47:05.000,0:47:08.000
dedicated group of students who are

0:47:08.000,0:47:08.000


0:47:08.000,0:47:12.000
fun to be around and great people to make friends with. So I

0:47:12.000,0:47:14.000
highly encourage you to take a look at that.

0:47:14.000,0:47:16.000
We interview for that every quarter,

0:47:16.000,0:47:17.000
so usually about week six,

0:47:17.000,0:47:19.000
we put out

0:47:19.000,0:47:21.000
applications and bring people in for interviews. We're always looking for new people

0:47:21.000,0:47:24.000
to join on a quarterly basis.

0:47:24.000,0:47:27.000
There are research opportunities all around the campus. One that the CS

0:47:27.000,0:47:30.000
department sponsors in particular is their [inaudible] summer institute.

0:47:30.000,0:47:33.000
So matching professors with undergrads to do work in the summer for

0:47:33.000,0:47:35.000
slave wages.

0:47:35.000,0:47:38.000
But great opportunity. You can get started on

0:47:38.000,0:47:40.000
thinking about how research might be part of your future.

0:47:40.000,0:47:43.000
One of the best preparations for thinking about grad school.

0:47:43.000,0:47:46.000
We do have an honors program.

0:47:46.000,0:47:50.000
Like most, we have a chance to stake out on an independent project and

0:47:50.000,0:47:50.000
show your mettle.

0:47:50.000,0:47:53.000
We have a co-terminal masters program

0:47:53.000,0:47:54.000
where you can

0:47:54.000,0:47:57.000
get some of the depth

0:47:57.000,0:47:58.000
before you leave this place.

0:47:58.000,0:48:01.000
Not to mention, there's a million fabulous

0:48:01.000,0:48:03.000
things to do with Stanford, getting involved with

0:48:03.000,0:48:06.000
arts or nonprofit organizations or sports or the student leadership

0:48:06.000,0:48:07.000
or whatever.

0:48:07.000,0:48:10.000
Maybe the most important memory I have from my undergrad was that the

0:48:10.000,0:48:13.000
trickiest part of my undergrad was learning what to say no to.

0:48:13.000,0:48:14.000
Realizing that there are

0:48:14.000,0:48:17.000
10,000 fabulous, worthwhile opportunities,

0:48:17.000,0:48:21.000
and doing all of them only means sacrificing your sanity and

0:48:21.000,0:48:23.000
the quality of the things you do.

0:48:23.000,0:48:24.000


0:48:24.000,0:48:29.000
So be careful and thoughtful about choosing the things you do and embracing them.

0:48:29.000,0:48:32.000
Be okay with saying, I won't do this. Even though it's great to go overseas, and I

0:48:32.000,0:48:35.000
would've liked that opportunity, it's not going to fit, and I'm okay with that. Don't

0:48:35.000,0:48:38.000
beat yourself up over it and cause

0:48:38.000,0:48:41.000
yourself too much grief trying to do too many things.

0:48:41.000,0:48:44.000
I won't be here on Friday. Keith is going to come. He's going to teach you about C++ in the real

0:48:44.000,0:48:45.000
world.

0:48:45.000,0:48:47.000
I'm going to see you guys Friday at the final.

0:48:47.000,0:48:57.000
I think that's all I need to say for today.