CARTER ZENKE: OK. Well, hello one and all, and welcome to CS50's third session, this one for week 3. My name is Carter Zenke, the course's preceptor. And the goal of these sections is to help you bridge the gap between the lecture you perhaps just watched and the problem set you'll tackle this week, or perhaps throughout the rest of some other period of time you'll be working on that problem set. 

Now, today we actually are going to talk about a few different topics. Among them are these here. So talking about how we can learn about algorithms, discuss what they do, and what they are, but also how we can compare algorithms. What makes one algorithm better than some other algorithm? We'll talk about that today. 

We'll also talk about this idea of a struct, or a structure, allowing us to make our very own data types. And we'll also, towards the end, talk about this idea of recursion, or trying to define something by defining it within itself. And that'll hopefully make a little more sense towards the end of section. But it is a powerful tool you can use to solve problems in computer science, and a worthwhile tool to have in your toolkit as a computer scientist. 

So let's begin by jumping into our very first topic, which is how we can compare algorithms. And in lecture, we had two algorithms we were going to think about, or two-- really, two types of algorithms, if you will. One of them is an algorithm used for searching, how we can find certain data from a data set. And then an other type of algorithm for sorting. How do we order data to make things perhaps more efficient to search later on? 

And we also talked a bit briefly about these notations we could use to compare algorithms. You might recall big O notation and big omega notation. So we'll talk more about those in section today. 

Now, let's go back as a bit of a review and think first through some searching algorithms. So here, I have a list of people. You can see on my screen. And currently, what do you notice? The people here are not quite sorted by name. 

We have Matthew first, then Samia, then Alyssa. So it isn't quite in alphabetical order. And if I could ask you all, what is the algorithm we might use to search, in this case, an array of people, if we know the list isn't sorted? What kind of algorithm could we use in this case? 

So I'm seeing some people say linear search. And linear search, to be clear, is when we start at maybe one side of this list and just look at the very first person, then the next person, then the next person, and so on. So let's pretend here we're trying to find this person, Alyssa, among these seven people. 

So if we are a person, I could very clearly spot Alyssa. Alyssa seems to be right here. Right? That's not too hard for me. I could do that in one step. 

But a computer has to look at only one piece of information at a time. So it looks a bit more like this. You can imagine these people being on a stage and us dimming the lights and allowing us to only see one person at a time. 

So for a computer, it might look first and see Matthew. And is Matthew Alyssa? No. So we're going to look at the next person. 

So we'll turn our spotlight to the next person. We'll see Samia. And we're not quite there yet. 

We'll take the next person now and we'll see still Alyssa. So now we have Alyssa on our third try, going through person by person, left to right. This is an example, then, of linear search. 

So let's imagine that we go back and turn on all the lights, and we have people, in this case, rearranged. So notice how their names are in alphabetical order. We have Alyssa, then Cecelia, then Douglas, then Lucas. 

What kind of algorithm could we use now to search for Alyssa? We saw this in lecture 2. So I'm seeing some people say this idea of binary search. We actually saw a binary search in our very first lecture when David took a phone book and opened it to the middle and asked if we went too far or not far enough, tore off half of it, and then kept going, and going, and going. So a similar idea applies to binary search in this case with people, too. 

So let's again dim the lights and let's only look at one person. And if we're using binary search, we know it's perhaps most efficient to look in the middle and ask ourselves, have we gone too far or not far enough in our list? So let's look in the middle. 

And here we get Lucas. Have we gone too far in our list or not far enough? Seems like we've gone a little too far. 

If Alyssa's name begins with A, Lucas is after Alyssa and the alphabet. So let's say, OK, let's not worry about Lucas or the people after Lucas. Let's focus this on the first half of people here and look in the middle of that. 

So it turns out the middle of our first half here is going to be Cecelia. And again, have we gone too far or not far enough? Seems we've gone a little bit too far still. 

So we'll do the same thing. We'll take that half of the problem and tear it away, and now I'll focus just on that very first half. And it turns out the very first person in that first half here is going to be Alyssa themselves. 

So we have two algorithms here, one called linear search and one called binary search. But it's also worth thinking about how we can compare them. So let me ask you here, how many steps did each algorithm take, if you can think back? 

Just in terms of a plain, old number of steps, how many did each take? Alyssa was the third person in our linear search, so it took probably three steps. And if you recall, just now, our binary search also took three steps. 

We start in the middle, divide it in half once, and divide it in half again for three steps. So it seems like linear search and binary search were the same here. They performed the same way. 

So I might then argue, well, it doesn't quite matter which one we use. I could use linear search or binary search. Each are equivalent. And what might you say, based on what you saw in lecture? 

If I were arguing with you that linear search is the exact same as binary search, what would you say? So I'm seeing some people say it depends on the problem size, which does make sense. Depends on the input that we get. So perhaps maybe we just got a little unlucky here, and both binary search and linear search took three steps. But it might not be the case in all inputs. 

And I like this idea of it depends on the size of our data set. So in this case, if we had a very, very big data set, we heard, or saw, in lecture that binary search might be a little bit better for that big data set. So let's think instead as a computer scientist would and think not just in terms of this one particular input, but in terms of input in general. In the general case, how well do each of these algorithms perform? 

So a better question to ask here is this one, which is, what's the greatest number of steps these algorithms will ever take? And let's focus actually just here on our seven people. Let's say, how long would linear search take? 

