# CS50 2020 – Lecture 3 – Algorithms (pre-release)

all right

this is cs50 and this is week three and

and they tend to focus only on the dominant factor like which value in that mathematical expression is going to grow the most grow the fastest and n divided by two n is going to dominate over time the bigger the phone book gets the more pages you have it’s really n that’s going to matter less so than that divided by 2. and same thing over here if you’re familiar with and remember your logarithms we don’t really have to even care about the base of that logarithm yes it’s base 2 but we can just multiply that logarithm by some other number to convert it to any base we want base 10 base 3 base 7 anything so let’s just say it’s on the order of log n so this is good because it means we’re not really going to waste time getting really into the weeds mathematically when we talk about the efficiency of algorithms it suffices to describe things really in terms of the variable and in this case if you will that dominates over time and indeed let’s zoom out if i zoom out on this picture boom you begin to see that yeah these are really starting to look almost identical and if we kept zooming out you would see that they’re essentially one and the same but the green one stands out so that’s indeed on the order of log of n as opposed to n itself so here’s a little cheat sheet it turns out that within computer science and within alg the analysis of algorithms we’re going to tend to see some common formulas like this so we’ve just seen on the order of n we’ve seen on the order of log n it turns out that very common 2 is going to be n times log n maybe even n squared and then even big o of one and the last of those just means that an algorithm takes wonderfully one step or maybe two steps maybe even ten steps but a constant number of steps so that’s sort of the best case scenario at least among these options whereas n squared is going to start to take a long time it’s going to start to feel slow because if you take any value of n and square it that’s going to imply more and more steps so just a bit of jargon then to start off today whereby we now have this sort of vocabulary with which to describe the running times of an algorithm in terms of this big o notation but there’s one other notation and just as big o refers to an upper bound on running times like uh like how many steps maximally how much time maximally might an algorithm take this omega notation refers to the opposite what’s a lower bound on the running tom of an algorithm and we don’t need another picture or other formulas we can reuse the same one so this cheat sheet here just proposes that when describing the efficiency or inefficiency of an algorithm and you want to come up with a lower bound like minimally how many steps does my algorithm take we can use the same mathematical formulas but we can note that with omega instead of big o so again looks fancy but it really just refers to a wave of the hand trying to sort of ballpark exactly what the running time is of an algorithm and thankfully we’ve seen a few algorithms already including in that week zero and now we’re going to give it a more formal name linear search is what we did with that phone book first off by searching it page by page by page looking for my phone number in that particular example and so the difference today is that unlike us humans can who can sort of look down at a phone book page and see a whole bunch of names and numbers at once unlike a human who can look at an array on the board a moment ago and sort of see everything at once we need to be more methodical more deliberate today so that we can translate week zero’s ideas now not into even pseudo code but actual c code and so wonderfully here at the american repertory theater as we are on harvard’s campus this semester we’ve been collaborating with uh the whole team here who are much more artistically inclined and certainly i could be on my own here and we have these seven wonderful doors that were previously used in various theatrical shows that took place here in this theater and we’ve even collaborated with the uh theaters prop shop who in back have wonderfully manufactured some delightful numbers and brought them to life which is to say that behind each of these seven doors is a number and this is going to be an opportunity now to really hammer home the point that when we want to search for some number in an array it’s pretty equivalent to having to search for a number in this case behind an otherwise closed door you and i can’t just look at all of these doors now and figure out where a number is we have to be more methodical we have to start searching these doors maybe from left to right maybe from right to left maybe from the middle on out but we need to come up with an algorithm and ultimately translate that to code so for instance suppose i were to search for the number zero how could we go about searching methodically these seven wooden doors for the number zero let me take a suggestion from the audience what approach might you take what first step would you propose i take here on my own with these doors any recommendations how do i begin to find myself the number zero florence what do you propose um i would propose starting from the left since zero is one a smaller number okay good and hang in there for with me for just a moment let me go ahead and start on the left as florence proposes go ahead and open the door and hopefully

