VIDEO: Data structure.
Now let's look at a more concrete incarnation of trees.
DOUG LLOYD: You know it's really a shame that we
don't have a problem sat on it in this year's implementation of CS50.
But this is probably one of my favorite topics of CS.
I love Huffman coding.
I just love the trajectory of six weeks ago,
we're talking about zeros and ones.
And eventually extracting this to ASCII, that 8-bit or 7-bit character
encoding scheme.
And now, we're trying to turn that on its head.
And saying, well, actually, if you're clever about it,
you can represent data with 5-bits, 4-bits, or 3-bits.
With clever manipulation of data structures.
DAVID MALAN: I agree.
And it's a really nice way of applying some of the more theoretical stuff
that we're doing around this point in the semester
to a very real world problem.
One that students can wrap their mind around.
And also something they probably hadn't necessarily
thought about how that's possible.
And yet much like some of our earlier examples in the semester,
it's really just reduced to these fundamental principles.
You have the zeros and ones.
You have the ASCII representation on top of that.
And once you understand the world at that level of detail,
can you do any number of things with it, including compress.
DOUG LLOYD: Yeah it is too bad we don't have the pset anymore.
I think we lasted it maybe four years ago.
DAVID MALAN: Or so.
It just was never great for C. There's so much passing around
of pointers and these structures.
That it always felt like a perfect opportunity
to motivate object oriented programming.
Which we don't just get with C. So maybe we
could bring it back now with Python or with a higher level language.
Because I too like it.
But it's a trade off.
There's so many other things we want to do too that it
makes for a nice example in class.
But it does kind of steer us away from the main line message.
Because it's very much focused now on an example.
DOUG LLOYD: I also enjoyed the fun of it.
The problem's that there were two parts.
There was the standard edition and the hacker edition.
You had huff and puff.
And it had the big bad wolf theme to it.
So if you want to take a look at it you can find it on CS50.tv from 2012
or maybe a little bit earlier.
But hopefully we can bring this back at some point.
Maybe a Python to problems with object oriented.
As opposed to having to build more of an API to hide the bit masking.
DAVID MALAN: Indeed.
And that was what was nice about that problem set in.
That we had a pre-define some of the functionality
that students would implement.
Because we had to give them, I think, one half of it.
They had to implement puff and we implemented huff, or vice versa.
So that they wouldn't have to do the entire thing from scratch.
But that means adhering to what basic API we expect out for them.