CS50 2019--考試複習 (CS50 2019 - Test Review)

字幕列表影片播放

all right.
Hi, everyone.
Welcome to see a 50 test review goal of this afternoon is going to be an opportunity to talk about all of the topics that we've really covered in CS 50 over the course of the 1st 8 weeks or so of the term and to get an opportunity to ask questions in preparation for the test.
So a couple of logistical notes before we get on to the actual content of what's going to be today's test review.
Note that the test is going to be released later this evening at 7:30 p.m. It'll be released on the course website US.
If you go to the core Spencer, you'll see a link to the test there.
You'll have until Friday, this Friday at 11 59 PM to turn in the test.
There's no timer on the test.
It's entirely self paced.
You're welcome to take as much or as little time within that timeframe to work in the test as you like a CZ long as you meet that final deadline of turning in the test by Friday, the eighth at 11 59 PM and you'll do so by turning in the test by a grade scope in much the same way that you've been turning in quizzes where you upload a pdf of your responses, you'll choose, which pays it pages.
Each of your answers to each of the questions corresponds to on that will be how you'll turn in that test.
A couple of rules about the honesty policy for the test.
The test is entirely open book, which means you're allowed to reference any of the notes.
You can go back and look at the lecture video of you can look at the lecture notes, the slides, any of your own notes that you've taken.
You're welcome to use any and all online resource is that you'd like to.
You're welcome to Google things.
Look things up for the purposes of the test.
The only thing you cannot do is turn to other human.
Resource is you cannot turn to other students in the class or other people or you're teaching fellows for questions.
If you need to ask anything pertaining to the test, you should email the course heads on.
If you email the course, heads will be able to respond to you, but that is just for, like, clarifying questions.
You're expected, Thio for any of the content part of the test you expected to work on that on your own without turning to other human resource is for help.
But you're more than welcome.
Thio.
Look things up online or reference any of the river asses on the course website, but without the lecture resources or otherwise questions about test logistics, anything about how the test is going to work.
Yeah, When can you expect results back after turning in the test usually will try to get the tests graded within a couple of days a week at most other questions about test logistics.
Yes, If you look something up on Google, should you reference that in your test response?
Yes.
At the end of every question in the test will be a debriefing section, which will ask you which resource is you used in order to answer the question.
So any resource is that you took advantage of whether the website you looked up online or a lecture slide just referenced that in your response to that test question, just that we have that information as well.
Other logistical questions about the test.
Oh Yes.
Can you resend it before the deadline?
Yes.
You're welcome to resubmit as many times as you like prior to the Friday midnight deadline.
Yeah.
Process.
Yeah.
Can you log in and out of the test across dates?
Absolutely.
There's no limit on when During that range you can access to test.
You can access it immediately.
Monday at 7 30 In fact, I'd encourage you to as soon as possible.
Open up the testing.
At least read through the questions on dhe.
Then you can continue to access it up until the deadline.
Other logistical things?
Yes, back there.
There are no tutorials or sections or office hours during the test question up there.
About how long should you expect the test to take you?
In general, we say you will probably be spending half a now, er a little more than half an hour per question.
And you can look back at past years testing quizzes, and usually they're in the range of like, 8 to 12 questions or so somewhere in that range.
All right.
So, a couple of ways, in terms of preparation for the test in terms of what to do first and foremost I would recommend reviewing any of the lecture resource is so that includes the lecture video, but also lecture notes, any of the source code examples the David demonstrated in lecture.
All of that code is made available on the course website so you can download that code or open it up in the sandbox or inside of CS 50.
Idea to read that code understanding.
Experiment with it, and you find the slides from all the videos as well.
From the lectures.
All of the past year's tests and quizzes and the solutions to those tests and quizzes are also made available online.
So that's another thing definitely worth looking at, because the style of the questions that are asked are generally similar in terms of the types of questions that we're asking the types of things were asking you to be thinking about.
So past years, test quizzes and their solutions are available online Tomb, and then I'd recommend taking a look at the problem.
Since the problems have specifications are online.
In addition to sample staff solutions that you can take a look at and those they're often helpful resources as well, just to give you a sense for the types of problems that you were asked to solve during CIA 50 so far and therefore the types of things well, you might be thinking about over the course of the test on then.
Of course, a great thing to do for the test preparation is what you're all doing here.
Attending the test review session.
A really big goal of this is for it to be interactive.
So certainly as we talked through all of the topics from Week zero all the way up until week seven, definitely feel free to flag any of us and raise your hand and ask questions because we want this preparation session to be an opportunity for you to get your questions answered about whatever topics you might have questions about.
Over the course of the curriculum that we've covered so far in general is goes.
We think about all the different weeks in the different topics we've talked about from weeks weeks.
There have been a number of different themes that have come up again and again, and one of the big things that we try to emphasize as we think about preparing for the test is thinking about those big themes and how it's connected.
Thio Ah, lot of the different topics that we've covered over the course of the course so far.
So the first of which is this idea of abstraction the idea that once you've been able to understand the underlying details of something, you can begin to think about it at a higher level without needing to worry about those underlying details.
So we saw that way back in scratch week when we introduced the idea of, like, functions and function, blocks that abstract away the details within them, or the idea that once we understand that electricity could be on or off, we can build abstractions on top of that in the number system and other systems that we use for representing information on.
Then we saw that in more recent weeks with things like data structures, where data structures can often be thought of abstractions of her lower level ideas or even more modern programming languages like Python that introduce a lot of new abstractions.
Easier ways of implementing particular tasks in comparison to a language like see where you didn't need to worry about a lot of those underlying details as you went about designing those programs.
Algorithms there Another big theme thinking about If you're given a problem, what are the step by step instructions you might use in order to solve that problem?
Remembering that in that process, you need to be very precise about telling the computer exactly what it is you want the computer to be doing.
You saw that this past Friday when we were doing the drawing example.
Where when you're trying to draw figure on the board, you have to be very precise about the instructions you're using in order to do that, representation is all about, like taking information and representing an inside the computer.
So we saw a lot of different ways to do this for things like, How do you represent text?
But also, how do you represent images?
How do you represent more complex data?
How do you store all that inside of a computer?
Another theme that has come across a lot during the course and then security, thinking about with any of the decisions we make.
Computers are vulnerable, and where are those vulnerabilities?
We saw a couple of those vulnerabilities when we're talking about databases this past week.
But we've seen other vulnerabilities when we consider things that might happen when things go wrong.
And so we'll be talking about a couple of those today and definitely feel free to ask about them as well.
And then, finally, a big theme has been trade off the idea that any time we get something in computer science, it often comes at a cost that an algorithm that might be faster might come at the cost of using more memory or an algorithm that might allow for certain operations might come at the cost of being a little bit slower.
And so, always thinking about with any of the decisions that we make in computer science, what the tradeoff there are.
What are you getting for?
The choice that you're making and what is the cost of the choice that you're making?
And thinking about those trade offs is another big theme that has come across time and time again over the course of CS 50.
So as we go through, all the weeks of the class will go through one week at a time.
Be thinking about those themes and how they connect to the topics in the course, because those will be some of the key takeaways from the class so far, questions about any of the fiends and the big ideas of the class.
Before we go into, we'll start with a zero.
All right.
In that case, I'll turn things over to Emma.
All right, so we're going to start where you all started with scratch and computational thinking in the very first or zero with week of the course.
And we began with trying to think and act like computers in a certain way.
So we learned about binary, which is a secrets of bits of zeros and ones, so a bit could be a zero or a one.
A sequence of eight bits would be considered a bite.
You can represent numbers from 0 to 2.
In this way, anybody know what this number is in binary?
Some quick maths.
It's really easy.
If you guessed the number that we would put on the board, what would it be?
50 Exactly.
So here you can think of.
It's sort of like, um, a base to system.
So wheat counts, typically with the base 10 system.
You have your once place.
You're tense place your hundreds place, et cetera.
And those are the sorts of operations that we're most familiar with in regular math, but in binary math.
Instead, it's based to sow the first place.
The two to the Zeros place could be either a zero or a one, representing quite literally, a zero or a one and so forth, all the way up to two to the seventh for eight bites for eight bits to make one bite.
Questions about binary great.
So moving on from there.
We have different representations of numbers, letters, things that we would want to store inside of our computer, that we also want to be aware of how those air actually represented in memory itself.
So in Caesar, you learned a lot about asking values, numeric representation of letters.
We know that they're different for upper case and lower case letters, as you learned with your two lower and two upper functions, it coating and see later in the course.
Thes numbers are also ultimately represented in binary, so this 65 which represents a would be represented similar to the number 50 that we saw on the previous slide in by dairy.
When it's stored in the computer's memory and moving forward.
We thought about another way of representing something that you're interested in in the filter problems that you had to do with RTB triples.
And so rgb values or numbers from 0 to 2 55 representing the amount of red, the amount of green and the amount of blue in any given pixel, you know that you are able to manipulate those values individually.
You're able to manipulate them as a series.
And in your computer they're stored as the values for the RGB numerically, just like asking.
And then ultimately, again in binary questions about representations of data.
Yeah, yes, And so ultimately, the question is, the sum of the Artemis values is ultimately to 55.
And so, yes, they go all the way up to that great other questions.
Cool.
If we think about how, then we knew the letters individual and the numbers themselves, then we think about algorithms as a black box.
And so in the first weeks you were given access to things like get string and get integer, where you were able to take a number from a user.
You had some text right after it in order to get those values that you needed.
Ultimately those things We didn't need to know how exactly they were working as long as we were using them properly.
And so get straying.
You knew that you had to write, Get underscore string.
You had to import the CS 50 library, then say, you know, ask for the name of a person in quotes right afterwards.
And then they would type in a string to the computer, which your computer with them store in whichever variable you used there they get string documentation, and the actual code behind how it works is somewhere in the C s of the library.
You could find it if you wanted it, but you didn't actually need to know how it was implementing such a thing in order to use it correctly.
A lot of the power of computer sciences reusing things that other people have written before.
And so here we think about a lot of those sorts of things that you used in the first weeks of the course as black box algorithms.
It takes an input.
In this case, it took a string from the user, and it gives you your desired output variable that holds that string questions about this black box structure quote.
So moving forward, then in scratch, you were able to see visually what these sorts of things looked like.
And so we learned about all sorts of, uh, tools that we have in computer science, such as functions.
It takes something like this.
The blue ball block boxes in scratch and says, Move 10 steps.
10 is the input that you give the function if you think of it, sort of like, um, your main function.
It takes in any sort of variable, usually returns void because it doesn't return anything directly.
Here.
This takes in an Intruder 10 and it moves that direct number of steps.
And so if we go to our thing about a previous life, the input is ton.
The output is the action of moving 10 steps.
Variables are something distinctly that holds a value, and so it could hold a string.
It can hold an integer any number of things that you define.
In this case it's sets my variable, which is the name of the variable to be 28.
That's a sort of tool that you would use money other times and see in python and beyond conditions hold Boolean statements, and so you have ifs.
L ifs else else's don't hold anything because they're your ultimate final thing that's going to happen in your code.
However, here, you know that you're if then conditions taken something called a pooling expression.
It says.
Either you know, if a equals B.
If A and B are both true, um, or operators, not operators.
You would learn about the syntax draft leave.
How would you?
You would use those things and see, and in Python later, you know that they change a little bit the double ampersand for aunt and see the actual word.
And in Python, however, the idea is always the same, and you know that you were able to compare any number of things of the same type in this way, loops and a similar vein represented and scratch.
With these yellow blocks, it can repeat something a certain number of times you learned about while loops about do while loops et cetera, and they are able to repeat actions any number of times that you define.
And those were all of these sorts of things that you use and became familiar with in scratch weeks.
Any questions about those broad concepts?
Cool.
So then we'll move into week.
What were you guys got the opportunity to start coding in the CIA using See your first programming language and the very first program that you likely wrote was this one you included standard io dot h and into Maine void You then wrote Print F Hello World into Maine is off.
Hold the void because it doesn't directly return any values.
The function isn't returning anything to be used anywhere later, but rather it's simply printing this message to you that you are now a computer.
Scientists you confront Hello world, And this was where we started.
One moving from here We learned about all sorts of different types of data.
So we know that a Boolean is something that returns true or false, true or false, are booming values.
A character is a single letter.
A double and afloat are sort of related afloat is an intruder is a number that has a decimal point in it.
And so it could be like 1.0 is afloat, whereas one is an integer you can represent things with more precision using close than you could.
Potentially using into a double is afloat that has 16 bites of memory rather than eight or eight bites memory rather than four.
And so that gives you even more ability to be even more precise with your calculations using a double rather than afloat.
Similarly, with an inter long and it's four bites along is eight, so you could hold more information along has represented, sometimes in different ways, in different coding environments.
But for the sake of the I.
D, it would be eight bites and then a string, which is in a right of characters.
You learned later a little bit more about what means in terms of memory directly.
But for the sake of Week one, we knew that strings, worries of characters, questions about data types, Yeah, for thanks, other questions cool.
So moving forward.
Once you had all of the tools to build whatever sorts of did, then you were able to use it.
So here we used functions like get string.
There was black box abstractions that are made available to you through the CS 50 library, and you would rate your variable name, string name You declare it with the crack type and then get string Name.
Then if I typed my name Emma in when prompted, then name would be a variable that held the string Emma or the array of characters.
Emma.
Um And then you could print using this in tax with the percent s to hold a space for a string essentially and then pass in the variable name for conditional is they would look something like this.
This is very familiar to you as well.
He would write if excellence and wine print this X is greater than why else, et cetera.
You know that if you have an ultimate condition, then you put it in an else without a boolean expression because anything else would fall under that, um, condition automatically by not satisfying any of the previous ones.
Questions about any of these things so far and see syntax.
You're all experts.
I know.
So then if we move forward into loops, you would write for anti equal zero I less than 50 I plus plus how many times with that print something or do the action in the middle 50 because that's how you said it.
So the constraints in the middle say the number of times that you want something to happen, and that's every loop you define has that sort of road map for how many times you want something to happen.
Loops also can be like a wild loop, so this one doesn't directly generate over with.
I you can use something like this if you don't actually need that value of I to influence the inputs that you're going through.
We know that for a lot of our programs earlier, like if you think about moving through an image you needed that I value in orderto orient yourself within a picture, etcetera.
But sometimes you just want to do an action a certain number of times.
Then you could have a wild loop or even a do I loop, which does something as long as another condition is true.
Something else that you saw with maybe getting inputs from the user that match a certain number of constraints that you watched a set questions about loops great.
So then we learned how to define our own functions, and so you know that sometimes it's easier for both readability and repetition within your code in order to create functions of your own so that you can call them up in your main function and do the same thing over and over again without having to physically right, repetitive code.
We know that as programmers, we want to be a CZ lazy as possible, and functions are a really great way to abstract out some of your logic and then apply it later in the future.
So here we have a function for cough on that takes in an inch of your end and then four eyes less than the integer, and we cough that number of times.
And so you would be potentially in your main function.
You would say something like get an integer from the user into your end and then cough that number of times maybe for every single person in this room.
I wanted to give you all an opportunity to cough him over many times he would wish, and then it would make a lot of sense toe have this function separated so that I didn't have to repeat this code every time.
I would just have to repeat getting an intruder and from you individually and then running the call function with Inter Duran.
Any questions about functions?
Yeah, something to do.
You like to find it, like at the end, But something notice reference code that you what's so I think the questions about structuring your code so that coat, like if your main function is above it, understands that the functioning this later and so you can declare functions earlier on so that you can use them so you don't get like weird C syntax Evers in order to use things in the order that you want them while they might be created later, because this would probably down lower in your coat and your main function would be above it.
What other questions you have about functions?
Sweet.
So then you dealt in your quiz with floating point in precision, and so we know that computer memory is complicated.
It only gets more complicated as we get later in the course.
But we knew even now when we were doing programs like cash that your computer memory doesn't have space toe hold things exactly the way that they are.
And so, in a function like cash, you had to use the round function because when you divide to buy 10 it does 100.200000 That's all very correct.
And then it sort of goes off the wire because if you think about the way that things are stored in memory, there might you might run into other blocks of things that aren't directly related to what you calculated.
And so you always have to be careful about floating point in precision in order to be sure that you apply the round function, et cetera, that you're always getting back the results that you're looking for.
And then a similar memory error that we saw in the Gandhi problem of one of the quiz is that you did is integer overflow.
So here is a function that takes an intruder.
I equals one and wild True, which is essentially the sea equivalent of a forever block in scratch.
Um, you would print f I and then multiply.
I buy two.
And so this would go on forever.
Never, Never, never, never.
Until the intruder I that you defined originally can't hold it anymore.
It would overflow back to the beginning.
And so, like in the Gandhi problem, where you tried to subtract two from zero when you ended up at the highest possible aggression rating.
You have to be careful about where your values are headed and whether or not you have enough space to hold them there.
Questions about integer, overflow floating point in precision Great.
So that is all for week one.
That's when you were able to do your problem.
Sets the first ones in See Mario Hello and Cash.
And then we moved into Week two, where we talked about a raise and compiling.
And so one of the first things we looked at was using clang.
Here we had this big, bulky line where you took in the name of the program and the libraries that you had to import.
All of that was difficult to remember and difficult to execute.
And so then we gave you something called Make, which was made compiling a little bit easier.
It did this whole process for you, where it took your original source code.
Say the program hello dot c.
It did pre processing, which is the process of taking all of the things that you hashtag include like standard I over the CS 50 library and turns those along with your initial source code into assembly code.
Um, in compiling, then the assembly that assembling assembles at assembly code essentially and then linking links them all together.
And so when it's turned into assembly code, the things that you included instead I owe in the seas of the library and you're so source code, are all separate versions of us all Separate assembly code files linking puts them all together into one big binary file that your computer can read and execute correctly.
And so this is the big, scary process behind the make function, which simplified a lot of it for you.
What questions you have about compiling great.
And so once we knew how to compile and run things and our code got a little bit more complex, there became a need to be able to debug it.
When you're taking the test, it'll be important to note that there won't be office hours or tutorials as usual for other people to help find your bugs.
And so it will ultimately be up to you to use the tools that we have given you and your own knowledge of how things are working in order to debug any coding aspects of the test itself.
So you know that we have the tools help 50 and debug 50 notes on how to use both of them are in the notes tab of the lecture to slides and presentation.
And then you always know that you can use print off statements in order to see where you are at any given time.
So if you know that something is messed up in a four loop, you can print every single variable using that four loop and usually tell by process of elimination and some clever printing where you're going wrong.
Yeah, so python is a little bit different in terms of compiling, because you don't Yeah, we'll talk about this a little more when we get to high phone.
Want to be in a couple of sides?
But in short, this is the process for seen.
Things look a little different for python because Python is what we would call an interpreted language as opposed to a compiled language like seem.
And so the way that you run Python programs is a little bit different, but we'll get there.
It's a little fuzzier cause you don't impact memory directly, and things are a little bit more abstracted.
Generally, just at one point there and see, you'll notice that if you have some sort of syntax errors, you can't run the code because the compile it'll catch those errors and break before your program actually executes.
Whereas in python it just kind of executes line by line until they're some sort of error.
And then your program crashes, so you'll notice.
In Python files, you can have, like 1/2 functioning program that does everything is expected and then crashes, whereas didn't see you're not allowed to run it until you fix all the books.
Yeah, like caldrons.
Look, we will talk about that when we do pointers and memory accessing.
But that's another tool just like this that you would want to have in your back pocket for debugging on your own.
Great.
So moving on from debugging, we'll talk about a rate so a razor, a super powerful data structure, you're able to store things in continuous blocks of memory, and so if you want to be sure that things are right next to each other in a way that's easily accessible and, uh, you could use indexing in order to get to it all.
Then you would want to use an array.
So here, if we run into value, then we get an actual integer called value.
But if we write into values in brackets five, then we get an array with size spaces for intruders, and those would all be stored next to each other.
We could do any number of things with them.
So, for example, I swear I didn't make these slides.
Brian made them.
I'm not that vain.
Um, but if we have a string name Emma, that we know that that story as an array of characters eat on them, eh?
And then annul character.
So even though my name was only four letters, it needs five spaces of memory.
Um, that automatically gets stored as an array.
If I wanted to say, uh, array name Brockett five, then I could later put the strength the individual characters into it in order to get the same output.
What questions?
Do you have a batteries?
Great.
Oh, So then we talked a lot about command line arguments because it's limiting toe only be able to do as we did in Mario prompt the user for input.
Once the code has compiled and started running and then act based on that.
It's a lot more powerful if we're able to take things indirectly and act upon them in our code itself.
And so here, um, we have Mario where you made Mario and then it compiled.
And then you use those arguments.
And then we had a plurality where you passed in the names of the candidates themselves to the command line.
And so here, for a plurality, we know that we have in dark sea and string.
RV, which is the dark sea, is a number of arguments that you passed in, including the name of the file itself and R.
V is the array of the inputs to that file.
And so here.
What would our CSI be for this called a plurality for and your array would be, what I'll talk a little louder.
Yes, And so then it's directly the things that you typed in these four distinct strings of characters and then the ark see, is a number of things you typed in, which in this case would be four.
Great.
So that's all for a week.
To what questions you have about command line arguments raise anything from the past two weeks.
Yes, I think you still consider it to be annulled character, but it's not something that you access.
So you wouldn't say like this is none directly.
Do that Insurance Python.
The idea of the string has been obstructed away a little bit, so you don't need to worry about how exactly that string is stored in memory.
It's stored in a more complex way and python.
Then it isn't seen.
Um, so you don't need to worry about the Knoll Terminator when it comes to python.
Yes, yes, yes.
So if you had an array, if I put into that array of whatever the one of values 123455 would be the fourth technically index of that array, there wouldn't be a no character at the end.
Sorry, the question was, no.
Characters are only four string or is character is yes, so that's correct.
So there are four things stored in it, but with zero indexing.
Yes, actually, I'm pretty sure that Argus accounts from one number of commandment arguments.
And so if therefore commandment arguments, and our CSI has four.
That means the individual arguments A store that RV zero R V one RV to an r B three.
Similar to how If we, you know, create the interview right with space for five things, the fifth character would be at the fourth index thistles.
Something that you can test yourself a swell when you're, you know, and the idea you can just whip up a quick temper dot C file and just right, like print What's our CSI?
What's RV or like loop through the elements and RG so that you can see for yourself and get this better Intuition.
Um, instead of having to try to memorize, you can actually just test for yourself and see it.
Yeah, their store doesn't array of characters.
Yes, And so then that's why in C programming, when you were taking in, I liken intruders in your array.
Then you had to make, like, apply the inter function to them.
Great.
So now Brian is gonna talk to you about algorithms.
All right, So, weeks what?
012 We're really about building up the fundamentals of how to write programs in a programming language like sea.
So Emma talked about the building blocks of variables and conditions and loops.
And now that we had a lot in functions and now that we have all this capability, the next step is how do we use that in order to solve problems?
And so this was what we three of us about.
We thought it was all about algorithms trying to figure out how do we write code that is able to take these inputs and solve some sort of problem in the problems that you use this in order to implement a variety of different election algorithms.
So a simple, poor, out plurality election that counted up, who has the most number of votes but then looking at more sophisticated algorithms like a runoff election or the Tide Men election method that run a little more of a complex algorithm to try and figure out who the winner of an election is.
But a lecture We talked about a couple of strategies for how to represent information and then how you use that information inside of an algorithm.
And the first key idea was the idea of a struck.
And so here, give us the ability to create our own types, where Emma introduced the basic types that are already built into the sea, programming language types like into and float and bull and char on long and double in those sorts of types.
But if we needed to represent other types like we wanted to represent, Ah, person, for example, is we saw in lecture or in the problems that you saw the representation of a candidate as a brand new type.
In later problem sets, you saw a type for RGB triples for a triple of red, green and blue in order to store a pixel of information.
None of those types are built into the sea programming language, but that's okay, because we can create our own types in order to represent that information.
And so what we had here was the definition of a new type called person where the way the syntax worked as we use the type deaf key word to say, let me have a new type with a particular name.
What is that type?
Well, the type is a structure or a struck, where you can think of a struck as a way of encompassing multiple different pieces or types of information into a single unit into a single value.
And so inside of a person we're going to represent a person using two pieces of information.
Every person has a string called name and everyone.
Every person has a string called number that represents their phone number, for example, and recall that we used a string instead of an inch because we wanted to be able to represent maybe hyphens or parentheses that might have been included inside of the phone number.
So a string was a more reasonable choice for that.
But we can choose exactly what we want to be inside of that structure.
And so, with RGB triples inside of here, we had separate fields.
We might call them for some amount of red, some amount of green, some amount of blue for candidates.
We included a field in here for a number of votes, but in short we could take whatever data we wanted a store in, compass it all together inside of a structure, and then call that new type a person or whatever type we wanted, and that gave us the ability to more abstractly represent the idea of a person or a pixel somewhere inside of our program.
Questions about creating your own types of structures.
What questions do you have about that idea and how that worked?
Yeah.
Oh, yes.
Oh, good question.
The question is, when?
Why did?
Later on in future weeks, we sometimes had to include the words struck somewhere inside of this definition that was used when we needed for our data for the type that we were creating to be able to somehow reference itself.
And so this came up in particular when we were talking about linked lists where every linked less node contains a pointer to the next note in the link list.
Rodrigo will talk a little bit more about that later.
But in short, when we need that recursive data structure, we need some way of referencing itself.
And so we had to add an extra key word here.
But we'll see the syntax for that in just a bit too.
But very good question.
That was why we needed that.
Other questions about types and structures of data.
All right, so what do we use those structures of data for?
And what was the purpose of it?
Well, the first thing that we tried to do was solve the problem of being able to search for something inside inside of an array, for example.
And so there were a number of different ways that we could search for something.
But one way was to say, for example, if we have a big list of unsorted things, we could use linear search to say, like, started the very first element in the array and then look what element at a time in order to try to find it.
And then someone remind me, like in running time, What was the big O of linear search?
How efficient is linear?
Search a search for something?
Yeah.
Oh, of n yeah, linear time to be able to search for something big O notation recalls, sort of encodes the idea of what is the worst case or the upper bound on how long it might take for this algorithm to run.
And so, in the case of linear search, it might take us.
If we have any elements inside of the array that we're looking for him, it might take us end steps in order to look through it, and so that was one method of searching for something and what was a more efficient way to search for something inside of an array.
If we stipulate, for example, that theory, it's sorted.
Yeah, oh, of law again.
And we used an algorithm for that called binary search.
So binary search, another search algorithm only works when the array assorted in linear search doesn't matter whether the array of sorted or not.
But the idea of binary search is all right.
Let's say we're looking for the number 50 inside of an array.
We first say, Alright, wolf.
There's nothing in the array returned false.
We didn't find the number 50.
If the middle item of the array of 50 well, then we found fifties have return true.
And what are the only other possibilities?
Well, if 50 is less than the middle item, then we need to search the left half because of 50 is less in the middle item than if 50 is inside of this array.
It's got to be in the left half of the rent, so we'll search the left half of the raid.
The array and otherwise a 50 is greater than the middle item.
Then we'll search the right half in order to try and find that number.
So this algorithm gives us a couple of different insights.
But one of the big ideas is this idea of Rikers in that we're solving a big problem by solving a smaller problem that a 50 is less in the middle item.
Then we repeat the same algorithm just on the left half of the Iran, and we can keep repeating this process of solving a smaller and smaller and smaller problem.
Until either there's nothing left in the array, in which case we returned false or the middle item, it's 50 in which case we found the number we're looking for, and in that case we could just return.
True.
And so if we compare the running times of these, this is where Big O notation came in.
This was the more mathematical side of Week three.
Thinking about giving an algorithm.
How long is it going to take for that algorithm to run?
And computer scientists use the notation called big O notation to represent that idea where Big O is all about the upper bound.
In the worst case, there is an upper bound how many steps will it take for the algorithm to run if there are any inputs?
So in this case, if their end items in the list, how long might it take to be able to search for a particular element?
And we decided that all right, for linear search, the running time is big o of end.
If there any elements in the list, it might take us end steps to be able to find the thing we're looking for.
Because in the worst case, it might be all the way at the end of the Erect.
And we have to make our way through the whole array in order to be able to find it.
And then, as someone mentioned, binary search is an improvement on that.
In the worst case, it's law again if we assume that the um, yeah, if we're looking through the array, it's law again because we can cut the problem in half over and over again.
We can look for the middle item, then choose 1/2 and then just keep looking to the next half of the items, and we don't need to look through every single value in the array weaken, jump around a little bit in order to narrow our way down to the one value that we're looking for.
So in this sense, O of law again is a faster algorithm.
In the worst case, binary search was better.
But of course, it came at the cost of requiring that the list is sorted to begin with are right needs to be in sorted order another in order for binary search to work.
Otherwise, it's not going to work.
So that's binary search.
And also, as we introduced is part of binary search Big o notation in the sanitation we use for describing the runtime of algorithms how long it takes for an algorithm to run.
What questions do you have about that?
Viggo notation algorithms run time.
All right, We feel OK about that.
In that case related to big O notation with another notation.
So while Big o describes the upper bound on the running time of any algorithm, there was another notation we used called Big Omega, which was all about the lower bound on the run time of an algorithm.
So you can think of that is like in the best case, how long might the algorithm take?
And for linear search and vinyl research, what is the big Omega?
How long would it take in the best case if we get lucky, for example?
All right.
Heard a couple people say it.
Oh, of one.
In other words, constant time in the best case, meaning just a single step or some fixed constant number of steps.
And why is that?
Well, because we might just get lucky.
And the first thing we look at might be the element that we're searching for.
We might find 50 at the very beginning of the list.
In the case of Linear Search, we might find 50 at the exact midpoint of the list in the case of binary search.
So depending on the algorithm, we might just get lucky.
Or, depending on the array that we start with, we might get lucky and get the answer immediately.
So often in algorithms, you'll find that the big omega lower bound on the running time of the algorithm can be different than the big O of that algorithm.
What?
It might take us an upper bound on time and knowing the difference between those two and being able to think about that algorithm in deciding what is the big O of this algorithm.
What is the Big Omega that can often be a helpful way to frame an algorithm and think about the implications of its particular running time?
Questions about runtime Big Oh, a big Omega.
How to think more abstractly about these run times?
Another useful thing to remember is that when it comes to Big O and Big Omega, we didn't really care about the constant factors or the smaller terms inside of the runtime.
So it didn't matter if this was, like end steps or to end steps or three end steps.
The constant factor didn't really matter.
What we cared about is what happens is end gets very, very big.
And so we can throw away those constant term, so to speak and an algorithm that takes three end steps or four end steps we can really just consider to be o of Eddie steps.
It's the end part that we care about more so than what the individual constant factors happen to be.
All right, so that was searching for something, and we stipulated the binary search only works.
If we have a sordid or write first.
And so one of the next questions that came up with algorithms was, How do we sort things?
What are algorithms we can use for doing that?
And we looked at at least three different algorithms for being able to sort things, and the first of which was bubble sort here, represented in pseudo code.
We're the big idea of Bubble sort is if we have a big array where the elements air unsorted.
We look at the elements in that array two at a time, look at a pair of elements and in assorted array, the element on the left should always be less than or equal to the element on the right in any pair of elements.
And so we look at any pair of two elements, and the element on the left is greater, then the element on the right.
Then those two elements are out of order, and we can swap them, and that's what bubble sort is all about.
It's going through the entire array, pair by pair by pair and making swaps whenever two elements are out of order.
So the algorithm is we're going to repeat this and minus one times will come back to why and minus one in just a moment.
But we're going to repeat this from I from zero to n minus two.
So from the very first element in the array and up until the second to last element in the array recalled that if we have an array that has n elements, the first element is element zero.
The last element is and minus one a little bit tricky because you have to start counting it zero.
But for each element, I we're gonna look at Element I and II plus one, and if they're out of order, we're going to swap them.
And so we repeat that process again and again, making a SWAT, making this a lot, making the slop.
And at the end of this inner loop, the effect will be that whatever the largest element in the array is, it will bubble its way, so to speak, to the top of the array because we'll continue to make swaps until the biggest element gets to the right most position in the array.
And there's one element that we have not sorted, and after that we could go back and do the same thing again and again and again.
And we only need to sort n minus one elements into their correct place.
Because if you have an array of an elements and n minus one of them are in the right place, then the last element must also be in the right place because there's nowhere else for it to be.
And there was a visual demonstration of this shown in lecture where actual people were standing up here and they were switching places in order to figure out how to get into the right order.
So that might be a helpful thing to go back and look at just to familiarize yourself with bubble sort.
But if you recall from bubble Sort, there was an optimization we could make to make it more efficient.
And you remember what that optimization waas Yeah, merge sort with an entirely different algorithm.
But yes, it was more efficient, and we'll get to that in a moment.
But with bubble sort specifically, there was a way we could make it more efficient.
Use a wildly Yeah, and the idea here was where we don't always need to repeat and minus one times because as soon as we go through the elements pair by pair by pair, as soon as we go through all the elements and we don't swap anything, we can effectively stop running the algorithm.
Because if we make it through the entire array and we never need to make any swaps, then we can just stipulate that the entire array must now be sorted.
And so we were able to make this algorithm slightly more efficient by repeating until there were no more swaps left to make.
So a slight optimization that might require running this algorithm fewer times questions about bubble sort and how that algorithm works.
Yeah.
How can you tell that you're not?
How can you tell that you're not swapping things well to do it?
Just a bit of a visual example.
If we imagine we had four elements, let's say we had a three year and then one thio and then four.
What we would do in Bubble Sort is we would start with these 1st 2 rights a three and one.
Are they in order?
Out of order?
Well, three is greater than one.
So these air out of order.
So we would swap them.
And so this would be one and then three.
Then we go to the next three and two.
Well, these about her out of order as well.
So we'll go ahead and swap those.
And so now we have to And three.
Then we look at three and four and say, Are these in order or out of order there in order?
And so we don't need to do anything here.
So that was one pass through the array.
We went pair by pair by pair, making swamps, and then we might check this again.
Say All right.
One and two.
Have we made it?
Do we need to switch anything?
Well, no, we don't.
They're good.
Two and three.
Do we need to switch anything?
No.
Three and four.
Do we need to switch anything?
No.
And so we made an entire passed through the array and we didn't need to switch anything.
And so if you're keeping track of, did I actually have to switch anything?
And the answer to that question is no.
Then at the end of that, I can say this