DAVID MALAN: All right, well, this is CS50.

And this is lecture 4.

And you'll recall that last time, we focused really on algorithms.

Not so much code, but on algorithms, the step-by-step instructions

for solving problems.

And we did this in the context of numbers.

But more specifically, we assumed that we had places to put these numbers.

We called it an array.

And that was back-to-back-to-back memory where we could put numbers or maybe

characters or something else.

But for the most part, we haven't really had more sophisticated ways

of laying information out in memory, and so we're kind of

stuck going left to right, right to left, or maybe a little more

intelligently using what we call binary search, or divide

and conquer, and kind of split the difference.

But we can start to get fancier.

Because if you recall, we have memory inside

of our computers, which we keep modeling as this rectangular region

with numbers and so forth.

But that's kind of a nice canvas, right?

Much like you could paint on a canvas, so could we kind of move things around

in memory.

But we don't yet have the vocabulary or really the data structures,

as they're going to be called, to do anything more

interesting than this linear approach.

And so today and next time when we begin to start

to solve problems more cleverly and then revisit some of the kinds of algorithms

that we've seen already, and those algorithms last time

were like these, linear search and binary search.

And that brought us full circle back to week zero when we used those,

albeit not by name.

And then recall that we introduced sorting.

Sorting's a more involved algorithm, more time-consuming.

But it was a precondition for which of those first two algorithms

to actually work?

Yeah, so binary search assumes, just like a phone book

assumes that the names are actually sorted from left to right.

Otherwise, you're completely wasting your time,

if you're splitting a phone book in half,

if there's no rhyme or reason to where the names and the numbers are.

So this is sort of a requisite ingredient

to get better efficiency with other algorithms.

And we're to see that moving forward.

And it's going to be up to decide, you know what?

It's going to take me more time to figure out

how to write the code for an algorithm than it

is to just write it the easy way, and just cut a corner

and run the code once.

But if you're a company, if you're a website,

if you're a piece of software that's doing the same algorithm again

and again and again, maybe you do want to spend that upfront cost.

Maybe it's human time, like your time, figuring out the algorithm.

Or maybe it's n squared or hopefully something better, n log n,

that you have to spend just to get the data in a nice format,

and then, thereafter, everything can be blazing fast.

So especially when we get to web programming,

we'll revisit these questions when we talk about databases as well.

But recall last time we also introduced a bit of formalism.

And we won't get more mathematical than this.

But These were sort of broad strokes with which

we can paint the efficiency of algorithms from sort of slowest on top

to fastest on the bottom.

And recall that we introduced some Greek symbols here just

to kind of standardize what it is we're talking about.

And as a quick check, big O refers to what kind of boundary?

The upper bound.

So maybe in the worst case, what's the upper bound on your algorithm's running

time?

How many steps, how many seconds, how many hours might it take?

By contrast, we had omega, which was the lower bound.

And then less commonly used, at least in CS50,

will be theta, which is just when those two are the same.

But realize those are the three ingredients,

especially if you continue on in other CS classes, that might be revisited.

And we introduce this, so that we're not just counting seconds.

We're not, like, looking at our watch and counting how fast our algorithm is,

because that's not a very reliable way of measuring whose algorithm is better

than someone else's.

Maybe my Mac is faster than your Mac or your PC.

And so we don't want to just look at raw time.

We want to think about things a little more theoretically,

albeit without worrying about denominators and lower order terms.

We talk generally in terms of these higher order terms

that we saw last time.

So I thought it would be fun to kind of reminisce.

Some years ago, when a certain someone was still

just a senator, being interviewed by Google's own Eric Schmidt,

who was the former CEO of Google.

And this was an interview that took an interesting algorithmic turn.

If we could dim the lights for a moment.

[VIDEO PLAYBACK]

[APPLAUSE]

- Now, Senator, you're here at Google.

And I like to think of the presidency as a job interview.

Now, it's hard to get a job--

- Right.

- --as president.

- Right.

- I mean, you're going through the rigors now.

It's also hard to get a job at Google.

- Right.

- We have questions.

And we ask our candidates questions.

And this one is from Larry Schwimmer.

- OK.

- What-- you guys think I'm kidding?

It's right here.

What is the most efficient way to sort a million 32-bit integers?

- Well, I--

- Maybe-- I'm sorry, maybe we should--

- --no, no, no, no, no, no, I think--

- That's not a fair question.

