1
00:00:00,000 --> 00:00:00,500


2
00:00:00,500 --> 00:00:02,390
VIDEO: Data structure.

3
00:00:02,390 --> 00:00:04,890
Now let's look at a more
concrete incarnation of trees.

4
00:00:04,890 --> 00:00:07,130
DOUG LLOYD: You know it's
really a shame that we

5
00:00:07,130 --> 00:00:10,892
don't have a problem sat on it in
this year's implementation of CS50.

6
00:00:10,892 --> 00:00:13,100
But this is probably one of
my favorite topics of CS.

7
00:00:13,100 --> 00:00:14,960
I love Huffman coding.

8
00:00:14,960 --> 00:00:19,040
I just love the trajectory
of six weeks ago,

9
00:00:19,040 --> 00:00:21,110
we're talking about zeros and ones.

10
00:00:21,110 --> 00:00:24,170
And eventually extracting this to
ASCII, that 8-bit or 7-bit character

11
00:00:24,170 --> 00:00:25,400
encoding scheme.

12
00:00:25,400 --> 00:00:27,681
And now, we're trying to
turn that on its head.

13
00:00:27,681 --> 00:00:29,930
And saying, well, actually,
if you're clever about it,

14
00:00:29,930 --> 00:00:33,560
you can represent data with
5-bits, 4-bits, or 3-bits.

15
00:00:33,560 --> 00:00:35,540
With clever manipulation
of data structures.

16
00:00:35,540 --> 00:00:36,420
DAVID MALAN: I agree.

17
00:00:36,420 --> 00:00:39,350
And it's a really nice way of applying
some of the more theoretical stuff

18
00:00:39,350 --> 00:00:41,433
that we're doing around
this point in the semester

19
00:00:41,433 --> 00:00:42,726
to a very real world problem.

20
00:00:42,726 --> 00:00:44,600
One that students can
wrap their mind around.

21
00:00:44,600 --> 00:00:47,000
And also something they
probably hadn't necessarily

22
00:00:47,000 --> 00:00:48,600
thought about how that's possible.

23
00:00:48,600 --> 00:00:51,320
And yet much like some of our
earlier examples in the semester,

24
00:00:51,320 --> 00:00:54,384
it's really just reduced to
these fundamental principles.

25
00:00:54,384 --> 00:00:55,550
You have the zeros and ones.

26
00:00:55,550 --> 00:00:57,650
You have the ASCII
representation on top of that.

27
00:00:57,650 --> 00:01:00,950
And once you understand the
world at that level of detail,

28
00:01:00,950 --> 00:01:06,450
can you do any number of things
with it, including compress.

29
00:01:06,450 --> 00:01:10,070
DOUG LLOYD: Yeah it is too bad
we don't have the pset anymore.

30
00:01:10,070 --> 00:01:12,699
I think we lasted it
maybe four years ago.

31
00:01:12,699 --> 00:01:13,490
DAVID MALAN: Or so.

32
00:01:13,490 --> 00:01:16,850
It just was never great for C.
There's so much passing around

33
00:01:16,850 --> 00:01:18,650
of pointers and these structures.

34
00:01:18,650 --> 00:01:20,600
That it always felt like
a perfect opportunity

35
00:01:20,600 --> 00:01:22,800
to motivate object oriented programming.

36
00:01:22,800 --> 00:01:24,757
Which we don't just
get with C. So maybe we

37
00:01:24,757 --> 00:01:27,590
could bring it back now with Python
or with a higher level language.

38
00:01:27,590 --> 00:01:28,506
Because I too like it.

39
00:01:28,506 --> 00:01:29,600
But it's a trade off.

40
00:01:29,600 --> 00:01:31,849
There's so many other things
we want to do too that it

41
00:01:31,849 --> 00:01:33,350
makes for a nice example in class.

42
00:01:33,350 --> 00:01:37,580
But it does kind of steer us
away from the main line message.

43
00:01:37,580 --> 00:01:39,900
Because it's very much
focused now on an example.

44
00:01:39,900 --> 00:01:41,160
DOUG LLOYD: I also
enjoyed the fun of it.

45
00:01:41,160 --> 00:01:42,600
The problem's that there were two parts.

46
00:01:42,600 --> 00:01:43,880
There was the standard edition
and the hacker edition.

47
00:01:43,880 --> 00:01:45,440
You had huff and puff.

48
00:01:45,440 --> 00:01:48,230
And it had the big bad wolf theme to it.

49
00:01:48,230 --> 00:01:51,480
So if you want to take a look at it
you can find it on CS50.tv from 2012

50
00:01:51,480 --> 00:01:52,730
or maybe a little bit earlier.

51
00:01:52,730 --> 00:01:56,180
But hopefully we can bring
this back at some point.

52
00:01:56,180 --> 00:01:59,480
Maybe a Python to problems
with object oriented.

53
00:01:59,480 --> 00:02:05,037
As opposed to having to build more
of an API to hide the bit masking.

54
00:02:05,037 --> 00:02:05,870
DAVID MALAN: Indeed.

55
00:02:05,870 --> 00:02:08,078
And that was what was nice
about that problem set in.

56
00:02:08,078 --> 00:02:11,010
That we had a pre-define
some of the functionality

57
00:02:11,010 --> 00:02:12,260
that students would implement.

58
00:02:12,260 --> 00:02:14,630
Because we had to give them,
I think, one half of it.

59
00:02:14,630 --> 00:02:17,470
They had to implement puff and we
implemented huff, or vice versa.

60
00:02:17,470 --> 00:02:20,095
So that they wouldn't have to do
the entire thing from scratch.

61
00:02:20,095 --> 00:02:25,088
But that means adhering to what
basic API we expect out for them.

62
00:02:25,088 --> 00:02:25,588