SPEAKER 1: All right.

So this is CS50.

And this is the start of week 3.

And you'll recall that last time, we introduced a number of new ideas

that we'll now start taking for granted as being already under our belt.

In particular, we looked last time at debugging more generally.

And recall that debugging is the process of removing bugs from your code,

removing mistakes from your code.

And we proposed these three CS50-specific tools.

In particular, help50, which is a command line tool.

Something that you can run at your keyboard

and actually run it before your own command.

So that if you don't understand some error

message from a program you're compiling or a command you're running,

you can actually see some helpful output from CS50 staff.

eprintf, which, by contrast, is something you can put into your code,

like printf, and print a message to yourself.

And nicely enough, it's going to actually include the line number

and the file name from which it came.

So you can identify where some output is coming.

And then lastly, debug 50 which is the most sophisticated of these programs.

And debug 50 when you run it at the command line,

followed by the name of your program in the usual way,

it's actually going to open up what's called a debugger.

A graphical user interface that CS50 staff put together

that will actually let you step through your code,

see variables, and generally understand it better.

So we also looked at this in the context of Ovaltine

in particular, and Little Ralphy.

And we looked at cryptography, the art of concealing information.

And indeed, among the challenges in CS50,

ultimately if you choose to accept them, are

things like implementing Caesar cipher and Vigenere

cipher, cracking passwords.

So indeed, those problems lie ahead and draw inspiration from this domain.

And then, we focused more technically on what a string is.

So Zamyla, a name we keep taking for granted, that a computer can express.

Z-A-M-Y-L-A, as a string or a phrase in a program.

But it turns out that underneath the hood,

strings are a little more mundane.

They really are just this grid of information.

And we might draw Zamyla's characters boxed in like this.

But if you think of what's inside of your computer itself,

you have a whole bunch of memory, or RAM.

And inside of that RAM, you have Z-A-M-Y-L-A,

but then this special character.

What is this /0 used for.

Why is there this seemingly strange character at the end of Zamyla's name?

Anyone?

Yeah.

AUDIENCE: [INAUDIBLE].

SPEAKER 1: Yeah, to denote the end of the string.

Because after all, if we were to have someone else's name here,

if the next string I got is Maria, for instance.

M-A-R-I-A, we need to be able to know where Zamyla's name ends

and Maria's name starts in memory.

Because at the end of the day, C, and programming in particular,

isn't really all that sophisticated.

At the end of the day, the only place you have to store things

is your computer's memory or RAM.

And each of these boxes represents a byte of memory inside of your computer.

And so if all this is-- so far as the computer cares--

is a sequence of six alphabetical letters,

the computer needs to be told or given a hint as with this /0,

which just represents 8 zero bits, as to where Zamyla's name ends and something

else begins.

And we use this as an opportunity to introduce ultimately

command line arguments.

So in particular, we've been writing programs thus far

with just int main void.

And void, we realized, signifies that a program takes no command line inputs.

It can still call functions, like get string and get int and get [? flow. ?]

But when you run the program, you can't put any additional words at the prompt

after it if you've declared main as taking void as input.

Nothing as input.

But we introduced instead this, int main int arg

c string arg v open bracket close bracket, which

means main can alternatively take two inputs from the so-called command line

when you run it.

It can take arg c and arg v. And what was arg c?

What was arg c?

Arg c.

Yeah, argument.

Yeah.

AUDIENCE: [INAUDIBLE].

SPEAKER 1: Yeah, the number of command line arguments.

Arg c for argument count.

So how many words did you type at the prompt?

And arg v means argument vector, which is

another way of saying it's an array, a contiguous block of memory

inside of which are all of the words themselves

that you might have typed at the prompt.

So this time, we're going to build on that.

We're going to focus today mostly on ideas.

Mostly on algorithms.

Mostly on problem-solving and less on the lower-level implementation

details of code.

Though, we'll look at a couple of examples.

So this more generally is what's called an array.

If you think of your computer's memory as just a block of memory,

block of bytes.

And maybe it's byte 0, then byte 1.

Then, byte 2, just because you can number them, certainly.

If you think of them that way, this is kind of an arbitrary generic data

structure, if you will.

A generic way of just storing things underneath the hood.

Now, what do I mean by that?

And why is this useful?

Well, consider something like this.

Consider having 8 doors, behind which are some numbers.

And the goal at hand is to solve a problem.

Find a number behind these doors.

Now, unfortunately, you don't know in advance

