DAVID MALAN: All right.

This is CS50, and this is lecture three.

And today, the goal is to be a lot more algorithmic than code-oriented,

and to really kind of come back to where we started in lecture zero,

when we talked about computational thinking, and algorithms.

Because now you have a few weeks under your belt,

and you have a few new tools, and hopefully skills, under your belt,

even though odds are, you're still getting

comfortable with some of those skills.

And so let's look, then, at this piece of hardware

that we talked about a couple times.

And this is an example of what?

AUDIENCE: Memory.

DAVID MALAN: Yeah, memory, or RAM, random access memory.

And this happens to be pretty big on the screen,

but it's actually pretty small, if you were

to find it in your Mac, or PC, in your laptop, or some other device.

And this is just memory.

And so, memory is places you can store information-- numbers and characters

and strings, and bigger things still.

And recall that if you want to use this memory, you need to address it.

You need to put something in particular locations.

And we're going to start doing this all the more So in particular, there's

at least, like, five--

four black chips on here, which is actually where the zeros and ones are

stored, in the green circuit board.

And little gold connectors you see on the screen,

too-- that just allows all of those black chips

to intercommunicate, ultimately, and for the zeros and ones to move around.

But if we zoom in on just one of these chips of memory,

arbitrarily, and then zoom in here, you can think of this, wonderfully enough,

as a rectangle.

Could be any shape, certainly, but if we think about it as a rectangle,

we can divide this chip of memory up into a grid, like this.

Completely arbitrary how I've drawn this, but the fact, now,

that I have a whole bunch of small boxes--

you can start to think of this as being one byte, and then

another byte, and then another byte.

And I coincidentally wrote eight bytes across, but it could be any number.

It doesn't really matter.

And so, you can start to think about these bytes

as having specific locations, or numbers, or addresses,

as we're going to start calling them.

So if I zoom in on the top of this, you could

start to think of the top left as being byte number 0,

because computer scientists generally start

counting at zero, and then byte 1, and 2, and 3, and 4, and dot dot dot.

And then, just as a refresher, in a typical Mac or PC these days,

how much RAM, or memory, would you typically have?

AUDIENCE: Four?

DAVID MALAN: Four what?

AUDIENCE: Four gigabytes.

DAVID MALAN: Four gigabytes.

And giga means billion, so that's four billion bytes.

And maybe you have a little less, maybe you have a little more,

but on the order of billions of bytes.

So we're only scratching the surface of just how much storage there is,

and how many numbers and characters you can store.

But the point is that we can address them, in some way-- zero, one, two,

and so forth.

So this is how we stored Stelios' name in memory.

Recall, this was an example last time, where

we needed to put the characters of his name somewhere.

And so we actually put the S, and then the T,

and then so forth, starting at the leftmost location on forward.

But we also put something else.

It's not sufficient just to put the letters of his name in memory.

What else did we have to do?

AUDIENCE: Put a zero in there?

DAVID MALAN: Yeah, the zero command, or more specifically, the zero byte,

or the so-called null byte--

N-U-L. And it's represented as backslash 0.

Because if you were just to type a normal zero,

that would technically be a character from your keyboard.

It looks like a number, but it's technically a character, a char.

And so backslash zero literally means 8-0 bits in that byte's location.

OK.

So now that we have this ability to represent Stelios

with a sequence of characters, null-terminated at the end,

we don't really need to worry about the hardware anymore.

Right?

We can abstract away from that just as we did in week zero,

and not worry about how those zeros and ones are stored.

We can just trust that they are, somehow.

And so we can abstract away, and just start

thinking about it as a sequence, or a grid, of letters like this.

But that backslash zero is important, because it

is the only way that this language we're currently using,

C, knows where strings end.

If you didn't have that, it would-- printf, for instance,

might just keep printing all of the contents, all four gigabytes, of memory

that your computer has, no matter what those characters actually are.

And then, of course, you couldn't distinguish Stelios' name from Maria,

or someone else altogether in memory.

So, let me go ahead and open up the IDE, just to demonstrate now what

you can do with this kind of knowledge.

Suppose I wanted to write a program that allows

me to let a user type in his or her name,

and then I just want to print out his or her initials.

And for simplicity, I'm going to assume that the person's initials,

or whatever the capitalized letters are, in the input they type.

So, I have to be a little nit-picky, and type in my name properly.

But with that said, let me go ahead and whip this up.

So, I'm going to save this as initials.c.

Just out of habit, I'm going to start by including the CS50 library,

because I'm going to want to get a string from the user.

I'm going to go ahead and include standard io.h, so that I

can print something to the screen.

And we'll decide later if we need anything more.

I don't need any command line arguments for the purpose of this program,