- --I think the bubble sort would be the wrong way to go.

- Come on.

Who told him this?

[END PLAYBACK]

DAVID MALAN: OK, so today we peel back the layers

that we've been assuming for some time now.

We've been talking about integers and characters.

But we also had this higher level concept

of a string, which was a generic way of saying

you had back-to-back characters that represent words

or sentences or paragraphs or whatnot.

But today we reveal that that's actually been a bit of a lie.

There actually is no such thing as string in the language called C.

And indeed, you might have kind of suspected

as much, given that we keep including cs50.h, which gives you things

like GetInt and GetString and so forth.

But it also gives you string, literally, a keyword

that actually doesn't come with C.

And before we peel back what exactly it is,

let's consider perhaps what problems it creates

and what powers it reveals to understand what's going on underneath the hood.

And let me propose that we try to implement, at least in pseudocode,

this algorithm here, swap.

So I proclaim that swap is a function whose purpose in life

is to take two inputs--

let's call it a and b--

and just swap them, so that a becomes b, and b becomes a.

And before we even get into the weeds of pseudocode or actual code,

we actually have two values here.

Might anyone like to join me onstage for just a moment for a drink of Gatorade?

A little Gatorade?

Around Maybe someone a little farther back today?

A little drink?

Yeah?

OK, come on down.

What's your name?

KATE: Kate.

DAVID MALAN: Kate, come on down.

Join me for some Gatorade onstage.

Welcome to Kate.

All right.

So the challenge at hand is this.

Let me just set us up here.

So we have some green.

That's very unnatural looking.

OK, we have some pink.

And you know what?

I think, actually, I'd like the pink, and maybe you could have green.

I need you to swap the values of these two cups if you could.

I need you to get the pink into the green cup and the green

into the pink cup.

KATE: I think I need another cup.

DAVID MALAN: OK, so she thinks she's going to need another cup.

And OK, so good.

I came prepared.

So we need another variable, if you will.

OK, so here we go, Kate.

Set us up.

All right, green goes into the empty cup.

All right, so pink goes into the former green cup.

And green goes-- most green goes back into the original cup.

Thank you so much to Kate.

Why don't we--

I don't know if you'd like that flavor.

Delicious.

OK, well, thank you very much.

Thanks for coming up.

Here we go.

Oh, and this.

Oh, and if you'd like.

KATE: Sure.

Thank you.

DAVID MALAN: So this was obviously very intuitive.

That one's not bad.

This is actually pretty intuitive, of course, for any of us in the room

that you obviously can very cleanly swap two values or two drinks.

You need some kind of temporary storage place.

And so we can introduce this in the form now of some actual code

by claiming that if you want to swap two values, you need the exact same idea.

So even if variables have seemed a little abstract

or you're at least used to them in the context of algebra x and y,

in a programming language, variables are just

like these empty cups into which you can put values.

In reality, it's green and pink.

But it could be a number, it could be a letter, or maybe something more.

Maybe even something like a string.

So we're going to come back to this idea.

Because if you agree that Kate's algorithm was correct,

once she had that temporary variable, it would

seem that this is a pretty reasonable translation to code.

Put store a in tmp.

So move a into the temporary variable, just like she did into the empty cup.

Then change a to be b.

And then change b to be what was a, which is currently in temp.

So it's kind of this three-step switcheroo,

just like Kate enacted for us here.

But recall last time that we have--

actually, let's do this.

Let me actually go ahead and open up a program here.

You know what?

Let me go ahead and open up, let's say, today's example

called noswap, which is a bit of a spoiler,

insofar as the name suggests what's actually going to or not

going to happen here.

And if I go ahead here and open this up in source 4.

Let me go ahead and open up noswap.

Let's take a look at what this program actually looks like.

Doesn't seem to do all that much.

But it does have a main routine up front.

And it's got an include of stdio.h.

And then what does main do?

It declares two variables, this time called x and y,

initializing them to 1 and 2 respectively.

And then a couple of printfs.

So printf x is such and such, y is such and such,

printing out its actual values.

So that's sort of week one use of printf.

And then we do the-- it looks like the exact same thing two lines later.

But in between those two lines is an actual function call to something

called swap, which, as it turns out, if we scroll down,

is literally the same thing as we had on the screen a moment ago.

I'm calling it a and b here, but I could have

called it anything I want, x and y, fu and bar, anything like that.

I have my temporary variable or temporary empty cup, like Kate had,