dot slash names okay now something’s clearly wrong right i can even search for the father arthur make names dot slash names it seems that i wrote you a program that just literally always says found so we shouldn’t have accepted this as correct can anyone spot the bug based on my definition thus far can anyone spot the bug you know in the meantime this isn’t uh really a bad time to open up the duck and say uh hello duck i am having a problem whereby my program is always printing found even when someone is not in the array and i could proceed to explain my logic to the duck but hopefully sophia can point me at the solution even faster than the duck yeah we need to compare the value that we receive from stir comp with something so we need to compare it with like zero and make sure that we receive the value that they’re equal perfect so i said the right thing but i literally did not do the right thing if i want to check for equality i literally need to check the return value when comparing names bracket i against ron to equal zero because only in the case when the return value of stir comp is zero do i actually have a match by contrast if the function returns a negative value or the function returns a positive value that means it’s not a match that means that one name is supposed to come before the other or lay after the other but the catch with my shorthand syntax here which is not always an incorrect syntax to use whenever you have a boolean expression inside of which is a function call like this notice that the entirety of my boolean expression is just a call so to speak to stir comp i’m passing in two inputs names bracket i and quote unquote ron and therefore i’m expecting stir comp to return output a so-called return value that return value is going to be negative or positive or zero and in fact to be clear if the first name being searched for is bill and names bracket i or names bracket zero is bill bill comma ron is effectively what my input is on the first iteration bill alphabetically and asciibetically comes before ron which means it should be returning a negative value to me and the problem with boolean expressions is as implemented in this context is that only zero is false any other return value is by definition true or a yes answer whether it’s negative one or positive one negative one million or positive one million any non-zero value in a computer language like c is considered true also known as truthy any value that is zero is considered false but only that value is considered false so really i was getting lucky at first because my program was finding bill but i was confusing bill for ron then when i did it again for caleb and i capitalized ron i was getting unlucky because suddenly i knew ron capitalized wasn’t in the array and yet i’m still saying he’s found but that’s because i didn’t practice what i preach per sophia is fine and so if i actually compare this against zero and now caleb we come full circle to your question i rebuild this program with make names i now do dot slash names and search for all caps wrong i should now see thankfully not found so i wish i could say that was deliberate but thus is uh the common case of bugs so here i am 20 years later making bugs in my code so if you run up to a similar problem this week uh rest assured that uh it never gets um it never ends but hopefully you won’t have several hundred people watching you while you do your problem set this week all right any questions then beyond caleb so great question caleb and the answer is no it is case sensitive so it does not find rob ron any questions here any questions on linear search using strings no all right well let’s go ahead and do one final example i think with searching but let’s introduce just one other feature and this one’s actually pretty cool and powerful up until now we’ve been using data types that just come with c or come from cs50 like int and char and float and the like and you’ll see now that there’s actually sometimes reasons where you or i might want to create our own custom data types our own types that didn’t exist when c itself was invented so for instance suppose that i want to represent not just a whole bunch of numbers and not just a whole bunch of names but suppose i want to implement like a full-fledged phone book a phone book of course contains both names and numbers and suppose i want to combine these two ideas together wouldn’t it be nice if i could have a data structure that is a data type that has some structure to it that can actually store both at once and

now i’ve put all of my special numbers at the top of my file or toward the top of my file and now i’m using this variable here and then what i could do and i alluded to this only verbally before i could absolutely start hard coding in for instance montague’s name and number and rithfix and benedict’s and cody’s and others but honestly this seems kind of stupid if you’re just hard-coding all of these names and numbers and in a few weeks we’ll see how you can actually store all of the same information in like a spreadsheet or what’s called a csv file comma separated values or even in a proper database which the the facebooks and googles of the world would use but what i could do for now is something like this for int i gets 0 i less than the number of people i plus plus and maybe i could do something like this people bracket i dot name equals get string what’s the name question mark and then here i could do people bracket i dot number equals get string what’s their number and i can ask that question too so now the program’s getting to be a little better designed i’m not arbitrarily hard-coding just me and brian now it’s dynamic and technically the phone book only supports 10 people at the moment but i could make that dynamic too i could also call getint or like you did this past week use a command line argument and parameterize the code so that it can actually be for two people 10 people whatever you want the program can dynamically adapt to it for you other questions on structs on types or the like no all right so how did we get here recall that we started with this problem of searching whereby we just want to find someone in the doors we just want to find someone in the array we’ve sort of escalated things pretty quickly to finding not just numbers or names but now names with numbers in the form of these data structures but to do this efficiently really requires a smarter algorithm like binary search up until now we’ve only used in c code linear search even though recall that we did have at our disposal this pseudocode for binary search but with binary search we’re going to need the data to be sorted and so if you want to get the speed benefits of searching more quickly by having sorted numbers somehow someone is going to have to do that for us uh joe for instance sorted behind the curtain all of these numbers for us but what algorithm did he use is going to open up a whole can of worms as to how we can sort numbers efficiently and indeed if you’re the googles and the facebooks and the instagrams of the world with millions billions of pieces of data in users you surely want to keep that data sorted presumably so that you can use algorithms like binary search to find information quickly when you’re searching for friends or for content but let’s go ahead here take a five minute break and when we come back we’ll consider a few algorithms for sorting that’s going to enable us to do everything we’ve just now discussed see you in five

