DAVID J. MALAN: All right, this is CS50, and this is week 4.

So let's consider first what we did last time, which was focus on numbers

and focus on how we can search them and how we can sort them.

And in particular, we took a look at a number of algorithms

that we finally gave names to, a couple of which we actually saw back in week

0, but didn't treat as formally.

So we looked more formally last time at linear search,

this process of searching elements from left to right or right to left

as though you're walking along a line looking for some value.

We looked at binary search, a divide and conquer algorithm

whereby we started, in this case, in the middle,

and then we looked left to right and then went to the left,

went to the right, and then did the same problem again and again.

We looked also at bubble sort.

How do you get to the point where you can

use an algorithm like binary search, which

assumes that your inputs are sorted?

So how do you get to that sorted state?

Well, bubble sort was one algorithm that essentially

swapped elements pairwise from left to right, from left to right,

until finally the biggest elements bubbled up to the top,

and the whole list was ultimately sorted.

But we also looked at selection sort.

And selection sort is the name implied, selected,

then smallest element again and again and again, plucking it out of the list,

and putting it where it belongs.

Insertion sort, meanwhile, walked through the list really just once,

and as it encountered each element, it then

inserted it into the sorted half of the list, the left half of the list

in its proper place.

And then lastly, and where we really concluded and really got more bang

for our buck was this final algorithm merge

sort, which actually solved this same problem no less correctly, but so much

more efficiently.

And indeed, lends itself perhaps to a fundamentally better design

in so far as it leverages a much better running time, so to speak.

In fact, we started to ascribe these kinds of formulas

to the running times of or the performance of our algorithms n

squared, otherwise known as quadratic, whereby

you take n times n number of steps or minutes or seconds

or some unit of measure, n log in, which is actually what we achieved

with the merge source, which was much faster

recall than the end squared algorithms like bubble sort and selection sort

and insertion sort in their upper bounds.

n would be something linear, like a straight line relationship.

Logarithmic of n, log of n, log base 2 of n,

technically, would be something like week 0's divide

and conquer approach looking for Mike Smith,

as well as last time's binary search.

And then one, which doesn't have to be literally one step.

Maybe it's two, maybe it's 10, but it is a fixed finite constant number

of steps.

And that too might be the running time of some algorithm.

Now how do we describe the running times of algorithms?

Well, we use some special notation, asymptotic notation,

so to speak, which while it might look cryptic at first glance,

really is just a handy way of succinctly expressing the fact that you know what

the upper bound on some algorithms running time is,

what the lower bounds on some algorithms running time is.

And if those are one in the same formulas in theta,

do you have a coincidence of the two of big O, so speak, and capital theta.

So that, while Greek, literally is just a way

of expressing a bit more succinctly what these running times are.

And we'll continue to revisit this issue as we

look at more algorithms and soon data structures still.

But this time, we apologize.

We pull back a layer here and admit that there is no such thing as a string.

Indeed, all this time we've been saying that there's ins, and there's floats,

and there's chars, and there's doubles and more.

And we've also been saying there are strings,

but there really aren't strings.

This is sort of a figment of the imagination of our so-called CS50

library.

But it's a pedagogical simplification that we've

been using for the past several weeks, so as to not get

lost in the weeds, the lower level implementation

details of what a string is, so that we can just get

real work done in these first weeks.

But now we'll begin to look underneath that hood

and see what a string actually is and what the implications are.

And it turns out, while more complicated in some sense,

it really just boils down to some first principles,

what it is the computer is doing underneath that hood.

So let's take a look at string first by way of a couple of examples.

Let's go in to CS50 IDE, create a new file, save it as Compare zero dot C,

and look at the little program that actually doesn't necessarily

do what we think it's going to do.

In particular, let me go ahead and include our typical,

include CS 50 dot H. And let me go ahead and include standard IO dot H as well.

Let me go ahead and use main void, so I'm not

going to worry about any command line arguments for now.

And then I'm going to go ahead and just prompt the user.

Hey user, give me a string called S for instance.

And then I'm going to have no newline.

I just want that all in one same line.

Now I'm going to go ahead and do string S,

gets gets string, open paren and close parens,

so as to get a string from the user.

And then, let me do this.

Let me also print T colon and ask the user, essentially, for a string

that I'll call T, since T comes after S quite simply.

And now let me just compare these strings as the filename suggests.

So I know how to compare, not with if s equals t,

because that's the assignment operator.

But we know that s equals equals t should compare the values on the left

and on the right.

So let's try this.

So if s equals equals t, then I'm going to go ahead and print out same.