And if we took the greatest number of steps here, it seems like seven. Right? So seven steps. We have to go through all the different people to find out have we found the person we're looking for or not. So it seems like seven. 

What about binary search, though? What's the greatest number of steps it would ever take if we had seven people? I'm seeing n over 2, or dividing it in half. And you're almost there. 

It, in fact, is a logarithm. So a logarithm allows us to take something and divide it in half, divide it in half again, and divide it in half again. So it's more appropriate here to say that linear search takes about seven steps, and binary search for this particular input of seven people takes log base 2 of 7, which basically means how many times we can divide 7 by 2, which turns out to be something like-- let's see. Maybe three or so steps. 

So in the worst case, if you will, linear search takes seven steps. In the worst case, binary search takes far fewer, and therefore might be a better algorithm. So what questions do we have so far on this idea of comparing these algorithms using the worst possible case? Any questions? 

I'm seeing a question here about big O notation, which is, where does that come in? So that's actually going to be our next step here. So we often don't think about problems in terms of the exact number of elements we're searching. 

We often might think about, in an even more general case, just some number of people, like N. If we had 7, or 8, or 10, or 1,000. Who cares? We'll just call it N. Some number of people. 

And so now we could say, well, linear search, in the worst case, the greatest number of steps it will ever take is going to be N steps, one for each person, where we assume we have N people. Right? Now, binary search would do the same thing. It would say, let's actually not go through all N of them. Let's divide things in half, and in half, and in half again so the most steps we'd ever take would be log base 2 of N, where again, N is just the general number of people we have overall. It could be 10, 100, 1,000, and so on. 

But now computer scientists, because we often work with data sets that are so large and so big, on the order of millions or billions of pieces of data, we don't often care about things as robust as, OK, is it log base 2 of N or log base 3? We care about an even more general case. And that's where this idea of big O notation comes in. 

So we might say that linear search operates on the order of N steps. And in the same way, binary search operates on the order of log of N steps. So thinking here not even about the general case of, OK, is it 7 or 10 people, but just, what are we actually doing here? How does the problem scale as we add new people? 

So big O notation, then, is used often for this question of, what is the greatest number of steps an algorithm will ever take? If you're more technical, you could think of it as the upper bound of the algorithm. The algorithm will never run slower than this. 

So questions then on the transition between talking in terms of individual steps and talking now in these general, kind of hand-wavy cases? Question. Is there a faster way than binary search? Mm-- it's a good question. 

So if you get really into this, you can find other kinds of algorithms to search data, and there might be cases that could be a little faster than binary search. I don't know any off the top of my head, but certainly there are researchers who are working on that kind of thing, to figure out how do we write a faster algorithm than, for instance, something like binary search. OK, so let's keep going, and let's think about a different kind of scenario. 

So here, we're talking about the worst case, the greatest number of steps our algorithm will ever take. But there's some other case, too. So let's consider this one where we're still trying to find Alyssa and we're using linear search. 

So let's say it just so happens to be that Alyssa is the very first person we find. How many steps would that take? Well, just one. Right? 

And now let's think, too, about a binary search. Let's say we have this input of people. They're kind of shuffled a little bit. 

We have Aaron, Amulya, Alex, Alyssa, Cecelia, Lucas, and Ramya, and we're doing binary search. We're still looking for Alyssa. And if we were to do binary search on this data set, where would we first look? Well, the middle. So it took us only one step to find Alyssa here. 

So there's another question we could ask, then, which is this. Well, first, how many steps did the algorithm take, did each one take? Well, we talked about how linear search took one, and so did binary search. 

But in general, we could also ask this question. What's the fewest number of steps the algorithm could ever take? So with big O notation, we talked about what's the greatest number. But now we're asking, what's the fewest number the algorithm could ever take? 

And in this case, you could kind of simplify things and say, what happens if we get lucky? Well, it turns out that in linear search, the best, fewest number steps we could take is just one. Our person is at the very front of our list. 

And in binary search, it's similarly just one. Our person is at the middle of our list. So in this case, it's still the same. Linear search and binary search, the best case, they only take one step. 

Now, in general, as we just talked about, computer scientists don't tend to think about one particular input. They think about general inputs, what happens in just the overall best case. And we could say even if we had 10 people, 100 people, 1,000 people, the best case scenario, each of these algorithms would take one and only one steps. And that's where this idea of omega notation comes in. 

So omega notation says, what, given any kind of input, would be the fewest number of steps we would ever take? And now here, too, is this idea that omega notation doesn't even quite care if it takes two, or three, or 10 steps in the best case. If it takes some fixed number of steps, it only is going to be written as omega of 1. 

And there are other notations we'll consider, too, which I'll show you in just a bit. But consider for now that even if it took a fixed number of steps, 10, 100, 1, all of those would be written as basically omega of 1, indicating it takes some certain number of fixed steps in the best possible case. So questions, then, on these algorithms? 

I see a question here. "Are linear search and binary search the only algorithms that we can search data with?" Certainly not. There are many researchers who are working on other algorithms we can use to search data, and you might find some that are suited for a particular use case. 

And from lecture, you might have recalled David saying that there's often a trade-off, let's say, between space and time. You could perhaps have an algorithm that uses a lot of space, but could perhaps be a little bit faster in searching something because it uses so much space. Good questions. 

A question about can we define an algorithm. So it's a good question here. What even is an algorithm to begin with? 

