1
00:00:00,000 --> 00:00:00,150


2
00:00:00,150 --> 00:00:02,441
VIDEO: With which we can
solve problems and we revisit.

3
00:00:02,441 --> 00:00:05,160
DOUG LLOYD: We've covered a lot
of different data structures.

4
00:00:05,160 --> 00:00:08,269
Or we're starting to cover a lot of
different structures at this point.

5
00:00:08,269 --> 00:00:11,310
And the one that students are most
familiar with at this point is arrays.

6
00:00:11,310 --> 00:00:15,310
But arrays, they're great
to get started with.

7
00:00:15,310 --> 00:00:18,420
But they definitely suffer
from a few major flaws.

8
00:00:18,420 --> 00:00:20,370
And particularly the
fact that they're fixed

9
00:00:20,370 --> 00:00:24,540
size and can only hold
elements of one type.

10
00:00:24,540 --> 00:00:25,997
At least in a language like C.

11
00:00:25,997 --> 00:00:26,830
DAVID MALAN: Indeed.

12
00:00:26,830 --> 00:00:29,880
And you have to know, of course, a
priori, how big of an array you want.

13
00:00:29,880 --> 00:00:34,260
Otherwise you have to manually
re-allocate it and repopulate it

14
00:00:34,260 --> 00:00:35,770
or copy everything over.

15
00:00:35,770 --> 00:00:40,860
So this is actually one of our first,
one of many, but one of our best,

16
00:00:40,860 --> 00:00:42,960
I think, opportunities
in class to really start

17
00:00:42,960 --> 00:00:45,072
discussing deeply trade offs.

18
00:00:45,072 --> 00:00:45,780
DOUG LLOYD: Right

19
00:00:45,780 --> 00:00:47,790
DAVID MALAN: And having
students critically

20
00:00:47,790 --> 00:00:49,560
think about what an array is good for.

21
00:00:49,560 --> 00:00:50,490
What it's bad for.

22
00:00:50,490 --> 00:00:53,270
And what kind of ceiling you
bump up against ultimately

23
00:00:53,270 --> 00:00:56,520
with this data structure when it comes
to solving more sophisticated problems.

24
00:00:56,520 --> 00:00:58,987
The goal here is,
without just saying, hey,

25
00:00:58,987 --> 00:01:02,070
there's these other data structures
in the world like linked lists, trees,

26
00:01:02,070 --> 00:01:03,420
or whatnot.

27
00:01:03,420 --> 00:01:06,570
What are the problem with what we
have, so as to actually motivate

28
00:01:06,570 --> 00:01:07,540
solving the problem.

29
00:01:07,540 --> 00:01:08,530
DOUG LLOYD: Right.

30
00:01:08,530 --> 00:01:09,030
Yeah.

31
00:01:09,030 --> 00:01:11,310
I would say that, at
least in my opinion,

32
00:01:11,310 --> 00:01:16,670
week five is really the week where we
start to focus a lot more on design.

33
00:01:16,670 --> 00:01:20,370
Or encouraging students to think a
little more critically about design.

34
00:01:20,370 --> 00:01:23,700
DAVID MALAN: And it's an
opportunity to really start

35
00:01:23,700 --> 00:01:28,420
to use as building blocks, pointers,
and a basic understanding of memory

36
00:01:28,420 --> 00:01:28,920
management.

37
00:01:28,920 --> 00:01:31,827
To start to stitch together
our own things in memory.

38
00:01:31,827 --> 00:01:34,410
And this is actually one of the
reasons that I like C so much.

39
00:01:34,410 --> 00:01:37,470
Is that we have this ability,
albeit at a low level, which

40
00:01:37,470 --> 00:01:40,470
can be a little scary and a
little difficult to grok at first.

41
00:01:40,470 --> 00:01:43,980
But we have this ability to create
out of memory anything we want.

42
00:01:43,980 --> 00:01:47,070
And so only those data
structures we ourselves

43
00:01:47,070 --> 00:01:49,346
design and then implement
do we have at our disposal.

44
00:01:49,346 --> 00:01:50,096
DOUG LLOYD: Right.

45
00:01:50,096 --> 00:01:51,630
It's something that students
can take for granted

46
00:01:51,630 --> 00:01:53,910
later on when they use a
language like PHP or Python.

47
00:01:53,910 --> 00:01:56,856
The things like hash tables
are just given to them for free

48
00:01:56,856 --> 00:01:58,230
by virtue of using that language.

49
00:01:58,230 --> 00:02:01,410
Here they get to see what it's
like behind the scenes at the very

50
00:02:01,410 --> 00:02:02,310
low level.

51
00:02:02,310 --> 00:02:06,960
Which really only C, among languages
that are frequently used today,

52
00:02:06,960 --> 00:02:09,297
that gives us the chance
to really take that peak.

53
00:02:09,297 --> 00:02:11,880
DAVID MALAN: And it allows us
to continue the conversation too

54
00:02:11,880 --> 00:02:12,750
about abstraction.

55
00:02:12,750 --> 00:02:15,450
In that, with an array, we can
ultimately build other things.

56
00:02:15,450 --> 00:02:17,158
Even using that data
structure eventually

57
00:02:17,158 --> 00:02:18,810
we'll talk about stacks, and queues.

58
00:02:18,810 --> 00:02:21,393
Which could be implemented more
dynamically with linked lists.

59
00:02:21,393 --> 00:02:26,040
But they could also be implemented
with fairly fixed sizes using an array.

60
00:02:26,040 --> 00:02:32,430
And yet you can therefore abstract
away the inside of a stack or a queue,

61
00:02:32,430 --> 00:02:33,520
might indeed be an array.

62
00:02:33,520 --> 00:02:35,520
But there too, it's an
opportunity to understand

63
00:02:35,520 --> 00:02:38,550
what the limitations or implications
of that design decision are.

64
00:02:38,550 --> 00:02:41,040
Especially if it's the easier
of the two design decisions.

65
00:02:41,040 --> 00:02:43,380
As soon as you take out
your text editor and have

66
00:02:43,380 --> 00:02:46,160
to start stitching things
together with pointers,

67
00:02:46,160 --> 00:02:48,377
there's a bit more effort involved.

68
00:02:48,377 --> 00:02:48,877