what numbers are behind those doors and where they are.

Indeed, that's why the doors are closed.

But you know that, say, the number 50 is somewhere behind those doors.

So what do we do to actually find this?

Well, let's go ahead and do this.

Let me go ahead and summon up a brave volunteer if you would.

There's a CS50 stress ball in it for you.

OK, come on up.

You want to come up on up over here?

So we have not 8, but rather 7 doors here.

Even easier.

So 7/8 the size.

And what's your name?

AUDIENCE: Derek [INAUDIBLE].

SPEAKER 1: Derek?

OK.

David, come on up.

Nice to meet you.

All right.

So here we have 7 doors.

And the goal at hand for you is to simply find the number 50.

How do we find it?

What are you going to do?

AUDIENCE: [INAUDIBLE].

SPEAKER 1: It's behind one of these doors, I think.

AUDIENCE: All right.

I'll just try a door?

SPEAKER 1: Try a door.

Not the door.

So 16 turns up.

OK.

Stress ball gets one step away.

Try another.

42.

Answer to life, the universe, and everything, but not this question.

50.

OK, very well done.

So a round of applause if we could for Derek here.

Very nicely done.

OK.

And let's pause for just a moment.

What was the algorithm?

What was the set of instructions that you used to find the number 50?

AUDIENCE: Just try and see if I could find any sort of arrangement.

But otherwise, try random doors.

SPEAKER 1: OK.

So try random doors.

And indeed, given no additional information from me,

that's the best you can do.

Just try random doors.

Or, if it's a little easier, just go left to right or right to left.

But random is perfectly equivalent to all of those algorithms

because you don't know anything necessarily a priori.

So how about for two stress balls?

Find the number 50 this time, but the additional ingredient

is that we have taken the time in advance

to sort the numbers behind these doors.

Does that change your thinking in any way?

AUDIENCE: Well, I don't know whether you're

sorting increasing left or right.

SPEAKER 1: Good.

So good challenge.

He doesn't know if we've sorted from left to right or right to left.

Left to right.

So generally, a computer scientist when he or she says "sorted"

would say left to right.

But reasonable question.

AUDIENCE: Left to right increasing or decreasing?

SPEAKER 1: Left to right increasing.

Yes.

It would be left to right in any way.

16.

Not 50.

So what are you going to do?

AUDIENCE: Well, let's see.

I know these have to be less, so I can remove them.

SPEAKER 1: Good.

AUDIENCE: [INAUDIBLE].

SPEAKER 1: 42 is still not 50.

And to the right.

Very well done for Derek.

OK, come on.

OK.

They're less impressed that time.

So what did you do, though, that second time that was actually more effective?

I mean, frankly, at first glance it looks like this approach was just as

fast or just as slow as your first approach

because it still took you through steps.

AUDIENCE: So what I did was since you told me that it was sorted left

to right increasing, I decided to look at the middle number first

and see whether it was greater than or less than--

SPEAKER 1: Good

AUDIENCE: --the target number.

SPEAKER 1: Good.

AUDIENCE: And since it was less than, I knew that all of these three values--

SPEAKER 1: Wonderful.

And indeed, are smaller by design.

And so you can throw half of that problem away, much like in week 0

when we tore the phone book in half.

You can throw half of that phone book away as well.

So thank you very much for finding us the number 50.

So this is something that we did see, indeed, in week 0.

And it's what we would generally call binary search.

Or more generally, just a divide and conquer algorithm.

But today, what we start to do is to assess

just how much better this actually is.

And how we can go about finding things more programmatically.

So what Derek could have tried is what someone would generally

call linear search.

And as the name suggests, linear, meaning line,

you can just kind of solve a problem from left to right.

And indeed, while Derek did take a random approach,

it would have been functionally equivalent

for him simply to go left to right or right to left and find the number 50.

It's indeed there.

So let's introduce some pseudocode for this.

And there is no one right way to implement pseudocode.

Here is one of the most succinct ways I could come up

with for expressing this kind of left to right approach.

Or equivalently, right to left.

For each element in the array, if element you're looking for return true.

And so this is a very common paradigm in programming.

Just say something generally, like for each element in an array.

And the implication is that you would generally go left to right,

but it's equivalent to go right to left.

And if we indeed see at some location in that array

that array of boxes, the element we're looking for, we can just return true.

And yet, here I have return false.

But the indentation, so to speak, is very different.

Why have I aligned return false with the for loop