We often say an algorithm is simply a set of steps to accomplish some task, and those steps have to be very clearly defined. Like in linear search, we look at the first person, then the next person, then the next person until we get to the very end. Good questions here. 

Any others so far? OK. So here's a question for you all, then. Suppose that you are creating a new algorithm and you want to assess its runtime. That is, how quickly does it run. 

You find out that the fewest steps this algorithm will ever take is two, and only two. And now question is, what is the big omega notation for this algorithm? Keeping in mind what we've just discussed, suppose, in the best case, this algorithm takes two steps. What would be the omega notation for this algorithm? 

I'm seeing a few answers here, which is actually what I had hoped for. So I'm seeing some saying it would be omega of 1 and some saying it would be omega of 2. So if we go back here, maybe we wouldn't have omega (1). But we instead, have omega (2). And I think it's a good intuition. 

If you know that the best case will take you two steps, it kind of just makes sense to write omega of 2. But it turns out that computer scientists, by convention, like to think of things as being on the order of some number of steps. And whether it takes two, three, four, if it takes some fixed number of steps, we'll say it operates in omega of 1 to symbolize that it just takes some finite number of steps in the best case. So not omega of 2, but instead, omega of 1 by convention in this case. 

So some other notations you might see as you go off and learn more about algorithms are these here. So on the furthest left-hand side, you'll see the big O notation. The worst case, if you will. So you'll have algorithms that, in the worst case, take some fixed number of steps. They'll be in O(1). 

There are other algorithms, like we just saw binary search, that operate in big O of log(N). They keep dividing problems in half, and half, and half again. There are still others that operate in O(N). That means they have to take a look at every individual element they might be searching for. 

And then there are some that operate in big O of N squared, where for every element, they have to take that number of element steps before they can move on to the next one, and the next one, and the next one. And in general here, we don't really care if it's big O of N squared plus another 10 steps at the end. In general, we care about the biggest term. N squared, N, log(N), or 1. 

And same thing for omega notation here. But now thinking about not the worst case, but the best case, or the fewest number of steps the algorithm could ever take. And a question here is, well, let's say the algorithm takes maybe 100 steps in the worst case. What would that be? 

Well, it kind of depends now. If the algorithm takes 100 steps in the worst case, we have to ask ourself not so how many steps the algorithm took in that case, but instead, how the steps scale. So if the algorithm will always take 100 steps, and only 100 steps, in the worst case, that would actually be O(1), because it's some fixed number of steps. 

If, though, I were to add one more element and you would then need to do 101 steps, or if I added two elements and you had to do 102 steps, that would be an example of an algorithm in O(N). Because for every element I add, I have to do one more step. Questions, too, on these notations? 

A question about encountering algorithms in other languages, like Python, for instance, as you'll see later on in CS50. So certainly there's this idea that we can take most any algorithm and translate it into, really, any other language. So for the first few weeks of CS50, you'll be using C. Later on, you'll use Python. You can take most any of these algorithms and put them into any language you'd like. 

Good questions here. OK, so let's try actually putting some of this into practice. And so the very first problem this week is one called sort, in which you're given some various sorting algorithms. 

So we've talked here about searching algorithms, but now let's transition to thinking about sorting algorithms. So in lecture, we saw three different sorting algorithms, and here they are, along with their big O and big omega notations. So notice here that we have merge sort, which we saw was among the fastest of our sorts. 

You can see that merge sort has a big O notation of O(Nlog(N)). And the same thing for its omega notation. Big omega of N times log(N). Now, this is faster than selection sort and bubble sort. 

So we'll see selection sort here. It was big O of N squared. And bubble sort was also big O of N squared. Now, the omega notation for selection sort and bubble sort is also omega of N squared. But for bubble sort, omega of N. 

So actually, I said earlier that merge sort is faster than these two. But can you think of a scenario where you might actually want to use bubble sort as opposed to merge sort? What scenario we might want to use bubble sort instead of merge sort. There is a case where bubble sort is faster. 

Seems like it's faster if we are in one of our cases that seems one of our best cases. If we're talking about sorting algorithms, well, if we know our data is close to being sorted, and we just want to check is it sorted or is it not, bubble sort could be a good way to do that faster, in this case, than merge sort. And we know this looking at the notation here. We see omega of N for bubble sort and omega of N times log N. So that is, for every step we do, we have to add in another log N steps in merge sort. But for bubble sort, we don't have to actually do that in this case. 

So I find it helpful to see these things in a bit of a chart. And the sorting problem asks you to figure out the identities of three mystery sorts. So here, you're given sort1, sort2, and sort3, and your job is to time them and see which algorithm each sort might be using. 

And one approach here is to think about, like big O and big omega notation, the best and the worst cases. Give them those inputs and see how long it takes them to run, and then compare them. Compare those run times and see which one you think might best characterize the algorithm you are just testing. 

So here, our goal will be to fill in a chart that looks a bit this, where we have a reversed 50,000 numbers. This is the worst possible case. Our numbers are in the exact wrong order. We'll go through and time each of our algorithms and see, perhaps, which one runs the fastest, which ones run the slowest. 

And we'll do the same thing, but now given a sorted list. Our numbers are in the best possible condition. They're already sorted for us. And we'll ask that same question. How long, in general, did each one seem to take? 