Elts, they are presumably difference, so I'm

going to go ahead and print out different with a newline character

and then save it.

So a pretty simple program, so let me go down into my terminal window and run

make compare 0.

Now let me go ahead and run dot slash compare 0. s,

I'm going to go ahead and type in Zamyla.

And I'm going to go ahead now and type in Maria.

OK, and they're different.

I expected as much.

Now let's go ahead and run this again.

Again with Zamyla.

And let's just say Zamyla again, different.

What did I do wrong?

Let me try this again.

Maybe it's the capitalization.

So Zamyla in all lower case, different.

Well, maybe it's just Zamyla's name.

Let me try Rob or RLB?

How about RLB?

Those are different, as is Rob and Rob.

So what is going on?

Those strings pretty much look the same to me.

I'm typing the same incantation of strings,

so what is it that's going on here?

You know what, let me do a test with something else.

Let me go ahead and create a new file here.

I'm going to call this copyzero.c.

Maybe I'm just misunderstanding how comparison works.

But surely I should be able to copy a string and make an identical copy,

so let's do that now.

Let me go ahead and create a file called copyzero.c.

And let me do an include cs50.h.

Include standard io.h into main void, so just as before.

And now, let me go ahead and just prompt the user like before.

Give me a string s.

And I'll put that in a variable, s, calling get string as before.

And now, I remember from prior classes that I'm supposed to do,

if s equals equals null, maybe I need to do some error checking here.

And if that's the case, I'm going to arbitrarily return 1.

So recall that main can return values.

0 means all is well.

1 or any other non-zero value means something is wrong.

So maybe that's what I was doing wrong earlier, just not error checking.

So let's try that.

Now, let me declare a variable of type string called t and assign it to s.

So in other words, I want to copy s into t.

And I know that this happens from the right to the left.

So that's as I think it should be.

And then, if strleng of t is greater than 0--

you know what, I'm going to do one other thing.

Not just copy it.

I'm going to go ahead and do this.

Recall, that you can treat strings as arrays.

So I'm going to say the zeroth character, the first character of t--

you know what?

I want to uppercase it.

I want to really make sure that these two strings are indeed

different as I intend.

And let's go ahead now and do this.

Let me go ahead now and do printf of s.

And let me plug-in s's value in a new line.

Plug-in s.

And then printf t:%s for a placeholder again.

Comma t semi-colon.

So in other words, if the length of t is greater than zero,

let's capitalize it by changing that first character.

And then, just print out s and t.

And surely, by capitalizing only t, I should see only one capitalized word.

Now, I'm using both strleng and two upper.

So rather than let Clang have a chance to yell at me, I'm going to go in here

and preemptively add ctype.h.

Which recall is a library you might have seen

or certainly will soon see that has a number of functions in it.

Among them, two upper.

And then, I also need to include string.h, so that I can use strlen--

the function that gives me the length of the string.

So Clang would have yelled at me if I forgot that, but let me preemptively

solve that problem.

And now, do make copies zero.

All seems to be well.

Let's run dot slash copy 0.

All right.

Let's go ahead and type in-- how about just my own name in all lowercase.

Huh?

Now, why is this confusing?

So I wrote code that got a string from the user and stored it in s.

I then wrote code that declared a second variable, t.

And I set t equal to s, thereby making I would

think a copy-- as in past weeks of using the assignment operator.

Then down here, I made sure t was long enough.

That's just a quick sanity check.

And then on this line here, I'm just saying,

set the first character of t, t bracket 0, equal to the result of upper casing

the first character of t.

So the only code that's touching t is this one here.

And yet, somehow my name gets capitalized both in s and in t.

So what is it that's actually going on here?

It seems to be broken still.

In fact, let me go ahead and open another example, rather than type

this one out ourselves.

Let me go ahead and open up an example called no swap.

As the name suggests, it's a bit of a spoiler.

I wrote this program in advance to do the following.

First, I've included standard io.h, so I can use printf.

I have a prototype of my function called swap up here, because indeed,

the goal at hand I decided was I just want to write a simple function that

swaps two values.

Given a and b, make b a and a, b.

And then, return.

So I'm just going to arbitrarily test this out by declaring a variable x.

Setting it equal to 1.

A variable y setting it equal to 2.

And then, just as a sanity check, I'm going to print out x is such and such,

y is such and such.

And then, I'm going to claim swapping dot dot dot.

And then, the key line is apparently this one.

Call a function called swap, passing in x and y.

And if I implemented swap correctly, this should swap the two variables.