all right we are back so to recap we have a couple different algorithms for searching linear search and binary search binary search is clearly the winner from all measures we’ve seen thus far the catch is that the data needs to be sorted in advance to order to in order to apply that algorithm so let’s just give ourselves a working model for what it means to sort something well as always if you think of this as just another problem to be solved it’s got input and output and the goal is to take that input and produce that output well what’s the input it’s going to be a whole bunch of unsorted values and the goal of course is to get sorted values so the interesting part of the process is going to be whatever there is in the middle but just to be even more concrete if we think now in terms of this unsorted input as being an array of input because after all that’s perhaps the most useful mechanism we’ve seen thus far to pass around a bunch of values at once using just one variable name we might have an array like this 63852741 which seems to be indeed randomly ordered that is unsorted and we want to turn that into an equivalent array that’s just one two three four five six seven eight so eight numbers this time instead of seven but the goal this time is not to search them per se but to sort them but before i get ahead of myself could someone push back on this whole intellectual exercise we’re about to do with sorting in the first place like

just put it into this open spot where there’s available space yeah and i feel like it’s it’s starting to become clear that we’re inside some kind of loop because you pretty much told the same story again but with a different number do you mind just continuing the algorithm to the end and select the next smallest next smallest next smallest and get this sorted sure so we got the eight five is smaller than that three is smaller than that and then the rest of the number is seven four six those are all bigger so the three that’s going to go into sorted position here and i’ll take the eight and swap it now i’m gonna look at the five eight and seven are both bigger the four is smaller than the five but the six is bigger so the four that’s the smallest number i’ve seen so far so the four that’s going to go into place and i’ll swap it with the 5 and now i’ve got the 8 the 7 is smaller than the 8 so i’ll remember that 5 is smaller than that but the 6 is bigger so the 5 that’s going to be the next number and now i’m left with 7 8 is bigger so seven is still the smallest i’ve seen but six is smaller so six goes next and now i’m down to the last two and between the last two the eight and the seven the seven is smaller so the seven is going to go in this spot and at this point i’ve only got one number left so that number must be in sorted position and now i would say that this is a sorted array of numbers nice so it seems definitely seems to be correct it felt a little slow but of course a computer could do this much faster than we using an actual array and if if you don’t mind making an observation it looks like if we have eight numbers to begin with or n more generally it looks like you essentially did n minus one comparisons because you you kept comparing numbers again actually you did n comparisons you looked at the first number and then you compared it again and again and again at all of the other possible values in order to find the smallest elements yeah because for each of the numbers in the array i had to do a comparison to see is it smaller than the smallest thing that i’ve seen so far and if it is smaller then i needed to remember that yeah so in each pass you considered every number so a total of n numbers first until you found the number one you put it in its place and that left you to be clear with n minus one numbers thereafter and then after that n minus two numbers n minus three numbers dot dot dot all the way down to one final number so i think this is correct and i think that’s a pretty deliberate way of sorting these elements a little more deliberately than your first approach brian which i might describe as a little more organic you kind of did it like more like a human just kind of eyeballing things and moving things around but if we were to translate this into code recall that we have to be ever so precise and so let me consider altogether how exactly we might translate what brian did ultimately to again pseudo code so what he did is actually an algorithm that has a name it’s called selection sort why well it’s sorting the elements ultimately and it’s doing so by having brian or really the computer select the smallest element again and again and again and once you found each such small element you get the added benefit of just ignoring it indeed every time brian lit up a number he didn’t need to keep comparing it so the amount of work we he was doing was decreasing each iteration n numbers then n minus 1 then n minus 2 n minus 3 and so forth and so we can think about the running time of this algorithm um as uh being manifest in its actual pseudo code so how might we define the pseudo code well let me propose that we think of it like this for i from zero to n minus one now undoubtedly this is probably the most cryptic looking line of the three lines of pseudocode on the screen but again this is the kind of thing that should become rope memory over time or just instincts with code we’ve seen and see how you can write a for loop for loops typically by convention start counting at zero but if you have n elements you don’t want to count up through n you want to count up two n or equivalently up through n minus one so from zero to n minus 1 all right now what do i want to do on the next on the first iteration find the smallest item between the ith item and the last item so this is not quite obvious i think at first glance but i do think it’s a fair characterization of what brian did because if i is initialized to zero that was like brian pointing his left hand at the first number on the very left of the the shelf and what he then did was she found the smallest element between the ith item the first item zero and the last item so that’s kind of a very fancy way of saying brian find the smallest element among all n elements then what he did was sm swap the smallest item with the ith item so we just did that switcheroo so as to not have to waste time shifting everything over he instead just made room for it by swapping it with the value that was in its wrong place but now in the next iteration of this loop consider how a for loop works you do an i plus plus implicitly in pseudocode that’s what’s happening here so now i equals 1 find the smallest item between the ith item item 1 0 indexed and the last item so this is a fancy way of saying brian check all of the n elements again except for the first because now you’re starting at location one instead of location zero and now the algorithm proceeds so you could write