And so by timing our sorts, we'll be able to figure out do they seem to run more equivalently to big O of N squared, or O(Nlog(N)), or something in between? So in this case, let's actually go back to Visual Studio Code. And I will restart mine here. 

Once you connect to yours, you'll be able to actually download some of the distribution code for the sort problem. And you'll be given, in this case, three different sorting programs along with the inputs I just mentioned. So I'll wait for mine to start here. 

But our goal will be to look at each of those three sorting algorithms, time them, and make note of, let's say, which one might be most equivalent to the three algorithms we just discussed so far. So it seems my code space is ready to go here. Let me hide a few things to get out of your way. 

And let me show you where I have my files. So if you download them, you should be able to see them in your very own folder called Sort. And I'll use this command called cd to change directory into Sort. I'll hit Enter. And now here, I see my prompt changes into sort. 

I can type ls again, and now I'll see some various text files, along with my three sorting programs, sort1, sort2, and sort3. So now let me show you what's inside answers.txt. I'll say code answers.txt. And now I'll see what I'm supposed to do. 

I'm supposed to identify which algorithm each of these sorts uses. So sort1, for instance, could use-- well, it could use merge sort. Or it could use, let's say, bubble sort. 

It could be any of these things. My goal is to type it in and figure out which one this-- which algorithm this sort is using. And then down below, type in why I think that's the case. 

So let's try timing these, given the best and worst case inputs, and seeing how well each one does. So I'll go to my terminal here. And if you read through the problem specification, it'll tell you that you can time these sorts using this. 

You can say time, and then followed by the command to execute the sort. So in this case, I want to run sort1. I can type ./sort1 and give it either the best or the worst case scenario. Maybe I'll give it the worst case to begin with. 

I'll say, let's give sort1 a reversed list of 50,000 numbers, and just time it and see how well it does. So I'll hit Enter and I'll see it's thinking, maybe sorting this list for me. And now down below, I can see how long it took to take all 50,000 of these numbers and put them in sorted order. 

So it seems sort1 took about 4.64 seconds. And you're given three different times here. Real, user, and system time. In general, you'll care about just the real time, how long did it take based on a stopwatch, in this case. 

So I can go back to my answers.txt and I could say, well, I'll just make note. sort1 seemed to take-- takes 4.64 seconds in worst case. Or maybe let's be more particular. To sort reversed list like this. 

Now, I might also care about how this algorithm performs in the best case. So I'll go back to my terminal and I'll then say, let's time it again, but use ./sort1, and now let's choose the sorted list, sorted50000..txt. And hit Enter and see how well it does. 

Now, that was a lot faster. That only took 0.3 seconds, about. So I'll go back to my answers page and I'll write that down. I'll say it takes 0.33 seconds to sort a sorted list. All-righty. And I could keep going here. 

And if you're watching this not-live, I encourage you to pause the video and go through and time the other sorts. If you are here live, we'll go through and time these ourselves and put them all together in our answer.txt. So let's keep going. 

I'll go ahead and say, I will run ./sort2 now. But I want to time it. time ./sort2. Let me give it the sorted 50,000-- actually, the reversed 50,000 numbers. See how long it takes. 

That was pretty quick. So I'll say it takes 0.27 seconds to sort reversed list. Let's try again, doing not reversed, but now sorted. That was still pretty quick. So it takes 0.45 seconds to sort a sorted list. 

And now I'll try sort3 now. Oops. Let me move this down to here. Let's try sort3. I'll say, give sort3 the reversed 50,000. See how long that takes. 

A little slower. I'll say it takes 2.25 seconds to sort reversed list. And now I'll try sort3 with my sorted list. Still took a little while. Let's say it takes 1.99 seconds to sort a sorted list. 

And now I'll zoom out here so we can see all of our numbers. And now keep in mind that we don't care so much about the milliseconds. Right? It doesn't quite matter if it took 10 milliseconds here, or 10 milliseconds there. We care more about how each algorithm performed in the best and the worst case. 

And we'll keep in mind what we know about our algorithms over here. So it seems merge sort, if I look at this list, is generally pretty fast in both cases. Right? Selection sort seems to be pretty slow in both cases, both my reversed list and my sorted list. Bubble sort, though, seems to be slow in the worst case, but actually pretty quick in the best case. 

So let's take a look, then, at our numbers. Here, if we look at sort2, it seems like this one was pretty quick in both cases. It took less than a second to sort a sorted list and to sort a reversed list. So knowing what we 

know about merge sort and how it performs in both best and worst cases, maybe this one is probably merge sort. So I'll say merge sort here. Now let's consider the other two. 

I have this one, sort1, that took over-- it was almost 5 seconds to sort of reversed list. But then it took less than a second to sort a sorted list. Now, knowing what we know about our algorithms, which one does this seem to be? 

It seems likely to be bubble sort, because we saw, if I go back to our notations here, that bubble sort was big O of N squared, but big omega of N. And N is certainly faster than N squared when it comes to these notations. And now the final one, we could say, well, by process of elimination, it's probably going to be selection sort. 

But we could also say here, well, it took about 2 seconds to sort the reverse list and a similar amount of time to sort the sorted list. So maybe it's going to be, in this case, selection sort. Because we know, based on our chart here, that selection sort takes out the same amount of time in the best and the worst cases. 

So I'll fix my typo here. And now we have our mystery solved of which algorithms these sorts are using. Now, questions, then, on our process or our selection of these algorithms? 