so I'm going to go back to our old version of main, where you just

specify void-- no argc, no argv.

And then here, let me go ahead and declare a string called s,

and get a name from the user, as with, "name," and get string.

And then, what do I want to do after this?

I want to go ahead and iterate over the characters in the user's name,

and print them out only if they're uppercase.

But you know what, rather than just print them out,

you know what I want to do?

I actually want to create a new string, myself, containing the user's initials.

So, I don't want to go ahead and just print out, with percent

c, one character after the other-- rather, I

want to go ahead and store the user's actual initials in a new string,

so that I've got one string for their name,

and one string for their initials.

And, ladies and gentlemen, Ian.

SPEAKER 2: Sorry for the video glitches.

DAVID MALAN: Thanks.

All right.

So, to be ever more clear, let me go ahead and rename this

to name, literally, and then I want to have a string for their initials.

But we know what a string is, as of last time.

It's really just a sequence of characters.

And a sequence really has another name in programming.

What is another synonym we've used for a sequence of something?

AUDIENCE: [INAUDIBLE]

DAVID MALAN: An array.

An array is that data structure we had when we

started using square bracket notation.

So, if I actually kind of roll this back and break the abstraction,

if you will-- don't think about it as a string.

What is a string?

It's a sequence of characters.

Technically, I could say char, and then I could say initials,

and then I can specify however many letters I

want to support in a human's initials.

And by-- assuming we have a first name, maybe a middle name, and a last name,

three characters should do it.

Three characters.

So, David J. Malan, DJM, three characters.

Is that enough chars?

AUDIENCE: [INAUDIBLE]

DAVID MALAN: I'm hesitating, because it doesn't--

AUDIENCE: [INAUDIBLE]

DAVID MALAN: It's not, but why?

AUDIENCE: You need for the null character.

DAVID MALAN: Yeah.

So if we want to terminate even my initials-- which isn't technically

a word, but it's certainly a string, it's

a sequence of characters-- we need a fourth character,

or we need to anticipate a fourth character,

so that whatever we put in the computer's memory is technically,

in my case-- like, D-J-M backslash 0.

You need that fourth byte.

Otherwise you do not have room to actually terminate the string.

So, now, even though this doesn't look like a string,

insofar as I'm not saying the word string, it really is.

It's a sequence of characters of size four that I can put characters in.

Now, what are the characters in this array, by default, have we said?

When you just declare a variable of some size, what values go in it?

AUDIENCE: [INAUDIBLE]

DAVID MALAN: Sometimes zeros, but generally,

what's the better rule of thumb?

AUDIENCE: You don't know.

DAVID MALAN: Yeah, you don't know.

It's so-called garbage values.

Nothing-- you should not trust the value of a variable, generally

speaking, unless you yourself have put the value there, as by storing it,

with the assignment operator, or by manually typing it in yourself.

So, just to be clear, if I wanted this program

to be kind of useless for anyone except myself, I could actually do this--

I could go ahead and do--

initials, bracket 0, get "d", initials, bracket 1, get "j",

and then finally initials, bracket 2, get "m".

And then lastly, and this is the thing you might forget sometimes,

you actually need to do the backslash zero there.

But of course, this is not at all dynamic.

But I have, in this these lines of code now,

created a new string called initials.

It's of length-- it's of human length three, DJM,

but the computer is actually using 4 bytes to store it.

But this is not the point of the exercise,

because we already asked the user for his or her name.

I need to now figure what that is.

So just logically, or algorithmically, if you will,

what process could we use, given a name like David J. Malan, or Brian Yu,

or anyone else's name--

how could we look at that input and figure out

what the user's initials are?

What's the thought process?

Let me go a little farther back.

So, David J. Malan, or any other name.

What's the process?

What do you think?

AUDIENCE: [INAUDIBLE]

DAVID MALAN: OK, good!

So, iterate with a for loop over the letters in the name-- and you've

done that before, or in the process of doing that,

for something like caesar or vigenere, most likely.

And then you can use something like is upper,

or you can even do asciimath, like we did a while ago, to actually determine,

is it in the range of A to Z capitals on both ends?

So we have a couple of options.

So, let me try to convert that to code.

Let me get rid of the hard-coded name, which

is just kind of nonsensical, but demonstrative of how

we could store arbitrary characters.

And now let me do this.

For int i get 0, i is less than the string length of name, i plus plus--

and then I'm going to do something like this.

If the i-th character character in name is an uppercase letter--

and I'm going to use a function that you might not have used yourself,

but recall that it does exist--

is upper will return, essentially, true or false, this is an uppercase letter--

so, if this is uppercase, I'm going to go ahead and do what?

Well, the story is not quite complete.

It's not enough to just iterate over the names and--