as brian is keeping track of how many swaps he made or didn’t make through one pass as with a variable called counter or whatever he can simply abort this algorithm early and certainly then save us some time so with that said let’s consider for just a moment what the running time of bubble sort might be in terms of an upper bound in the worst case if you will well in the case of bubble sort notice with the pseudo code where we’re doing something n minus 1 times and inside of that we’re doing something n minus 1 time so again repeat n minus 1 times literally says do the following n minus 1 times the for loop here which is just a different way in pseudocode of expressing a similar idea but giving us a variable this time for i from 0 to n minus 1 n minus 2 is a total number of n minus 1 comparisons so this is an n minus 1 thing inside the repeat and an n minus 1 outside the repeat so i think what that gives me is n minus 1 things times n minus 1 times so now if i just kind of foil this sort of in high school or middle school math n squared minus 1n minus 1n plus 1 we can combine like terms n squared minus 2n plus 1. but per our discussion earlier this is really getting into the weeds who cares about the 2n or the 1 the dominant factor as n gets large is definitely going to be the n squared so it would seem that bubble sort if you actually do out the math and the formulas is going to have an upper bound of n squared or rather on the order of n squared steps so in that sense it is equivalent to selection sort it is no better fundamentally it’s what we would say asymptotically equivalent that is as n gets really large this formula is for all intents and purposes equivalent to the selection sort formula even though they differed slightly in in terms of their lower order terms for all intents and purposes ah they’re on the order of n squared both but if we consider a lower bound perhaps um even though bubble sort has this same upper bound running time if we consider a lower bound as with this smarter code where brian might actually have the wherewithal to notice wait a minute i didn’t do any swaps i’m just going to exit out of this looping prema early not even prematurely but early because it would be fruitless to keep doing more and more work we can then whittle down this running time i think not quite as good as omega of one which was constant time like you cannot conclude definitively that an array is sorted unless you minimally look at all of the elements once so constant time is completely naive and unrealistic you can’t look at one element or two or three and say yes this is sorted you’ve got to obviously look at all of the elements at least once so this would seem to suggest that the omega notation for that is the lower bound on bubble sorts running time if we’re clever and don’t retrace our steps unnecessarily is in omega of n or technically it’s n minus it’s one steps right because if you’ve got n elements and you compare these two these two these two these two that’s n minus one total comparisons but ah who cares about the minus one it’s on the order of n or omega of n notation here so to recap selection sort selects the next smallest element again and again and again unfortunately based on how it’s implemented in pseudocode and actual code it’s in big o of n squared but it’s also an omega of n squared which means it’s always going to take the same amount of time asymptotically that is as n gets large unfortunately two bubble sort is no better it would seem in terms of the upper bound it’s going to take as many as n squared steps two but it’s at least marginally better when it comes to using something like uh an input that’s already sorted it can self short circuit and not waste time but honestly n squared is bad like n squared is really going to add up quickly if you’ve got n squared and n is a million or n is a billion i mean my god that’s a lot of zeros that’s a lot of steps in the total running time of your algorithm can we do better can we do better and it turns out we can and we’ll consider one final algorithm today that does fundamentally better just like in week zero we sort of latched on to binary search and again today is just fundamentally better than linear search by an order of magnitude so to speak its picture representation was fundamentally different i think we can do fundamentally better than bubble sort and selection sort and so while both bubble sort and selection sort might be the sort of thing that i was using in grad school just to rip up the code quickly and then go to sleep it’s not going to work well for very large data sets and frankly it wouldn’t have worked well if i didn’t want to just sleep through the problem rather we want to do things as efficiently as we can from the get-go and let me propose that we leverage a technique and this is a technique that you can use in almost any programming language see among them known as recursion and recursion quite simply is the ability for a function