A good question here just for people who are learning computer science. Is it good to practice making these algorithms? I would say it's certainly good practice to actually write the code for these algorithms just so you can get a hand-- get an experience of what it is each one is actually doing. So it actually is helpful, I think, to write things like linear search, like binary search, things bubble sort, merge sort, selection sort. Because in doing so, you get an appreciation for exactly the process each one is following. 

Let's see. A question here. Why is the reversed list-- why is sorting the reversed list faster than sorting the sorted list? So if I look here for merge sort, it seems this first case to the reversed list was faster than how long it took to sort the sorted list. 

And that doesn't make any sense to me. If I know that this is the worst case, and this is supposed to be the best case, well, why is the best case slower than the worst case? Turns out, when we're actually timing things in our computer, there are other processes going on that could interfere with these things and make them take a little bit slower or a little bit faster, depending on the time that I run them. 

So this is really just a single data point here. And this is why computer scientists don't time things in terms of milliseconds. They time things in terms of number of steps their algorithm might actually take in the best and the worst cases. So we don't have to consider here whether our computer's running some of their software. Just a single sort in this case. 

OK. So that will be our recap, then, on our searching and sorting algorithms. Hopefully you've gotten a taste of big O notation and big omega notation. Let's start now adding another tool to our toolkit, this one called structs. 

So at the end of lecture, or towards the middle, I believe, we learned about this idea of a structure. And a structure is great. We want to create our very own data type to use in our program. It's not quite a full data type, but it is a way to encapsulate information so we can refer to it with only one name. 

So let's take, for instance, this picture here. We have two candidates for US government. And I want to ask you what might you use to describe these candidates. If you were going to store information about them, what information would you store? 

Could be these two. Could be any candidate in any country for a political office. I'm seeing maybe their age, their party, their name. Maybe the contact info direct to Joe Biden's desk. Maybe the number of votes they got is a good one. So there's lots of things we could represent about this candidate. 

And up until now, we've been able to create individual variables that could store this information. But a struct allows us to combine these pieces into a single one and refer to it all, in general, as some candidate. So let's take an example here. Let's say in C we saw this syntax, typedef struct curly brace string name; int votes; end curly brace candidate;. This looks a little confusing at first. We can break it down to figure out what we're doing here. 

So let's say first here we have some syntax to create a new quote, unquote, "type." It's not a full type like an int is, but it does allow us to say we're going to consider name and votes part of some individual piece of data in our program. And here is that full text here. 

One other piece of syntax is this, the typedef. This is saying that we're going to take this combination of a string called "name" and an integer called "votes" and call it something else, in this case, a candidate, so we could reuse this idea of candidate throughout our file. And then inside here, we have what we call the members of the structure. That is, what kind of data are we going to encapsulate or consider to be part of what it means to be a candidate? 

So here, we chose just the name and the number of votes for a candidate. But you could very well have in this case their age, their party, and so on. So all we're doing here is saying that these two pieces of data, one a string we'll call "name" and one an integer. we'll call "votes," are now part of this more general data type called a "candidate." And we can reuse that type throughout our program. 

So let's consider here actually making our very own candidate. So we'll go through here and say, let's create a candidate called president. Let's create a candidate called president. And we'll, on the right-hand side, have this picture of a candidate here. So see on the right-hand side. 

Now, if we want to give this candidate a name, we could do so like this. We could say president.name equals whatever name we have for them. So in this case, Samia. And now, if we want to give them some number of votes, we could say president.votes now gets the value 10. 

So notice here, on the line below our typedef struct, we're saying candidate space president. So this looks a little similar to our prior syntax, where we're able to say maybe int x or string name. But now we're using this name candidate as kind of a type name, if you will, for this new variable we've created called president. 

And if I want to assign some value to the different members of president, I could simply access them using the name. the member's name. So president.name, president.votes, and so on. And even further here, I could try to create my very own array of candidates. 

I could say in this case, candidate candidates bracket 4. Now, to be clear here, what I've done is I've created an array called candidates, plural, that stores four elements. But what elements will it store? Well, in this case, those that are candidates. So you can see the type still comes first, but then we have the name, followed by brackets and the candidates here. 

So questions, then, on the syntax of these arrays or these structs here? Is it possible to have a struct made out of other structs? I don't quite know. I don't see why it wouldn't be the case that you couldn't do that. 

Yeah. I would try it out and see. I don't have as much experience to know about that, but you should definitely try it out and see. Let's see. Other questions here, too. 

Question. "Can we change the data in there if needed during runtime?" So that's a good question. If I go back to this candidate that we called president here, the question is, could I change the data inside of it later? 

So to be clear, I could assign different values to this candidate's members like candidate.name or candidate.votes. I could change those throughout my program. But I really shouldn't be able to add new members to my struct as my program is running. 

So up top here, you'll see we defined a candidate as having a string called name and an integer called votes. I have to do that at the very start of my program. I can't change that, really, when my program is running. Good question. 

All right. And a question here. Could we just use candidate.name instead of president.name, the structure name instead of the variable name we just created? So it's worth mentioning here that the struct candidate is more so not a variable we've created, but a template for one. 

So every new candidate we create has to have its own name. But it will all be, let's see, inherited from this idea of a candidate. So candidate president, candidate vice president We could maybe have a candidate called candidate, but we'd still have to instantiate that by saying candidate space candidate, the type name, then the variable name. And probably in that case, best not to confuse the variable name with the structure name. So I would probably avoid that altogether. 

