>> [MUSIC PLAYING]
>> ANDI PENG: Welcome to week 6 of section.
We deviated from our standard section time of Tuesday
afternoon to this lovely Sunday morning.
Thank you for everyone that joined me today, but seriously,
a round of applause.
>> That's a pretty big effort.
I almost didn't even make it up in time, but It was OK.
So I know that all of you have just made it to the quiz.
First of all, welcome to the flip side of that.
>> Secondly, we'll talk about it.
We'll talk about the quiz.
We'll talk about how you're doing in the class.
You'll be fine.
I have your quizzes for you at the end of here,
so if you guys want to take a look at it, totally fine.
>> So quickly before we begin, the agenda for today is as follows.
As you can see, we're basically rapid firing
through a whole bunch of data structures really, really, really quickly.
So as such, it won't be super interactive today.
It'll just be me kind of shouting things that you, and if I confuse you,
if I'm going too fast, let me know.
They're just various data structures, and as part
of your pset for this upcoming week, you'll
be asked to implement one of them, perhaps two of them-- two of them
in your pset.
OK, so I'm just going to start with some announcements.
We'll go over stacks and queues more in depth than what we did before the quiz.
We'll go over linked list again, once again,
more in depth than what we had before the quiz.
And then we'll talk about hash tables, trees and tries, which
are all pretty necessary for your pset.
And then we'll go over some helpful tips for pset5.
>> OK, so quiz 0.
The average was a 58%.
It was very low, and so you guys all did very, very well in accordance
with that.
>> Pretty much, rule of thumb is if you're within a standard deviation of the mean
especially since we're in a less comfy section, you're totally fine.
You're on track.
Life is good.
>> I know it's scary to think that I got like a 40% on this quiz.
I'm going to fail this class.
I promise you, you're not going to fail the class.
You're totally fine.
>> For those of you who got over the mean, impressive, impressive,
like, seriously well done.
I have them with me.
Feel free to come get them at the end of section.
Let me know if you have any issues, questions with them.
If we add up your score wrong, let us know.
>> OK, so pset5, this is a really weird week for Yale in the sense
that our pset is due Wednesday at noon including
the late day, so it's actually theoretically due Tuesday at noon.
Probably no one finished at Tuesday at noon.
That's totally fine.
We're going to have office hours tonight as well as Monday night.
And all of the sections this week will actually be turned into workshops,
so feel free to pop in any section you want,
and they'll be kind of mini-pset workshops for help on that.
So as such, this is the only section where we're teaching material.
All the other sections will be focusing exclusively on help for the pset.
Yeah?
>> AUDIENCE: Where are office hours?
>> ANDI PENG: Office hours tonight-- oh, good question.
I think office hours tonight are in Teal or at Commons.
If you check online CS50 and you go to office hours,
there should be a schedule that tells you where all of them are.
>> I know either tonight or tomorrow is teal,
and I think we may have commons for the other night.
I'm not sure.
Good question.
Check on CS50.
>> Cool, any questions regarding the schedule for the next like three days?
I promise you guys like David said, this is the top of the hill.
You guys are almost there.
Just three more days.
Get there, and then we'll all come down.
We'll have a nice CS-free break.
We'll come back.
We'll dive into web programming and development,
things that are very fun compared to some of the other psets.
And it'll be chill, and we'll have lots of fun.
We'll have more candy.
Sorry for candy.
I forgot candy.
It was a rough morning.
So you guys are almost there, and I'm really proud of you guys.
>> OK, so stacks.
Who loved the question about Jack and his clothing on the quiz?
No one?
OK, that's fine.
>> So essentially as you can picture Jack, this guy here,
loves to take the clothing out of the top of the stack,
and he puts it back onto the stack after he's done.
So in this way, he never seems to be getting
to the bottom of the stack in his clothing.
So this kind of describes the basic data structure
of how a stack is implemented.
>> Essentially, think of a stack as any stack of objects
where you put things onto the top, and then you pop them out from the top.
So LIFO is the acronym we like to use-- Last In, First Out.
And so last in to the top of the stack is the first one that comes out.
And so the two terms we like to associate
with that are called push and pop.
When you push something onto the stack, and you pop it back up.
>> And so I guess this is kind of an abstract concept for those of you
who want to see like an actual implementation of this
in the real world.
How many of you have written an essay maybe like an hour before it was due,
and you accidentally deleted a huge chunk of it, like accidentally?
And then what control do we use to put it back?
Control-Z, yeah?
Control-Z, so the amount of times that Control-Z has saved my life,
has saved my ass, every time that's implemented through a stack.
>> Essentially all the information that's on your Word document,
it gets pushed and popped at will.
And so essentially whenever you delete anything, you pop it back up.
And then if you need it back on, you push it, which is what Control-C does.
And so real world function of how simple data structure
can help with your everyday life.
>> So a struct is the way that we actually create a stack.
We type define struct, and then we call it stack at the bottom.
And within the stack, we have two parameters
that we can essentially manipulate, so we have char star strings capacity.
>> All that it is doing is creating an array
that we can store whatever you want which we can determine its capacity.
Capacity Is just the max amount of items we can put into this array.
int size is the counter that keeps track of how many items are currently
in the stack.
So then we can keep track of, A, both how large the actual stack is,
and, B, how much of that stack we filled because we don't want
to overflow over what our capacity is.
>> So for example, this lovely question was on your quiz.
Essentially how do we push onto the top of a stack.
Pretty simple.
If you look at it, we'll walk through this.
If [INAUDIBLE] size-- remember, whenever you
want to access any parameter within a struct,
you do the name of the struct.parameter.
>> In this case, s is the name of our stack.
We want to access the size of it, so we do s.size.
So as long as the size is not equal to capacity or as long
as it's less than capacity, either would work here.
>> You want to access the inside of your stack, so s.strings,
and you're going to put that new number that you want to insert into there.
Let's just say we will want to insert int n onto the stack,
we could do s.strings, brackets, s.size equals n.
Because size is where we currently are in the stack
if we're going to push it on, we just access
wherever the size is, the current fullness of the stack,
and we push the int n onto it.
And then we want to make sure that we're also incrementing size of the n,
so we can keep track of we've added an extra thing to the stack.
Now we have a greater size.
Does this here make sense to everybody, how logically it works?
It was kind of quick.
AUDIENCE: Can you go over the s.stringss.strings[s.size] again?
ANDI PENG: Sure, so what does s.size currently give us?
AUDIENCE: It's the current size.
ANDI PENG: Exactly, so the current index that our size is at,
and so we want to put the new integer that we want to insert into s.size.
Does that make sense?
Because s.strings, all that is is the name of the array.
All it is is accessing the array within our struct,
and so if we want to place n into that index,
we can just access it using brackets s.size.
Cool.
>> All right, pop, I pseudocode it out for you guys, but similar concept.
Does that make sense?
If the size is greater than zero, then you
know that you want to take something out because if the size is not
greater than zero, then you have nothing in the stack.
>> So you only want to execute this code, it can only
pop if there is something to pop.
So if the size is greater than 0, we minus the size.
We decrement the size and then return whatever is inside of it because
by popping, we want to access whatever is stored
in the index of the top of the stack.
Everything make sense?
If I made you guys write this out, would you guys be able to write it out?
OK, you guys can play around with it.
No worries if you don't get it.
We don't have time to code it out today because we've
got a lot of these structures to go through, but essentially
pseudocode, very, very similar to push.
Just follow along the logic.
Make sure you're accessing all the features of your struct correctly.
Yeah?
>> AUDIENCE: Will these slides and this whole thing be up today-ish?
ANDI PENG: Always, yep.
I'm going to try to put this up like an hour after.
I'll email David, David will try to put it up like an hour after this.
>> OK, so then we move into this other lovely data structure called a queue.
As you guys can see here, a queue, for the British amongst us,
all it is is a line.
So contrary to what you think a stack is,
a queue is exactly what logically you think it is.
It's held by the rules of FIFO, which is First In, First Out.
If you're the first one in the line, you're
the first one that comes out of the line.
>> So what we like to call this is dequeueing and enqueueing.
If we want to add something to our queue, we enqueue.
If we want to dequeue, or take something away, we dequeue.
>> So same sense that we're kind of creating fixed-size elements that we
can store certain things, but we can also
change where we're placing parameters inside of them
based on what type of functionality we want.
So stacks, we wanted the last one, N to be the first one out.
Queue is we want the first thing in to be the first thing out.
>> So the struct-type define, as you can see,
it's a little bit different from what the stack was
because not only do we have to keep track of where the size currently is,
we also want to keep track of the head as well as where we currently are.
So I think it's easier if I draw this up.
So let's imagine we've got a queue, so let's say the head is right here.
The head of the line, let's just say that's currently there,
and we want to insert something into the queue.
I'm going to call size essentially is the same thing as tail,
the end of wherever your queue is.
Let's just say size is right here.
>> So how does one feasibly insert something into a queue?
What index do we want to place where we want to insert into.
If this is the beginning of your queue and this is the end of it
or the size of it, where do we want to add the next object?
>> AUDIENCE: [INAUDIBLE]
ANDI PENG: Exactly, you want to add it depending on have you written it.
Either this is blank or that is blank.
So you want to add it probably here because if the size is--
if these are all full, you want to add it right here, right?
>> And so that's, while very, very simple, not quite always correct
because the main difference between a queue and a stack
is that the queue can actually be manipulated
so that the head changes depending on where you want
the beginning of your cue to start.
And as a result, your tail is also going to change.
And so take a look at this code right now.
As you guys were also asked to write out on the quiz, enqueue.
Maybe we'll talk through why the answer was what it was.
>> I couldn't quite fit this line on one, but essentially this piece of code
should be on one line.
Spend like 30 seconds.
Take a look, and see why this is the way that it is.
>> Very, very similar struct, very, very similar structure as the previous
stack except for perhaps one line of code.
And that one line of code determines the functionality.
And it really differentiates a queue from a stack.
>> Anyone want to take a stab at explaining why you've
got this complicated thing in here?
We see the return of our wonderful friend modulus.
As you guys will soon come to recognize in programming,
almost anytime you need something to wrap around anything,
modulus is going to be the way to do it.
So knowing that, does anyone want to try explaining that line of code?
Yeah, all answers are accepted and welcome.
AUDIENCE: Are you talking to me?
ANDI PENG: Yeah.
AUDIENCE: Oh, no sorry.
ANDI PENG: OK, so let's walk through this code.
So when you're trying to add something onto a queue,
in the lovely case that the head happens to be right here, it's very easy for us
to just go to the end insert something, right?
But the whole point of a queue is that the head can actually dynamically
change depending on where we want the start of our q to be,
and as such, the tail is also going to change.
>> And so imagine that this was not the queue, but rather this was the queue.
Let's say the head is right here.
Let's say our queue looked like this.
If we wanted to shift where the beginning of the line is,
let's say we shifted head this way and sizes here.
>> Now we want to add something to this queue, but as you guys can see,
it's not so simple as to just add whatever is after the size
because then we run out of bounds of our actual array.
Where we want to really add is here.
That's the beauty of a queue is that to us, visually it
looks like the line goes like this, but when stored in a data structure,
they give it as like a cycle.
It kind of wraps around to the front the same way
that a line can also wrap around depending on wherever you
want to beginning of the line to be.
And so if we take a look down here, let's
say we wanted to create a function called enqueue.
We wanted to add int n into that q.
If q.size q-- we'll call that our data structure-- if our queue.size does not
equal to capacity or if it's less than capacity,
q.strings is the array within our q.
We're going to set that equal to q.heads,
which is right here, plus q.size modulus by the capacity, which
wrap us back around here.
>> So in this example, index of head is 1, right?
The index of size is 0, 1, 2, 3, 4.
So we can do 1 plus 4 modulus by our capacity which is 5.
What does that give us?
What is the index that comes out of this?
>> AUDIENCE: 0.
>> ANDI PENG: 0, which happens to be right here,
and so we want to be able to insert into right here.
And so this equation here kind of just works with any numbers
depending on where your head and your size are.
If you know what those things are, you know
exactly where you want to insert whatever is after your queue.
Does that make sense to everybody?
>> I know kind of a brain teaser especially since this
came in the aftermath of your quiz.
But hopefully everyone now can understand
why this solution or this function is the way that it is.
Anyone a bit unclear on that?
OK.
>> And so now, if you wanted to dequeue, this
is where our head would be shifting because if we were to dequeue,
we don't take off the end of the q.
We want to take off the head, right?
So as a result, head is going to change, and that is why when you enqueue,
you've got to keep track of where your head and your size
are to be able to insert into the correct position.
>> And so when you dequeue, I also pseudocode it out.
Feel free to if you want to attempt coding this out.
You want to move the head, right?
If I wanted to dequeue, I would move the head over.
This would be the head.
>> And our current size would subtract because we no longer
have four elements in the array.
We only have three, and then we want to return whatever was stored inside
of the head because we want to take this value out so very similar to the stack.
Just you're taking from a different place,
and you have to reassign your pointer to different place as a result.
Logically, everyone follow?
Great.
>> OK, so we're going to talk a bit more in depth about linked lists
because they'll be very, very valuable for you in the course of this week's
psets.
Linked lists, as you guys can remember, all they are
are nodes that are nodes of certain values of both a value and a pointer
that are linked together by those pointers.
And so the struct on how we create a node here is we
have int n, which is whatever the value in a store or string n
or whatever you want to call it, the char star n.
Struct node star, which is the pointer that you want to have in each node,
you're going to have that pointer point towards next.
You'll have the head of a linked list that's
going to point to the rest of the values so on and so forth
until you eventually reach the end.
And this last node is just going to not have a pointer.
It's going to point to null, and that's when
you know you've hit the end of your linked list
is when your last pointer doesn't point to anything.
>> So we're going to go a bit more in depth regarding how one would possibly
search a linked list.
Remember what are some of the drawbacks of the linked lists
verses an array regarding searches.
An array you can binary search, but why can't you do that in a linked list?
>> AUDIENCE: Because they're all connected, but you don't quite know where
[INAUDIBLE].
>> ANDI PENG: Yeah, exactly so remember that the brilliance of an array
was the fact that we had random access memory where
if I wanted the value from index six, I could just say index six,
give me that value.
And that's because arrays are sorted in a contiguous space of memory
in one place, whereas kind of linked lists
are randomly interspersed all around, and the only way you can find one
is through a pointer that tells you the address of where that next node is.
>> And so as a result, the only way to search through a linked list
is linear search.
Because I don't exactly know where the 12th value in the linked list is,
I have to traverse the entirety of that linked list one
by one from the head to the first node, to the second node, to the third node,
all the way down until I finally get to where that node I'm looking for is.
And so in this sense, search on a linked list is always n.
It's always n.
It's always in linear time.
>> And so the code in which we implement this, and this
is a bit new for you guys since you guys haven't really talked about or ever
seen pointers in how to search through pointers,
so we'll walk through this very, very slowly.
So bool search, right, let's imagine we want
to create a function called search that returns true
if you found a value inside the linked list, and it returns false otherwise.
Node star list is currently just the pointer
to the first item in your linked list.
int n is the value that you're searching for in that list.
>> So node star pointer equals list.
That means we're setting and creating a pointer
to that first node inside of the list.
Everyone with me?
So if we were to go back here, I would have
initialized a pointer that points to the head of whatever that list is.
>> And then once you get down here, while pointer does not equal null,
so that is the loop in which we are going to be subsequently traversing
the rest of our list because what happens when pointer equals null?
We know that we have--
>> AUDIENCE: [INAUDIBLE]
>> ANDI PENG: Exactly, so we know that we've reached the end of list, right?
If you go back here, each node should be pointing to another node
and so on and so forth until you hit eventually
the tail of your linked list, which has a pointer that just
doesn't point anywhere other than no.
And so you basically know that your list is still there up
until pointer does not equal null because once it equals null,
you know that there's no more stuff.
>> So that is the loop in which we're going to have the actual search.
And if the pointer-- do you see that kind of arrow function there?
So if pointer points to n, if the pointer at n equals equals n,
so that means that if the pointer that you're
searching for on the end of each node is actually equal to the value
you're looking for, then you want to return true.
So basically, if you're at a node that has the value that you're looking for,
you know that you've been able to successfully search.
>> Otherwise, you want to set your pointer to the next node.
That is what that line here is doing.
Pointer equals pointer next.
Everyone see how that's working?
>> And essentially you're going to just traverse the entirety of the list,
resetting your pointer each time until you eventually hit the end of the list.
And you know that there are no more nodes to search through,
and then you can return false because you know that, oh, well,
if I've been able to search through the entirety of the list.
If in this example, if I wanted to look for the value of 10,
and I start at the head, and I search all the way down,
and I eventually got to this, which a pointer that points to null,
I know that, crap, I guess 10 isn't in this list because I couldn't find it.
And I'm at the end of the list.
And in which case you know I'm going to return false.
>> Let that soak in for a little bit.
This will be pretty important for your pset.
The logic of it is very simple, perhaps syntactically just implementing it.
You guys want to make sure that you understand.
Cool.
>> OK, so how we would be inserting nodes, right,
into a list because remember what are the what of the benefits
of having a linked list versus an array in terms of storage?
>> AUDIENCE: It's dynamic, so it's easier to--
>> ANDI PENG: Exactly, so it's dynamic, which
means that it can expand and shrink depending on the user's needs.
And so, in this sense, we don't need to waste unnecessary memory because I
if I don't know how many values I want to store, it doesn't make sense for me
to create an array because if I want to store 10 values
and I create an array of 1,000, that's a lot of wasted memory, allotted.
That's why we want to use a linked list to be able to dynamically
change or shrink our size.
>> And so that makes insertion a bit more complicated.
Since we can't randomly access elements the way that we would of an array.
If I want to insert an element into the seventh index,
I just can insert it into the seventh index.
On a linked list, it doesn't quite work as easily,
and so if we wanted to insert the one here in the linked list,
visually, it's very easy to see.
We just want to insert it right there, right at the beginning of the list,
right after head.
>> But the way in which we have to reassign the pointers is a bit convoluted
or, logically, it makes sense, but you want to make sure that you have it
completely down because the last thing you want
is to reassign a pointer the way that we're doing here.
If you dereference the pointer from head to 1,
then all of a sudden the rest of your linked list
is lost because you haven't actually created a temporary anything.
That's pointed to the 2.
If you reassign the pointer, then the rest of your list is totally lost.
So you want to be very, very careful here
to first assign the pointer from whatever you
want to insert into wherever you want, and then you
can dereference the rest of your list.
>> So this applies for wherever you're trying to insert into.
If you want to insert at the head, if you want to answer here,
if you want to insert at the end, well, the end I
guess you would just have no pointer, but you
want to make sure that you don't lose the rest of your list.
You always want to make sure your new node is pointing
towards whatever you want to insert into,
and then you can add the chaining on.
Everyone clear?
>> This is going to be one of the real issues.
One of the most major issues you're going to have on your pset
is that you're going to try to create a linked list and insert things
but then just lose the rest of your linked list.
And you're going to be like, I don't know why this is happening?
And it's a pain to go through and search all of your pointers.
>> And I guarantee you on this pset, writing and drawing these nodes out
will be very, very helpful.
So you can completely keep track of where all your pointers are,
what's going wrong, where all your nodes are,
what you need to do to access or insert or delete or any of them.
Everyone good with that?
Cool.
>> So if we wanted to look at the code?
Oh, I don't know if we can see the-- OK, so
at the top all it is is a function named insert where we want
to insert int n into the linked list.
We're going to walk through this.
It's a lot of code, a lot of new syntax.
We'll be OK.
>> So up at the top, whenever we want to create anything
what do we need to do, especially if you want it to not be stored on the stack
but in the heap?
We go to a malloc, right?
So we're going to create a pointer.
Node, pointer, new equals malloc the size of a node
because we want that node to be created.
We want the amount of memory that a node takes up
to be allotted for the creation of the new node.
>> And then we're going to check to see if new equals equals null.
Remember what we said?
Whatever you malloc, what must you always do?
You must always check to see whether or not that is null.
>> For example, if your operating system was completely full,
if you had no more memory at all and you try to malloc,
it would return null for you.
And so if you try to use it when it was pointing to null,
you're not going to able to access that information.
And so as such, we wanted to make sure that whenever you're mallocing,
you're always checking to see if that memory given to you is null.
And if it's not, then we can move on with the rest of our code.
>> So we're going to initialize the new node.
We're going to do new n equals n.
And then we're going to do set new the pointer on new
to null because right now we don't want anything for it to point to.
We have no idea where it's going to put you,
and then if we want to insert it at the head,
then we can reassign the pointer to the head.
Does everyone follow the logic of where that's happening?
>> All we're doing is creating a new node, setting the pointer to null,
and then reassigning it to the head if we
know we want to insert it at the head.
And then the head is going to point towards that new node.
Everyone OK with that?
>> So it's a two-step process.
You've got to first assign whatever you're creating.
Set that pointer to the reference, and then you
can kind of dereference the first pointer
and point it towards the new node.
Wherever you want to insert it, that logic is going to hold true.
>> It's kind of like assigning temporary variables.
Remember, you've got to make sure that you
don't lose track of if you're swapping.
You want to make sure that you have a temporary variable that kind of keeps
track of where that thing is stored so that you
don't lose any value in the course of like messing around with it.
>> OK, so code will be here.
You guys take a look after section.
It will be there.
>> So I guess how does this differ if we wanted
to insert into the middle or the end?
Does anyone have an idea of what's the pseudocode as the logical reference
that we would take if we wanted to insert it in the middle?
So if we wanted to insert it at the head, all we do is create a new node.
We set the pointer of that new node to whatever the head,
and then we set the head to the new node, right?
If we wanted to insert it in the middle of the list, what would we have to do?
>> AUDIENCE: It would still be a similar process
of like assigning pointer and then assigning that pointer,
but we would have to locate there.
>> ANDI PENG: Exactly, so exactly the same process except you
have to locate where exactly you want that new pointer to go into,
so if I want to insert into the middle of linked list-- OK,
let's say that's our linked list.
If we want to insert it right here, we're going to create a new node.
We're going to malloc.
We're going to create a new node.
We're going to assign the pointer of this node here.
>> But the problem that differs from where the head is
is that we knew exactly where the head is.
It was right at the first, right?
But here we've got to keep track of where we're inserting it into.
If we are inserting our node here, we've got
to make sure that the one previous to this node
is the one that reassigns the pointer.
So then you have to kind of keep track of two things.
If you keep track of where this node currently is inserting into.
You also have to keep track of where the previous node that you're looking at
was also there.
Everyone good with that?
OK.
>> How about inserting into the end?
If I wanted to add it here-- if I wanted to add a new node to the end of a list,
how might I go about doing that?
AUDIENCE: So currently, the last one's pointed to null.
ANDI PENG: Yeah.
Exactly, so this one currently is pointed to know,
and so I guess, in this sense, it's very easy to add to the end of a list.
All you have to do is set it equal to null and then boom.
Right there, very easy.
Very simple.
>> Very similar to the head, but logically you
want to make sure that the steps you take towards doing any of this,
you're following along.
It's very easy to, in the middle of your code, get caught up on,
oh, I've got so many pointers.
I don't know where anything is pointing to.
I don't even know which node I'm on.
What's going on?
>> Relax, calm down, take a deep breath.
Draw out your linked list.
If you say, I know where exactly I need to insert this into
and I know exactly how to reassign my pointers, much, much easier to picture
out-- much, much easier to not get lost in the bugs of your code.
Everyone OK with that?
OK.
>> So I guess a concept that we haven't really talked about before now,
and I guess you probably won't encounter much yet--
it's kind of an advanced concept-- is that we actually have a data
structure called a doubly linked list.
So as you guys can see, all we're doing is creating
an actual value, an extra pointer on each of our nodes
that also points to the previous node.
So not only do we have our nodes point to the next one.
They also point to the previous one.
I'm going to ignore these two right now.
>> So then you have a chain that can move both ways,
and then it's a bit easier to logically follow along.
Like here, instead of keeping track of, oh, I
have to know that this node is the one that I have to reassign,
I can just go here and just pull the previous.
Then I know exactly where that is, and then you
don't have to traverse the entirety of the linked list.
It's a bit easier.
>> But as such, you have doubly the amount of pointers,
that's double the amount of memory.
It's a lot of pointers to keep track of.
It's a bit more complex, but it's a bit more user friendly depending
on what you're trying to accomplish.
>> So this type of data structure totally exists,
and the structure for is very, very simple except all you're having is,
instead of just a pointer to next, you also have a pointer to previous.
That's all the difference was.
Everyone good with that?
Cool.
>> All right, so now I'm to really spend probably
like 15 to 20 minutes or the bulk of the rest of the time in section
talking about hash tables.
How many of you guys have read pset5 spec?
All right, good.
That's higher than the 50% of normally.
It's OK.
>> So as you guys will see, you're challenge in pset5
will be to implement a dictionary where you load over 140,000 words
that we give you and spell check it against all of the text.
We'll give you random pieces of literature.
We'll give you The Odyssey.
We'll give you The Iliad.
We'll give you Austin Powers.
>> And your challenge will be to spell check
every single word in all of those dictionaries
essentially with our spell checker.
And so there's a few parts of creating this pset,
first you want to be able to actually load
all the words into your dictionary, and then you
want to be able to spell check all of them.
And so as such, you're going to require a data structure that can do this fast
and efficiently and dynamically.
>> So I suppose the easiest way to do this, you
would probably create an array, right?
The easiest way of storage is you can create an array of 140,000 words
and just place them all there and then traverse them by binary search
or by selections or not-- sorry that's sorting.
You can sort them and then traverse them by binary search or just linear search
and just final the words, but that takes a huge amount of memory,
and it's not very efficient.
>> And so we're going to start talking about ways of making
our running time more efficient.
And our goal is to get constant time where
it's almost like arrays, where you have instantaneous access.
If I wanted to search for anything, I want to be able to just,
boom, find it exactly, and pull it out.
And so a structure in which we'll be becoming very close
to be able to access constant time, this holy grail
in programming of constant time is called a hash table.
And so David previously mentioned the [INAUDIBLE] a little bit in lecture,
but we're going to really dive in deep this week
on a piece that's regarding how a hash table works.
>> So the way that a hash table works, for example,
if I wanted to store a bunch of words, a bunch of words in the English language,
I could theoretically put banana, apple, kiwi, mango, pair,
and cantaloupe all on just an array.
They could all fit in and be find.
It'd be kind of a pain to search through and access,
but the easier way of doing this is that we can create actually a structure
called a hash table where we hash.
We run all of our keys through a hash function, an equation,
that turns them all into some sort of a value
that then we can store onto essentially an array of linked list.
>> And so here, if we wanted to store English words,
we could potentially just, I don't know, turn all the first letters
into some sort of a number.
And so, for example, if I wanted A to be synonymous with apple--
or with the index of 0, and B to be synonymous with 1,
we can have 26 entries that can just store
all of the letters of the alphabet that we'll start with.
And then we can have apple at the index of 0.
We can have banana at the index of 1, cantaloupe at the index of 2,
and so on and so forth.
And thus if I wanted to search my hash table and access apple,
I know apple starts with an A, and I know exactly
that it must be and the hash table at index 0 because
of the function previously assigned.
>> So I don't know, we are a user program where
you'll be charged with arbitrarily-- not arbitrarily,
with trying to thoughtfully think of good equations
to be able to spread out all of your values
in a way they can easily access it later on with like an equation
that you, yourself, know.
So in the sense if I wanted to go to mango, I know, oh, it starts with m.
It must be at the index of 12.
I don't have to search through anything.
I know exactly-- I could just go to the index of 12 and pull that out.
>> Everyone clear on how a hash table's function works?
It's kind of just a more complex array.
That's all it is.
OK.
>> So I guess we run into this issue of what
happens if you have multiple things that give you the same index?
So say our function, all it did was take that first letter
and turn that into a respective 0 through 25 index.
That's totally fine if you only have one of each.
But the second you start having more, you're
going to have what's called a collision.
>> So if I try to insert bury into a hash table that already has banana on it,
what's going to happen when you try to insert that?
Bad things because banana already exists within the index
that you want to store it in.
Berry kind of is like, ah, what do I do?
I don't know where to go.
How do I resolve this?
>> And so you guys will kind of see we do this tricky thing
where we can kind of actually create linked list in our arrays.
And so the easiest way to think about this,
all hash table is an array of linked lists.
And so, in that sense, you have this beautiful array of pointers,
and then each pointer in that value, in that index,
can actually point to other things.
And so you have all these separate chains coming off of one big array.
>> And so here, if I wanted to insert berry,
I know, OK, I'm going to input it through my hash function.
I'm going to end up with the index of 1, and then I'm going to be able to have
just a smaller subset of this giant 140,000-word dictionary.
And then I can just look through 1/26 of that.
>> And so then I can just insert berry either before or after banana
in this case?
After, right?
And so you're going to want to insert this node after banana,
and so you're going to insert at the tail of that linked list.
I'm going to go back to this previous slide,
so you guys can see how hash function works.
>> So hash function is this equation that you're running kind of your input
through to get whatever index you want to assign it towards.
And so, in this example, all we wanted to do was take the first letter,
turn that into an index, then we can store that in our hash function.
All we're doing here is we're converting the first letter.
So keykey[0] is just the first letter of whatever string we're having,
we're passing in.
We're converting that to upper, and we're subtracting by uppercase A,
so all that is doing is giving us a number
in which we can hash our values onto.
>> And then we're going to return hash modulus SIZE.
Be very, very careful because, theoretically, here
your hash value could be infinite.
It could just go on and on and on.
It could be some really, really large value,
but because your hash table that you've created only has 26 indexes,
you want to make sure your modulusing so that you
don't run-- it's the same thing as your queue--
so that you don't run off the bottom of your hash function.
>> You want to wrap it back around the same way in [INAUDIBLE] when
you had like a very, very large letter, you
didn't want that to just run off the end.
Same thing here, you want to make sure it doesn't run off the end by wrapping
around to the top of the table.
So this is just a very simple hash function.
All that did was take the first letter of whatever our input was
and turn that into an index that we could put into our hash table.
>> Yeah, and so as I said before, the way that we resolve collisions
in our hash tables are having, what we call, chaining.
So if you try to insert multiple words that start with the same thing,
you're going to have one hash value.
Avocados and apple, if you've run it through our hash function,
are going to give you the same number, the number of 0.
And so the way we resolve that is that we can actually kind of link them
together via linked lists.
>> And so in this sense, you guys can see kind
of how data structures that we've been setting previously
like a raisin linked list kind of can come together into one.
And then you can create far more efficient data structures
that can handle larger amounts of data, that dynamically resize depending
on your needs.
Everyone clear?
Everyone kind of clear on what happens here?
>> If I wanted to insert-- what's a fruit that starts with, I don't know,
B, other than berry, banana.
>> AUDIENCE: Blackberry.
>> ANDI PENG: Blackberry, blackberry.
Where does blackberry go here?
Well, we actually haven't sorted this yet, but theoretically
if we wanted to have this in alphabetical order,
where should blackberry go?
>> AUDIENCE: [INAUDIBLE]
>> ANDI PENG: Exactly, after here, right?
But since it's very difficult to reorder-- I guess it's up to you guys.
You guys can totally implement whatever you want.
The more efficient way of doing this perhaps
would be to sort your linked list into alphabetical order,
and so when you're inserting things, you want
to be sure to insert them into alphabetical order
so that then when you're trying to search them,
you don't have to traverse everything.
You know exactly where it is, and it's easier.
>> But if you kind of have things interspersed randomly,
you're still going to have to traverse it anyways.
And so if I wanted to just insert blackberry here
and I wanted to search for it, I know, oh, blackberry
must start with the index of 1, so I know instantaneously just search at 1.
And then I can kind of traverse the linked list
until I get to blackberry, and then-- yeah?
>> AUDIENCE: If you're trying to create-- I guess like this is a very simple hash
function.
And if we wanted to do multiple layers of that like,
OK, we want to separate into like all the alphabetical letters
and then again to like another set of alphabetical letters within that,
are we putting like a hash table within a hash table,
or like a function within a function?
Or is that--
>> ANDI PENG: So your hash function-- your hash table
can be as large as you want it to.
So in this sense, I thought it was very easy, very
simple for me to just sort based on letters of the first word.
And so there's only 26 options.
I can only get 26 options from 0 to 25 because they can only
start from A to Z. But If you wanted to add, perhaps, more complexity
or faster run time to your hash table, you absolutely
can do all sorts of things.
You can make your own equation that gives you
more distribution in your words, then when you search,
it's going to be faster.
>> It's totally up to you guys how you want to implement that.
Think of it as just buckets.
If I wanted to have 26 buckets, I'm going
to sort things into those buckets.
But I'm going to have a bunch of stuff in each bucket,
so if you want to make it faster and more efficient,
let me have a hundred buckets.
>> But then you have to figure out a way to sort things so that they are
in the proper bucket they should be in.
But then when you actually want to look at that bucket,
it's a lot faster because there's less stuff in each bucket.
And so, yeah, that's actually the trick for you guys in pset5
is that you'll be challenged to just create
whatever is the most efficient function you can think of to be
able to store and check these values.
>> Totally up to you guys however you want to do it,
but that's a really good point.
That the kind of logic you want to start thinking about
is, well, why don't I make more buckets.
And then I have to search less things, and then maybe I
have a different hash function.
>> Yeah, there's a lot of ways to do this pset, some are faster than others.
I'm totally going to just see how fast was the fastest you guys will
be able to get your functions to work.
OK, everyone good on chaining and hash tables?
It's actually like a very simple concept if you think about it.
All it is is separating whatever your inputs are into buckets,
sorting them, and then searching the lists that there's associated with.
>> Cool.
All right, now we have a different sort of data structure that's called a tree.
Let's go on and talk about tries which are distinctly different,
but in the same category.
Essentially, all a tree is instead of organizing data in the linear way
that a hash table does-- you know, it's got a top and a bottom
and then you kind of link off of it-- a tree has a top which you call the root,
and then it has leaves all around it.
>> And so all you have here is just the top node
that points to other nodes, that points to more nodes, and so on and so forth.
And so you just have splitting branches.
It's just a different way of organizing data, and because we call it a tree,
you guys just-- it's just modeled out to look like a tree.
That's why we call it trees.
>> Hash table looks like a table.
A tree just looks like a tree.
All it is is a separate way of organizing nodes
depending on what your needs are.
>> So you have a root and then you have leaves.
The way that we can particularly think about it is a binary tree,
a binary tree is just a specific type of a tree
where each node only points to, at max, two other nodes.
And so here you have distinct symmetry in your tree
that makes it easier to kind of look at what values you are because then you
have always a left or a right.
There's never like a left third from the left or a fourth from the left.
It's just you have a left and a right and you can search either of those two.
And so why is this useful?
The way that this is useful is if you're looking
to search through values, right?
Rather than implementing binary search in an error array,
if you wanted to be able to insert nodes and take away nodes at will and also
preserve the search capacities of binary search.
So in this way, we're kind of tricking-- remember when we
said linked lists can't binary search?
We're kind of creating a data structure that tricks that into working.
>> And so because linked lists are linear, they only link one after the other.
We can kind of have different sort of pointers
that point to different nodes that can help us with search.
And so here, if I wanted to have a binary search tree,
I know that my middle if 55.
I'm just going to create that as my middle, as my root,
and then I'm going to have values spin off of it.
>> So here, if I'm going to search for the value of 66, I can start at 55.
It's 66 greater than 55?
Yes it is, so I know I mus search i n the right pointer of this tree.
I go to 77.
OK, is 66 less than or greater than 77?
It's less than, so you know, oh, that has to be the left node.
>> And so here we're kind of preserving all of the great things about arrays,
so like dynamic resizing of objects, being
able to insert and delete at will, without having to worry about the fixed
amount of space.
We still preserve all of those wonderful things
while also being able to preserve the log and search time of binary search
that we were only previously able to get a phrase.
>> Cool data structure, kind of complex to implement, the node.
As you can see, all it is the struct of the node
is that you have a left and a right pointer.
That's all it is.
So rather than just having an x or a previous.
You have a left or a right, and then you can kind of link them together
however you so choose.
>> OK, we're actually going just take a few minutes.
So we're going to go back here.
As I said previously, I kind of explained
the logic behind how we would search through this.
We're going to try pseudocoding this out to see
if we can kind of apply the same logic of binary search
to a different type of data structure.
If you guys want to take like a couple minutes to just think about this.
OK.
All right, I'm going to actually just give you the-- no,
we'll talk about the pseudocode first.
So does anyone want to give a stab at what
the first thing you want to do when you're starting out searching is?
If we're looking for the value of 66, what's
the first thing we want to do if we want to binary search this tree?
>> AUDIENCE: You want to look right and look left and see [INAUDIBLE]
greater number.
>> ANDI PENG: Yeah, exactly.
So you're going to look at your root.
There's lots of ways you can call it, your parent node people say.
I like to say root because that's like the root of the tree.
You're going to look at your root node, and you're
going to see is 66 greater than or less than 55.
And if it's greater than, well, it is greater than, where do we want to look?
Where do we want to search now, right?
We want to search the right half of this tree.
>> So we have, conveniently, a pointer that points to the right.
And so then we can set our new root to be 77.
We can just go to wherever the pointer is pointing.
Well, oh, here we're starting at 77, and we can just
do this recursively again and again.
In this way, you kind of have a function.
You have a way of searching that you can just repeat over and over and over,
depending on where you want to look until you eventually get to the value
that you're searching for.
Make sense?
>> I'm about to show you the actual code, and it's a lot of code.
No need to freak out.
We'll talk through it.
>> Actually, no.
That was just pseudocode.
OK, that was just the pseudocode, which is a bit complex,
but it's totally fine.
Everyone following along here?
If the root is null, return false because that means
you don't even have anything there.
>> If root n is the value, so if it happens to be the one you're looking at,
then you're going to return true because you know you found it.
But if the value is less than root of n, you're
going to search the left child or the left leaf,
whatever you want to call it.
And if the value is greater than root, you're going to search the right tree,
then just run the function through search again.
>> And if root is null, that that means you've reached the end?
That means you have no more more leaves to search,
then you know, oh, I guess it's not in here
because after I've looked through the whole thing and it's not here,
it just might not be here.
>> Does that make sense to everybody?
So it's like binary search preserving the capabilities of linked lists.
Cool, and so the second type of data structure you guys
can try implementing on your pset, you only have to choose one method.
But perhaps an alternative method to the hash table is what we call a trie.
>> All a trie is is a specific type of tree that
has values that go to other values.
So instead of having a binary tree in the sense that only one
thing can point to two, you can have one thing point to many, many things.
You essentially have arrays inside of which you store
pointers that point to other arrays.
>> So the node of how we would define a trie
is we want to have a Boolean, c word, right?
So the node is Boolean like true or false,
first of all at the head of that array, is this a word?
Secondly, you want to have pointers to whatever the rest of them are.
A bit complex, a bit abstract, but I will explain what that all means.
>> So here, at the top, if you have an array declared already,
a node where you have a Boolean value stored at the front
that tells you is this a word?
Is this not a word?
And then you have the rest of your array that
actually stores all the possibilities of what it could be.
So, for example, like at the top you have
the first thing that says true or false, yes or no, this is a word.
>> And then you have 0 through 26 of the letters that you can store.
If I wanted to search here for bat, I go to the top
and I look for B. I find B in my array, and so I know, OK, is B a word?
B is not a word, so thus I must keep searching.
I go from B, and I look to the pointer that B points towards
and I see another array of information, the same structure that we had before.
>> And here-- oh, the next letter in [INAUDIBLE] is A.
So we look in that array.
We find the eighth value, and then we look to see, oh,
hey, is that a word, is B-A a word?
It is not a word.
We've got to keep looking.
>> And so then we look to where the pointer of A points,
and it points to another way in which we have more value stored.
And eventually, we get to B-A-T, which is a word.
And so the next time you look, you're going
to have that check of, yes, this Boolean function is true.
And so in the sense we're kind of having a tree with arrays.
>> So then you can kind of search down.
Rather than hashing a function and assigning values by linked list,
you can just implement a trie that searches downwords.
Really, really complicated stuff.
Not easy to think about because I'm like spitting so many data structures out
at you, but does everyone kind of understand how the logic of this works?
>> OK, cool.
So B-A-T, and then you're going to search.
The next time you're going to see, oh, hey, it's true,
thus I know this must be a word.
>> Same thing for zoo.
So here's the thing right now, if we wanted to search for zoo, right now,
currently zoo is not a word in our dictionary
because, as you guys can see, the first place that we have a Boolean
return true is at the end of zoom.
We have Z-O-O-M.
>> And so here, we don't actually have the word, zoo, in our dictionary
because this check box is not checked.
So the computer doesn't know that zoo is a word
because the way that we've stored it, only a zoom here
actually has a Boolean value that's been turned true.
So if we want to insert the word, zoo, into our dictionary,
how would we go about doing that?
What do we have to do to make sure our computer knows that Z-O-O is a word
and not the first word is Z-O-O-M?
>> AUDIENCE: [INAUDIBLE]
>> ANDI PENG: Exactly, we want to make sure that this
here, that Boolean value is checked off that it's true.
Z-O-O, then we're going to check that, so we know exactly, hey, zoo is a word.
I'm going to tell the computer that it's a word so
that when the computer checks, it knows that zoo is a word.
>> Because remember all these data structures, it's very easy for us
to say, oh, bat's a word.
Zoo's a word.
Zoom's a word.
But when you're building it, the computer has no idea.
>> So you have to tell it exactly at what point is this a word?
At what point is it not a word?
And at what point do I need to search things,
and at what point do I need to go next?
Everyone clear of that?
Cool.
>> And so then comes the problem of how would we
go about inserting something that's actually not there?
So let's just say we want to insert the word, bath, into our trie.
As you guys can see like currently all we have now is B-A-T,
and this new data structure there had a pint that
pointed to null because we assume that, oh, there's no words after B-A-T,
why do we need to keep having things after that T.
>> But the problem arises if we do you want to have a word that comes after
the T's.
If you have bath, you're going to want an H right.
And so the way we're going to do that is we're going to create a separate node.
We're not allot whatever amount of memory for this new array,
and we're going to reassign pointers.
>> We're going to assign the H, First of all, this null,
we're going to get rid of.
We're going to have the H point downwards.
If we see an H, we want it to go to somewhere else.
>> In here, we can then check off yes.
If we hit an H after the T, oh, then we know that this is a word.
The Boolean is going to return true.
Everyone clear on how that happened?
OK.
>> So essentially, all of these data structures
that we've gone over today, I've gone over them really, really quickly
and not in to much detail, and that's OK.
Once you start messing with it, you'll be
keeping track of where all the pointers are,
what's going on in your data structures, et cetera.
They'll be very useful, and it's up to you
guys to totally figure out how you want to implement things.
>> And so pset4, of 5-- oh, that is wrong.
Pset5 is misspellings.
As I said before, you're going to, once again, download source code from us.
There's going to be three main things you'll be downloading.
You'll download dictionaries, kers, and texts.
>> All those things are are either dictionaries of words
that we want you to check or test of information
that we want you to spell check.
And so the dictionaries we give you are going
to give you actual words that we want you to store somehow in a way that's
more efficient than an array.
And then the texts are going to be what we're
asking you to spell check to make sure all of the words there are real words.
>> And so the three blocks of programs that we'll give you
are called dictionary.c, dictionary.h, and speller.c.
And so all dictionary.c does is what you're asked to implement.
It loads words.
It spell checks them, and it makes sure that everything is inserted properly.
>> diction.h is just a library file that declares all those functions.
And speller.c, we're going to give you.
You don't need to modify any of it.
All speller.c does is take that, loads it, checks the speed of it,
tests the benchmark of like how quickly you're able to do things.
>> It's a speller.
Just don't mess with it, but make sure you understand what it's doing.
We use a function called getrusage that tests the performance of your spell
checker.
All it does is basically test the time of everything in your dictionary,
so make sure you understand it.
Be careful to not mess with it or else things will not run properly.
>> And the bulk of this challenge is for you guys to really modify dictionary.c.
We're going to give you 140,000 words in a dictionary.
We're going to give you a text file that has those words,
and we want you to be able to organize them into a hash table or a trie
because when we ask you to spell check-- imagine if you're spell
checking like Homer's Odyssey.
It's like this huge, huge test.
>> Imagine if every single word you had to look
through an array of 140,000 values.
That would take forever for your machine to run.
That is why we want to organize our data into more efficient data structures
such as a hash table or a trie.
And then you guys can kind of when you search access
things more easily and more quickly.
>> And so be careful to resolve collisions.
You're going to get a bunch of words of that start with A.
You're going to get a bunch words that start with B. Up to you
guys how you want to resolve it.
Perhaps there's more efficient hash function
than just the first letter of something, and so that's up to you
guys to kind of do whatever you want.
>> Maybe you want to add all the letters together.
Maybe you want to like do weird things to account the number of letters,
whatever.
Up to you guys how you want to do.
If you want to do a hash table, if you want to try a trie, totally up to you.
I will warn you ahead of time that the trie is typically a bit more difficult
just because there's a lot more pointers to keep track of.
But totally up to you guys.
It's far more efficient in most instances.
You want to really be able to keep track of all of your pointers.
Like do the same thing that I was doing here.
When you're trying to insert values into a hash table or delete,
make sure that you're really keeping track
of where everything is because it's really easy for if I'm
trying to insert like the word, andy.
Let's just say that's a real word, the word, andy,
into a giant list of A words.
>> If I just happen to reassign a pointer wrong, oops,
there goes the entirety of the rest of my linked list.
Now the only word I have is andy, and now
all of the other words in the dictionary have been lost.
And so you want to make sure you keep track of all of your pointers
or else you're going to get huge problems in your code.
Draw things out carefully step by step.
It makes it a lot easier to think of.
>> And lastly, you want to be able to test your performance of your program
on the big board.
If you guys take a look at CS50 right now,
we have what's called the big board.
It is the score sheet of the fastest spell checking times across all of CS50
right now, I think the top like 10 times I think eight of them are staff.
We really want you guys to beat us.
>> All of us were trying to implement the fastest code as possible.
We want you guys to try to challenge us and implement faster than all of us
can.
And so this is really the first time that we're
asking you guys to do a pset that you can really do in whatever method
you want.
>> I always say, this is more akin to a real-life solution, right?
I say, hey, I need you to do this.
Build a program that does this for me.
Do it however you want.
I just know that I want to fast.
That's your challenge for this week.
You guys, we're going to give you a task.
We're going to give you a challenge.
And then it's up to you guys to completely just figure out
what's the quickest and most efficient way to implement this.
Yeah?
>> AUDIENCE: Are we allowed to if wanted to research faster ways
to do hash tables online, can we do that and cite someone else's code?
ANDI PENG: Yeah, totally fine.
So if you guys read the spec, there's a line
in the spec that says you guys are totally free to research hash
functions on what are some of the quicker hash functions
to run things through as long as you cite that code.
So some people have already figured out fast ways
of doing spell checkers, of fast ways of storing information.
Totally up to you guys if you want to just take that, right?
Make sure you're citing.
The challenge here really that we're trying to test
is making sure that you know your way around pointers.
As far as you implementing the actual hash function
and coming up with like the math to do that,
you guys can research whatever methods online you guys want.
Yeah?
>> AUDIENCE: Can we cite just by using the [INAUDIBLE]?
>> ANDI PENG: Yeah.
You can just, in your comment, you can cite like, oh,
taken from yada, yada, yada, hash function.
Anyone have any questions?
We actually breezed through section today.
I will be up here to answer questions as well.
>> Also, as I said, office hours tonight and tomorrow.
The spec this week is actually super easy and super short to read.
I would suggest taking a look, just read through the entirety of it.
>> And Zamyla actually walks you through each of the functions
you need to implement, and so it's very, very clear how to do everything.
Just to make sure you're keeping track of pointers.
This is a very challenging pset.
>> It's not challenging because like, oh, the concepts are so much more
difficult, or you have to learn so much new syntax the way
that you did for the last pset.
This pset is difficult because there are so many pointers,
and then it's very, very easy to once you have a bug in your code not be able
to find where that bug is.
>> And so complete and utter faith in you guys to be able to beat our [INAUDIBLE]
spellings.
I actually haven't any written mine yet, but I'm about to write mine.
So while you're writing yours, I'll be writing mine.
I'm going to try to make mine faster than yours.
We'll see who has the fastest one.
>> And yeah, I will see all of you guys here on Tuesday.
I will run a kind like a pset workshop.
All of the sections this week are pset workshops,
so you guys have lots of opportunities for help, office hours as always,
and I really look forward to reading all of your guys' code.
I have quizzes up here if you guys want to come get those.
That's all.