OK. So let's get some practice with this. And we'll have a task here, which is to find a candidate who's gotten the most votes. So what we'll do is first create an array of candidates, and we'll search the array, perhaps using linear search, to find the votes most awarded to any single candidate. And then once we know that, we'll print out the candidate's name. 

And our goal here is to get some practice using the syntax of structs. So I'll go back to my code space, and now let me pull up a file I've already created. This one, called, let's see, search. c. So I'll code search.c to pull it up. 

And notice how I already have some code in here. So at the top, I've included my CS50 library and my standard I/O library. I've defined for myself a struct that has a name and a votes member, and I've called it candidate. Now, down below in main, I've created myself an array of candidates. This has a total of three possible members. 

I've defined this constant here, a number that can't change, and defined it as 3. So now I have three candidates that can go inside of this array. Down below, I've defined their name and the number of votes. But now my goal is to find who has the highest number of votes. 

Or even before I do that, before I find who has the highest number of votes, I should probably find what the highest number of votes actually even is. So the question really boils down to, how could we use linear search to find this highest number of votes? And now let me ask you, what kind of structure might be good to search this array? If I wanted to loop through every candidate, what kind of structure might be good? 

I'm seeing a for loop, so I could do for. And I know I want to go from, let's say, the very first candidate, all the way to the final candidate. So I'll start my index, i, at 0. And I'll say I'll keep going while i is less than, well, however many candidates I have, which turns out to be num_candidates, which I defined up above right here. 

So now I want to increase i by 1 each time that I go. And now, inside this loop, what should I do? My goal is to find the highest number of votes, so maybe I should first make a variable that defines that number of votes for me. 

I could say, create an integer. Let's call it highest votes. And we'll set it equal-- well, at the beginning, we don't quite know what it will be. Maybe it could be 0 to begin with. 

So now we have this variable, highest_votes, that's equal to 0. But now I need to ask, under what scenario should I update highest_votes as I loop through my candidates? When should I try to update the highest_votes? 

Let's say I look at Carter first. Should I update highest_votes? Seems like I should, because Carter has 10 votes, and our previous highest was 0. So while I'm looping, I could ask this question. 

I could say if, let's say, candidates bracket i, that is, the candidate in my list at the index i, if their number of votes, candidates bracket i .votes, is greater than what we've currently set as the highest number of votes, well, I want to update it. So I'll say highest_votes then becomes candidates bracket i .votes. 

So now what I've done is said that if I ever find a candidate who has a number of votes greater than my current highest number of votes, I want to update what I'm considering to be the highest number of votes. So let's walk through this once step by step. 

So first highest_votes is 0. I'll look first at Carter. 10 is greater than 0, so our highest number of votes will now be 10. I'll look at the next candidate this one is Yulia. And I'll say, well, is 12 greater than 10? It is. So my new highest number of votes is now 12. 

I'll then look at Inno, and I'll ask, well, is 7 greater than 12? It's not in this case. So my highest number of votes is still going to be 12. And by the time I'm done, highest votes should actually equal the person with the highest-- or should equal the number of votes that is the highest. 

And to confirm this, I could say printf("%i/n") for that integer format code, and I'll print out now highest_votes. And let's try to make this program and compile it and see what happens. So I'll go back to my terminal and I'll say make, in this case, search. Seems like no errors. I'll run ./search, and I'll get back 12 for the candidate who has that highest number of votes. 

OK, so that seems to accomplish my very first task, finding the highest number of votes. What can I do now to print the name of the candidate with that highest number of votes? Any ideas here? 

I know the highest number. I just want to see who has that number of votes. So maybe what I should do is do another loop through my candidates array, this time, asking, are you the person who has the highest? Are you the person who has the highest? And if you are, I'll print out your name as I go. So let's try this. I'll say for (int i = 0;). i is less than my number of candidates, i++. 

I'm going to loop through every candidate here, and I'll ask this question now. If candidates bracket i .votes, the candidate at this index, their number of votes, if that is equal to highest_votes, well, then I want to print out their name. So I'll say printf, and I'll do %s for that string format code, and now I'll use candidates bracket i .name to get the name of this candidate. 

So now what I've done is I've looped through my entire array asking this question, does this candidate have the highest number of votes? And if they do, let me print out their name. So now let me go back and make my program again. 

I'll type make-- let's say make search, and I'll run ./search, and I'll see the highest number of votes is 12. And the candidate with that number of votes is now Yulia. So our goal here was to see how we could use this structure syntax to simplify things for us. Now I have this structure called candidate that I can use in my program. And I can talk in the same breath about a candidate's name and the number of votes without keeping those two things separate. They're part of that same structure I defined up top, which can really help me out as I run my program here. 

So questions, then, on structs? A question about repeating code. So, in general, it is true that you generally don't want to repeat code in your programs. In this case, though, I would argue we can't avoid repeating code here. 

So if I'm first trying to find the highest number of votes and print out that person's name, you might think I could do it all in the same loop. But let's try this. So I'll look first at my very first candidate, whose name is Carter, and I'll see that Carter's votes for 10, well, that's higher than I've previously seen. It's greater than 0. Right? 

But should I print Carter's name yet as having the highest number of votes? I probably shouldn't. I need to keep looking through my list. I need to confirm that there's no person with a higher number of votes than Carter. So that's why I need now two loops. 

My first loop goes through and confirms what is the highest number of votes. My second loop goes through and then confirms what will be their candidate's name, in that case. Other questions, too? 

Let's see. That seems to be covering most of the questions I'm seeing here. OK. So let's keep going, then. 

And I think we have an idea of what structs are. But I want to give you one more tool to use as you go off for this week, and that is a tool called recursion. So often, recursion tends to be a very elegant solution to some problems. And for that reason, we have to try to find a way to use recursion to solve problems. 

The caveat here is that it's not always the best way to do things, but it can be elegant in certain cases. And so we'll talk about the kinds of problems that actually have good potential to be solved with recursion. Now, one problem like this, this idea of a factorial. 

So if you aren't familiar, a factorial is simply a number where you take that number and multiply it by the number that's 1 less than it, then the number that's 1 less than that, the number that's 1 less than that, and so on. So let's take a look at an example here. 

If I want to find 1 factorial, well, that is just 1. And the factorial is this exclamation point here. 1 factorial equals 1. But now if I want to find 2 factorial, 2 factorial is simply 2 times 1, so 2 times the number less than it. 1, in this case. 

Well, 3 factorial, that is 3 times 2 times 1. So again, start with that number, 3, multiply it by the number 1 less than it, then again, then again. So 3 times 2 times 1. 

And now 4 factorial. What do you think that will be? Well, 4 times 3 times 2 times 1. So in this case, 1 factorial, 1; 2 factorial, 2; 3 factorial, 6; and 4 factorial, about 24 in the end. 

So what makes this problem good for a recursive solution? Well, you might notice a bit of a pattern here. And it gets a little more obvious if I do this with these numbers, if I slide them over. 

So what do you notice in particular about now 2 factorial? Seems like to me that the solution for 1 factorial is part of the solution for 2 factorial. That is, if 1 factorial is 1, we could compute 2 factorial by taking 2 times 1 factorial. 

And similarly, for 3 factorial, looks like to me we could solve that problem by saying, well, 3 factorial is just 3 times 2 factorial. And same thing with 4. We could say, well, 4 factorial is just 4 times 3 factorial, and so on and so forth. So we're able to find a solution to this problem in a smaller version of that problem. Until, of course, we get down to 1 factorial, and we just say, well, that is just 1 in the end. 

So to make things a little more concrete, in computer science, we might give a few names to these things. So first, we'll say 4 factorial is equal to what? Well, 4 times 3 factorial. 

But this here is what we're going to call our recursive call. We're going to "kick the can," as David said, and say, well, we know the solution to 4 factorial is just 4 times 3 factorial. Now, the question becomes, what is 3 factorial? Let's find out. 

Let's take 3 factorial and let's find it. Well, 3 factorial is just 3 times 2 factorial. OK, well, what's 2 factorial? Well, it's 2 times 1 factorial. 

Well, what is 1 factorial? Eventually, there has to be some base case, some definite solution to this problem. In this case, we say 1 factorial has to be 1. And when we get to this base case, we can use that to solve all prior problems. In this case, I could say-- I could substitute 1 factorial for 1, going back up the call stack. 

So now we have 2 factorial is 2 times 1, 3 factorial is 3 times 2 times 1, and 4 factorial is just 4 times 3 times 2 times 1. And to be clear here, the vocabulary is that we're calling these functions again, and again, and again. And when we get to that base case, we go back up what we call this call stack. We're calling it a call stack because we're calling functions, and they kind of stack on top of each other one at a time before we resolve everything all at once at the end. 

So questions here on this recursive solution to factorials before we write our own implementation in C? A question. "Is recursion faster than using regular loops?" That is a great question. 

So recursion is often seen as this elegant way to solve problems, and it certainly is, because it is kind of magical when you see how things click together and how they work like this. At the same time, recursion isn't always necessarily faster. So just because a problem uses recursion doesn't mean it's going to be always faster than some other solution. It just means we're trying to solve the problem by first solving a smaller version of that problem. And eventually, we'll get to a base case that we know the answer to. Good question here. 

OK, so let's now take the same idea. And translate it into code. So I'll go back to my code space here, and I will get rid of search.c, and I will instead find factorial.c. 

So in the same way, we already have some code here for us. I have included the CS50 library and standard I/O. Now, I've defined up here a function called factorial. This is the prototype for that function. 

So notice here it takes an integer called n as an input and it gives us back some integer in the end. And that makes sense. If I were to say, give me 4 factorial, where I would give it some integer, in this case 4, I would get back some integer in the end. In this case, 24. Right? 

So now in the main function, I have a few components here. The first is to get the input from the user. And it turns out that in factorial land, you can't take a factorial of a negative number, or at least we don't really want to do that here. It gets kind of complicated. So we're only going to focus on positive numbers. We'll prompt the user again and again for a positive number. 

And then finally, we'll print the factorial of that number. In this case, we're going to print out our %i format code, a placeholder, if you will, but we'll substitute in the result of calling the factorial function given our n input from the user. But now, down below, seems like factorial isn't quite implemented here. So if you think you have a solution to a problem that involves recursion, it's often a good first step to ask yourself, what is the base case, what is the scenario I know the answer to, and try to code that one first. 

So my question to you, then, is, what is the answer that we know the answer to in this case? We know the answer to if n is 1. So I could say if (n == 1), like this, what do I return? 

Well, I just return 1. It's a very simple solution. Right? If n is 1, return 1. 

And now down below-- well, I might actually first call this my base case here. Now, down below, what is my recursive call? If I go back to my template here, we certainly have our base case now. But what is our recursive call? What should that look like? 

Well, I know I could return, let's say, n. But n times what? n times-- well, I could just call factorial again. I could say, return n times factorial (n - 1), like this. 

So now what I've done is I've added that recursive call. If I call factorial, given, let's say, 4, I won't activate my base case. 4 is not 1. But I will go down here and say, I'm going to calculate 4 times the factorial of 3. And I'll go back to running factorial again, and again, and again, until I find that base case and return, and return, and return, and return, until I find my ultimate answer here. 

So let me prove to you this works. So I'll go back to my terminal. I'll say make factorial, and then I'll say ./factorial. And I'll give it, in this case, 4, and I get 24. I'll do it again. 

I'll put in 3 and I'll get 6. I'll do it again. I'll put in 2, and in this case, I'll get 2. So now let's actually try to prove to you that this works. 

I will use debug50, which is what we saw in an earlier lecture. And in debug50, I can actually step through my program step, by step, by step to show you what's happening underneath the hood as this program runs. So I will say let's pause on line 17 right here, and let's walk through each step one at a time to see what this recursive function is actually doing. 

So I will go back to my terminal and I'll say, debug50 ./factorial, like this. And we'll wait for things to load here. It might take a minute or two. 

But as things come into picture here, notice a few different areas. So let me clean this up. Notice in particular my Variables portion and my Call Stack. 

So recall what a variable is. Simply some name that has some value. And our call stack was some new vocabulary we just learned. That is, the idea of calling some function, then calling another function, and calling another one, until we have this stack of function calls we need to resolve at the end. 

So here, I'll tell my program-- I'm going to give it an input of 3 in this case. 3, like this. So now I'm paused at this step in my program. Notice here on the Variables tab, that n is equal to 3, like we thought it would be. 

Now, instead of stepping over this, that is, completing this function and just printing the result, let me step into this and try to figure out what's going on in this factorial function itself. So I will choose, in this case, step into. And notice how here, I called factorial for the first time. This is the first time I've called factorial. n is equal to 3 up top. 

Now, is n equal to 1? It's not. So what our program will do is move on. It will go down here and instead return n times factorial(n - 1). 

So let's step inside again and see what this next call to factorial is doing. I'll step into, and notice a few things change. Well, n is now 2, but I've added one more step to my call stack. 

Before I can resolve this one, I need to resolve this one. Right? So I'll keep going. 

n is now 2. Is that equal to 1? It's not. We'll step over, and now I'll say, n times factorial(n - 1). I'm going to compute that next. 

So 2 times factorial of 1. I'll step into this again. And notice my call stack again. 

So before I can resolve this first factorial call, I have to resolve those that are on top of it, the one for 2, and now the one for 1. So let's resolve this one here. N equals 1. Well, seems like this is not going to be true, so I'll step over and I'll now return 1. 

Notice what happens here. This call that we're currently on, 2 factorial, when we return 1, it'll go away, and it will just give back to this call here that value 1. So I will now step over. Step over again. And now I'll see I've completed that call to factorial. 

I was able to find that this call is now 2 times 1, returning 2 times 1. This call can now return-- it knows that 2 factorial is 2 times 1. I'll return. 

Now, this one knows, well, what is 3 factorial but 3 times 2 times 1? I'll return that, and now I'm back up at main and completing my program as a whole. So that is our step-by-step walkthrough of the recursive nature of factorial. 

Now, it's OK if it didn't come all at once. And, in fact, I encourage you to do the same thing on your own computer, or even get out some pencil and paper and just write stuff down and visualize as you go through, and you'll hopefully see the recursive nature of it, trying to solve a smaller problem and a smaller problem. Once you get that base case, all the other problems become clearer as you go. 

So questions, then, on this? A question on, "In the call stack, in what order do the calls execute?" So you'll hear this more later in the course, but there's this idea of a data structure called a stack. 

And the key idea of a stack is that the last thing you put in is the first thing you do, or that you see. So in a call stack, the last function I added was factorial. That is, then, the first function I must resolve before I can do anything else. 

So you could imagine here I call factorial once. If I call factorial for 3, I then end up calling factorial two more times overall. But what I have to do first is resolve that very base case. Then I can resolve the 2 factorial, then I can resolve the 3 factorial, until finally, I go back up here and resolve main as a whole. I hope that helped a little bit. 

A question about the return 1 here. So if I scroll down here, we said return 1 for this factorial call. And the question was, why didn't it kill the entire program? Why didn't it end the entire program? 

Well, notice how return here ends my given function call. So remember how we called factorial a total of three times? That final time we called factorial, we triggered our base case and simply returned 1 without making any new recursive calls. And as soon as we did that, we knew, then, how to resolve the other recursive calls that we tried to finish beforehand. 

And a clarifying question here. "Is main always resolved last?" Yes, it is, because it is our very first function we call when we run our program. 

Other questions here, too? All right. So if there are no more questions I'm seeing here, why don't we call that a wrap for this week's section? 

Certainly, you've gotten a lot of new tools in your tool kit to solve problems, which you certainly solved this week's problem set. I wish you all the best as you go through and finish this week, and I'll hopefully see you next time. Thank you all for coming in.