# CS50 2017 – Lecture 3 – Algorithms

Just another WordPress site

### CS50 2017 – Lecture 3 – Algorithms

And then, what do I want to do after this? I want to go ahead and iterate over the characters in the user’s name, and print them out only if they’re uppercase But you know what, rather than just print them out, you know what I want to do? I actually want to create a new string, myself, containing the user’s initials So, I don’t want to go ahead and just print out, with percent c, one character after the other– rather, I want to go ahead and store the user’s actual initials in a new string, so that I’ve got one string for their name, and one string for their initials And, ladies and gentlemen, Ian SPEAKER 2: Sorry for the video glitches DAVID MALAN: Thanks All right So, to be ever more clear, let me go ahead and rename this to name, literally, and then I want to have a string for their initials But we know what a string is, as of last time It’s really just a sequence of characters And a sequence really has another name in programming What is another synonym we’ve used for a sequence of something? AUDIENCE: [INAUDIBLE] DAVID MALAN: An array An array is that data structure we had when we started using square bracket notation So, if I actually kind of roll this back and break the abstraction, if you will– don’t think about it as a string What is a string? It’s a sequence of characters Technically, I could say char, and then I could say initials, and then I can specify however many letters I want to support in a human’s initials And by– assuming we have a first name, maybe a middle name, and a last name, three characters should do it Three characters So, David J. Malan, DJM, three characters Is that enough chars? AUDIENCE: [INAUDIBLE] DAVID MALAN: I’m hesitating, because it doesn’t– AUDIENCE: [INAUDIBLE] DAVID MALAN: It’s not, but why? AUDIENCE: You need for the null character DAVID MALAN: Yeah So if we want to terminate even my initials– which isn’t technically a word, but it’s certainly a string, it’s a sequence of characters– we need a fourth character, or we need to anticipate a fourth character, so that whatever we put in the computer’s memory is technically, in my case– like, D-J-M backslash 0 You need that fourth byte Otherwise you do not have room to actually terminate the string So, now, even though this doesn’t look like a string, insofar as I’m not saying the word string, it really is It’s a sequence of characters of size four that I can put characters in Now, what are the characters in this array, by default, have we said? When you just declare a variable of some size, what values go in it? AUDIENCE: [INAUDIBLE] DAVID MALAN: Sometimes zeros, but generally, what’s the better rule of thumb? AUDIENCE: You don’t know DAVID MALAN: Yeah, you don’t know It’s so-called garbage values Nothing– you should not trust the value of a variable, generally speaking, unless you yourself have put the value there, as by storing it, with the assignment operator, or by manually typing it in yourself So, just to be clear, if I wanted this program to be kind of useless for anyone except myself, I could actually do this– I could go ahead and do– initials, bracket 0, get “d”, initials, bracket 1, get “j”, and then finally initials, bracket 2, get “m” And then lastly, and this is the thing you might forget sometimes, you actually need to do the backslash zero there But of course, this is not at all dynamic But I have, in this these lines of code now, created a new string called initials It’s of length– it’s of human length three, DJM, but the computer is actually using 4 bytes to store it But this is not the point of the exercise, because we already asked the user for his or her name I need to now figure what that is So just logically, or algorithmically, if you will, what process could we use, given a name like David J. Malan, or Brian Yu, or anyone else’s name– how could we look at that input and figure out what the user’s initials are? What’s the thought process? Let me go a little farther back So, David J. Malan, or any other name What’s the process? What do you think? AUDIENCE: [INAUDIBLE] DAVID MALAN: OK, good! So, iterate with a for loop over the letters in the name– and you’ve done that before, or in the process of doing that, for something like caesar or vigenere, most likely And then you can use something like is upper, or you can even do asciimath, like we did a while ago, to actually determine, is it in the range of A to Z capitals on both ends? So we have a couple of options So, let me try to convert that to code Let me get rid of the hard-coded name, which is just kind of nonsensical, but demonstrative of how we could store arbitrary characters And now let me do this For int i get 0, i is less than the string length of name, i plus plus– and then I’m going to do something like this If the i-th character character in name is an uppercase letter– and I’m going to use a function that you might not have used yourself, but recall that it does exist– is upper will return, essentially, true or false, this is an uppercase letter–

so, if this is uppercase, I’m going to go ahead and do what? Well, the story is not quite complete It’s not enough to just iterate over the names and– the letters in the name– we now need to decide where to put the first capitalized letter that we find It’s obviously going to go in the initials array, but what more do I need to add to my code to know where, in this block of four characters, to put the first character, D, in the case of my name? Yeah AUDIENCE: [INAUDIBLE] initials i? DAVID MALAN: Initials i OK, so if I do that– good thought So let’s do, initials, bracket i, gets name bracket i– that would seem to put the i-th character of name at the -th location in initials, which at the moment is perfectly correct, because i is 0 And if I typed in David J. Malan, D is at the zeroth location So, we’re good But there’s going to be a bug here AUDIENCE: [INAUDIBLE] continue to the name, then you’ll have less slots DAVID MALAN: Exactly I is going to continue marching forward, one character at a time, through the entire name of the user, but you only want to index– you don’t want to keep doing that same amount in the initials array, because again, the initials is much smaller So even as i moves through the user’s name, you want to take baby steps, so to speak, through the initials So, how can we solve this? I can’t use i, it would seem AUDIENCE: You could use a variable that’s like a [INAUDIBLE] DAVID MALAN: OK, great Let’s do that We need another variable So, I could put this in a few different places, but I’m going to go ahead and put it here for now So, int counter gets zero– I’m just initializing my counter to zero– and then as soon as I won’t find an uppercase letter, I think I want to do this? Put it at whatever the value of counter is? And then there’s one more step What do I need to do once I, yeah, put it at the counter location? AUDIENCE: Increment counter by one DAVID MALAN: Exactly Increment counter by one So, I can do this in a few ways I can do it very literally– counter gets counter plus one, semi-colon It’s a little annoying to type You could do plus equals one, which is slightly more succinct Or, the ever-prettier, plus plus, which achieves the same result Fewer characters, same exact result, in this case OK, so now, I think we have a for loop that iterates over all the letters in the name If it’s an uppercase letter, it stores that letter, and only that letter, in the initials array, and then increments counter so that the next letter is going to go at the next location in the initials array So, if all that seems to be correct– ultimately, I want to do this– I want to go ahead and print out percent s, backslash n, initials I want to just print the user’s initials But there’s one key step in this blank line that I should not forget What’s the very last thing I need to do? Yeah AUDIENCE: You need to print a null character [INAUDIBLE] put a null character at the end of the [INAUDIBLE] DAVID MALAN: Exactly I need to put a null character at the end of the array So, how do I do that? Well, I have the syntax, and I think– you know, I want to say, end of array– but how can I do that? What values should I put here? Yeah DAVID MALAN: The string length name? DAVID MALAN: Yeah, I could do strlen of name, well, not of name– AUDIENCE: Of the initials DAVID MALAN: The initials, but now, you kind of got me in a circular argument, because I’m trying to– it’s kind of a catch-22 now I am trying to store a backslash n at the end of the string But recall from last time, the way strlen knows where the end of the string is, is by putting the backslash 0 So, it’s not there yet So we can’t use strlen But, we already have, I think, the solution– AUDIENCE: Can’t you just put initials four? [INAUDIBLE] DAVID MALAN: OK So, we could absolutely do that, or almost that It’s not quite four One tweak here, yeah? AUDIENCE: [INAUDIBLE] DAVID MALAN: In back, yeah? AUDIENCE: [INAUDIBLE] DAVID MALAN: OK, good So, actually– so, counter– is, yeah Spoiler, counter is going to be the answer But let me just fix this one bug here Four was the right intuition, but remember, if you have four characters possible, it’s 0, 1, 2, 3, is the very last one So, we needed to fix that to 3 But even more general would be to put counter, because the value of counter is literally the length of the string we just read into the initials And so if we want to terminate that string, we already know how many characters we’ve counted up And in fact, it would technically be wrong to just blindly put backslash zero only at the very end of these four characters Why? In what situation would that be– logic be incorrect? Yeah? AUDIENCE: If someone has more than three initials DAVID MALAN: If they have more than three initials, we really have a problem, because we don’t have space for anything beyond three actual letters and a null terminator And there’s another problem, potentially Yeah? AUDIENCE: If they don’t have a middle name? DAVID MALAN: Yeah, if they don’t have a middle name, there’s going to be, only maybe two letters, first name and last name And so, you’re putting the backslash zero at the end of your array, which is good

actually sum to or multiply out to And so it turns out that that summation can actually be expressed more succinctly as n times n minus 1, all divided by 2 That is the same thing, mathematically, as the long series that I had a dot-dot-dot there for So if I multiply this out, just using some algebra, that’s like n squared minus n, divided by 2 And then if I kind of multiply that out, that’s n squared, divided by 2, minus n over 2 So if I wanted to be really precise, this is the running time of bubble sort It takes this many steps to sort n people Why? Because I literally just counted the number of comparisons I made That’s how many comparisons it takes to do bubble sort But honestly, this is really getting tedious, and my eyes are already starting to glaze over I don’t want to remember these algebraic formulas here So let’s actually try an example, just to get a sense of how slow or how fast this is Suppose that n were a million So not eight, but a million people, or a million numbers How slow, or fast, is bubble sort going to be? Well, if we plug in a million, that’s like saying n is a million So that’s a million squared, divided by 2, minus a million divided by 2 Because that’s what it all summed up to be So if I do this out, it’s a really big number 500 billion minus 500,000 And in any other context, 500,000 is a pretty darn big number But not so much when you subtract it from 500 billion, because you still get 499,999,500,000 after subtracting those off Which is to say, of those two terms, the one on the left versus the one on the right, which is the bigger one? The more dominating factor in the mathematical expression? It’s the one on the left, right? That’s the one that’s massively bigger And so more generally, n squared divided by 2 feels like a bigger result than n divided by 2 alone And we’ve seen it by proof– by example, which is not a proof, but it at least gives us a feel for the size of the program, or the number of comparisons we’re actually making So you know what, ugh– if that is the case, if the dominant factor– the one on the left, in our case; the one with the square, specifically– is just so much more influential on the number of comparisons we’re going to make, then let’s just wave our hands at the lower-ordered terms, and divide it by 2, and anything like that, and just say, ugh, this algorithm feels like n squared I’m going to throw away the denominator, I’m going to throw away the thing I’m subtracting off, I’m going to throw away anything that is not the dominating factor, which is the term that contributes the most to the total number of steps incurred And indeed, this is what a computer scientist would describe, generally, as the running time of this algorithm It is on the order of n squared It’s not n squared, but it’s on the order of n squared, as we’ve seen It’s pretty darn close, and it’s good enough for a conversation with another reasonable person who wants to debate whether his or her algorithm is maybe better or worse than yours So, this would be called big O notation Big O is used to refer to an upper bound on an algorithm’s running time Upper bound meaning, we’ll consider, for our purposes, in the worst case, how much time might this algorithm take? Well, it’s going to take on the order of n squared steps Because if the list of numbers is unsorted initially, we’ve got to do a lot of work to actually sort it There’s other terms that we could put in those parentheses Some algorithms are not on the order of n squared Some algorithms are actually order of n log n; some algorithms are on the order of n itself, or log n, or even 1, where 1 refers to constant time And in fact, the ones I’ve highlighted here, we’ve actually seen examples along the way of all of these so far For instance, what algorithm have we seen that has a running time on the order of n? n steps? AUDIENCE: Linear search DAVID MALAN: Linear search If we were to think back, even to today, to linear search– or from the first lecture, when I was just looking for Mike, really slowly, one phone book page at a time, that’s a linear algorithm If there’s n pages, or n humans, it might take me on the order of n steps, because Mike Smith– S is toward the end of the alphabet, so he might be way over there, or way toward the end of the phone book, or, God forbid, his name starts with a Z, then I’m really going to have to go all the way into the phone book And so that’s on the order of n steps So, n here would be linear We’ve also seen another algorithm, here in yellow– big O of log n Saw it just a moment ago Which of our algorithms was on the order of log n running time? Yeah, so binary search Divide and conquer We didn’t call it– we didn’t describe it this formulaically in the first lecture, but that’s how you would describe the running time Not just with a pretty picture, but just with an expression like this, that all humans– at least computer scientists– can agree upon And constant time The funny thing here is, because we’re throwing away terms that don’t really matter, O of 1 does not mean an algorithm that takes one step only That would be a very limited number of options for your algorithms But it does mean, symbolically, a constant number of steps A constant number of steps So, what’s something you might do that takes a constant number of steps, in an algorithm? Maybe in, like, the first lecture, we had the silly peanut butter

numbers are bubbling up to the top, to the right, just as the number 8 did, when we did it on paper So, this is bubble sort And we could watch this for quite some time, and in some sense, it’s kind of mesmerizing But in another sense, it’s pretty underwhelming, because at the end of the day, all you’re going to get is a bunch of bars, sorted, from short bars to big bars But perhaps the takeaway is that I’d kind of have to stall here for a decent amount of time, even though we’re running this at the fastest speed, because it’s only fixing, at best, one number at a time And maybe some others are improving, but we’re only moving all the way to the end one number at a time And we have to then go back, and go back, and go back, and do more work It’s going to be very ungratifying to abort it, but let’s go back to random And now, if we choose, for instance, selection sort, you’ll see that the algorithm works a little differently Let me slow it down And what it’s doing now, which is a little less obvious, is it’s looking through the list for the next smallest element, and it’s going to put it at the beginning of the list All the way at the left So, it’s looking, and looking, and looking, and it leaves highlighted in red the most recently discovered smallest element And then as soon as it gets to the end of the list, it’s going to move that smallest element all the way to the left So that we now, kind of like the opposite of bubble sort, have all of the smallest elements to the left Though, this is arbitrary We could bubble up the small elements by just reversing the order of our operations; we could sort from biggest to smallest– that is irrelevant It’s just by human convention we tend to sort from smallest to biggest, at least in examples like this And we can speed this up, but it doesn’t quite have quite the same comparison effect, because all you’re doing is a swoop through the list looking for the smallest, looking for the smallest, looking for the smallest And so, this way, it’s going to build up from short to tall Let me go ahead and do it one more time, this time with insertion sort, and slow it down And so, what we’re doing here is the following We identify the next element, and then we go and insert it into the place it belongs in the “sorted half” of the list So, recall that I generally describe stuff on the left as being sorted, stuff on the right as being unsorted, and the implication of that is that even though these numbers here on the left are indeed sorted, when I encounter a new number, out in the unsorted area, I might have to move some things around and shuffle things around And unlike the cheat I was doing here in person– when I grabbed that music stand before and just kind of moved it over here– that’s not really legitimate Right? This is garbage value land Like, I should not have had access to this memory And so what we did with our actual eight humans was more legitimate The fact that our volunteers did the physical labor of moving those numbers around? That was the low-level work that the computer has to do, too And you see it here all the more, either at this slow speed or the faster speed It’s being inserted into the appropriate location So, case in point, this tiny little element? We have to do a huge amount of work to find its location, until finally, we’ve found it, and now we do the same thing So, all of these have some pluses and some minuses But it turns out, with merge sort, we can do even better An algorithm that goes by the name of merge sort But to do better, we need to have a new ingredient, or at least more formally defined, that we’ve kind of sort of leverage before, but not by name And to do this, I’m going actually take out a little bit of code, in CS50 IDE, a program called sigma-0.c And we’ll see the interconnection in just a moment So in this program, notice the following We have a main function, whose purpose in life is to get a positive integer from the user, and to pester him or her, again and again and again, until they cooperate and provide a positive integer That’s what the do-while loop is often useful for And then, what do we do with it? We simply pass that value, n, that the human typed in, via get int, to a function called sigma And sigma is like the Greek character, or the capital E-looking character, that generally means, in math, like, sum a bunch of numbers Add a bunch of numbers together So, this is essentially a function called sigma, whose purpose in life is to sum all of the numbers from 0 to n Or, equivalently, from 1 to n So, 1 plus 2 plus 3 plus 4 plus, dot-dot-dot, n, whatever n happens to be And then, via printf, we’re just printing it out So, let me just run this program to make super clear what’s going on And I can do this by doing, of course, in my source three directory for today, make sigma 0, enter, dot slash sigma 0, positive integer, I will do 2 So by that definition, it should sum 0 plus 1 plus 2, so 1 plus 2– that should be 3 So I should see 3 And indeed, I see 3 Let’s do one more, if I add in three numbers So, this should be 1 plus 2 plus 3– so, that’s 1– that’s 6, in total And so forth And they get pretty big pretty quickly If I do 50, then we start to get into the thousands So, that’s all it’s doing And how is it doing this? Well, we could implement this in a whole bunch of ways, but if we leverage some of our sort of techniques thus far, we might do it using a for loop That’s kind of been one of the most common tools in our toolkit

So, the first three things for me to do to sort this list is to sort the left half, then sort the right half, then to merge the sorted halves OK, so let’s see how we get there So here’s the list, here is the left half, and I need to sort the left half, apparently How do I do that? Well, how do you sort a list of four elements? AUDIENCE: Break it up again? DAVID MALAN: Break it up again Sort the left half, then its right half, then merge those two halves together So let me do that I’m going to draw a box around only the elements we’re thinking about at the moment So, let me look at the left half OK, now I need to sort this list How do I sort a list of size 2? It’s actually 2, it’s not less than 2 So I have to do some work So, how do you sort a list of size 2? It’s a little strange to say it, but– sort the left half, then sort the right half, then merge the two And at this point in the story, you may very well be lost, because we literally just keep saying the same thing, and not actually doing any work But think of it like you’re buffering these instructions Like, I’ve said to sort the left half, then the right half, but you focused on just the left half for now But unfortunately, you got a little distracted, because now to sort the left half, you have to sort the left half, so you have to do a little more work So if you just kind of let this mental baggage build up, we have to remember to go back through it But we’ve not actually done the real work yet We’re about to now Because now that you’ve told me, given a list of size 2, sort the left half, here’s where we bottom out with that base case and actually start to make some progress So here’s 4 and 2, a list of size 2 Let’s sort the left half How do you sort a list of size 1? You don’t, right? Because n is 1; 1, of course, is less than 2, and what was the one instruction that we had at the top of this function merge sort? Just return Like, do nothing So, OK, everyone I have now sorted the number 4 for you Like, it’s true, it’s kind of a foolish statement, but the magic must therefore come when we combine the results So, let’s see where the story goes I’ve sorted the left half– done Return Now, what was I supposed to do next? Now I have to sort the right half of that list of size 2 OK, done What’s the third step at this point in the story? Merge them So I’m now looking at a list of size 2 again, each of whose halves is sorted– according to the crazy logic we’re using here– but now, something interesting happens I have on the left the number 4, I have on the right the number 2, and each of these lists is of size 1 And if you vary, in your mind’s eye, or just visually, with my fingers, consider, like, your left hand pointing at the first list, your right hand pointing at the second list, the process of merging numbers is just comparing what your fingers are pointing at and deciding which one comes first Obviously 2 is going to come first, so in a moment, we’ll see that 2 should move over here, and then there’s nothing left for my right hand It’s done So, 4 is obviously going to go here And that process of merging 2 followed by 4 is what we mean by merging It’s pretty much what I was doing with insertion sort, but here we’re just doing it with individual elements at a time, kind of weaving things together, or zipping things together, like with a zipper, if you think of it that Way So, now, let me grab 2 and put it here Let me grab 4 and put it here OK So I sorted left half, I sorted right half, I merged them– how do we unwind the story? Where did we leave off? AUDIENCE: Sort the right half DAVID MALAN: Now we have to sort the right half that was, like, a minute ago in the story– which, just to highlight it now, is the 7 and 5 So now I have to do the same thing I’m sorting a list, of size 2, that happens to be on the right of the left So now, I sort the left half, done Sort the right half, done I now have to merge the two together So now my hands have to do some work, but I’ll just do it from over here 5 goes down, then 7 goes down And at this point in the story, we have sorted the left half of the left half, and the right half of the left half So, what point in the story are we at now? Right We’re– now we have– well, we did the right half just now We now have to merge the two halves together And, frankly, if you do this at home, if you want to kind of retrace your steps, literally just write down a to-do list, like, from top to bottom on the sheet of paper And then as you do something, cross it off, and go back to the previous thing in the list, you would actually see, or feel, even more what it was, that mental baggage you were accumulating that you need to attend to But now I have two lists of size 2, so let’s do the finger thing again here So, I start pointing at the left list, start pointing at the right list The first number to merge in is, presumably, going to be 2 Then what comes after that? I’m going to update my left finger, so now 1– my left hand’s pointing at the 4, at this point; my right hand, still pointing at the 5, so which comes next? 4 There’s no more work for my left hand, so it’s probably going to be pretty trivial– 5 and 7 But I do need to do the merging It looks merged already, but we have to do it And I’m going to do it in some new space, just as before So, 2 and 4 and 5 and 7 And now you can really see it for the first time The left half of the original list is finally sorted Unfortunately, like three minutes ago is when we started the story And now we need to unwind, in our mind, to go back to the original right half

So if you think about it now, even though I’ve said a lot of words, this is technically the second step in our algorithm Or at least the first invocation thereof All right, so we’ll do it a little faster, but same idea Sort the left half How do I do that? Sort the left half, then the right half, which are stupidly easy and dumb, but now I have to merge 6 and 8 So, merging in this case didn’t have much effect, but it needed to be done to be sure Next, let’s sort the right half of the right half Now I’m going to sort the left, sort the right Now the key step is merging And now we’re doing some actual work And now we really have some work to be done– now we have to sort the left half and the right half of the original right half So it’s 1, then 3, then 6, then 8 Now we’re finally, almost at the end Now what do we do with these? Now we have two halves, the original left and the original right, and you can think of the fingers as doing the work again 1 is going to go here, 2 is going to go here, 3 is going to go here, then 4– and I constantly compare where my fingers are pointing, but my fingers are constantly moving from left to right As soon as I deal with a number, it advances to the next number in the list So it’s obviously going to be, now, 1, 2, 3, 4, 5, 6 But notice, if you imagine my fingers doing this work, they’re constantly moving toward the right, to the end of the list So, as soon as my fingers hit the ends of those lists, I must be done merging And voila We’ve now sorted the elements It’s a huge number of words, and it would be a nightmare to kind of do it with humans, because there’s just so much going on, and you have to remember, or buffer, so many of those steps But in the end, we’ve done something that is kind of captured even by this picture So it turns out that merge sort, even though it sounds like a long story, is fundamentally faster, and it’s fundamentally faster because we’re dividing the problem in half, as we have been doing with binary search, in the phone book example even days ago So if we look on the screen, you can kind of see the remnants of work that we’ve done Like, how many times did we move the elements, from one row to another? They started up here, then they eventually made their way here, and then here, and then here So that’s one, two, three movements of the letters, or of the numbers, in memory, if you will So if you imagine each of these rows as just a different chunk of memory and RAM, I’m just moving things around in memory So, three is just a number But it turns out, and if we did more general cases of this, turns out that log base 2 of n, where n is 8– 8 is the number of elements we started with– log base 2 of 8 is 3 And so indeed– and if you’ll take on faith for now, so that we don’t have to go through an even bigger example, to show it even more– the number of times we move the numbers is going to equal, turns out, log base 2 of n Which, in this case, happens to be 3 And so that, then, invites the question– on each of the rows, every time you move these numbers into a new location in memory, how many times are you touching that number while it’s in that position? Or, how many times, equivalently, are you looking at it, to do something about it? What do I mean by this? Well, the movement from top to bottom was happening anytime we did the merging Right? We would move the numbers from here to here But as soon as we did that, we had to do some work, with the left pointer and right pointer I needed to then merge those together And I emphasized earlier that anytime I’m comparing numbers, my left hand and right hand are constantly advancing from left and right I never double back Much like I constantly was doubling back with bubble sort, insertion sort, selection sort– there was so much damn comparison going on, it felt like a lot of work, and it physically was But here, you know, merging, I’m moving things around, but my hands are constantly moving forward, looking at, on each row, n numbers total My left hand or right hand pointed at each of the numbers once Never doubled back So, it was never n plus 1, or 2 n, it was just n So, we have log n movements of the numbers, in memory And every time we do that, we merge them from left to right, effectively touching each number once So we’re doing n things log n times And so, that would be mathematically equal to n log n So, again, even if you’re not super comfy with logarithms, you do know, from our picture, with the straight lines and the curved line, that which is smaller? Log of n, or n, generally speaking? AUDIENCE: Log of n DAVID MALAN: Like, log of n is smaller, right? That’s why the green line was lower, and it was also curved It was below the linear line n So, generally speaking, the bigger n gets, the more slowly log n grows And again, if you just take on faith that this is a mathematical expression that communicates the time required to do something, it’s less So, which, therefore, is smaller? N squared, which of course is n times n? Or n log n? AUDIENCE: N log n

if you actually want to see how those map But what we thought we would do, in our remaining time today, is tee up one of the next algorithmic challenges It turns out that there are wonderful opportunities in computer science to intersect with other fields– among them the arts, and very specifically, music And it turns out that music, whether you’re an audiophile or even a musical theoretician, there are relationships among the sounds that we hear and the rate at which we hear those notes Which is to say, they follow patterns And these patterns can be produced by computers, they can be generated by computers, and what we’ll do, ultimately, in problem set three, in fact, is introduce you to a bit of the musical world, whether you have some prior experience or not And Brian, if you wouldn’t mind coming up just to assist with this teaser Here are just a few keys from a keyboard, and here are 88 keys from an actual keyboard And Brian will help us, in just a moment, with some of these definitions But you’ll see here that there are eight keys, or one, two, three, four, five, six, seven white keys and five black keys on the board And it turns out that mankind– at least, in Western music, years ago– decided to standardize on how we describe these keys And we assigned letters to them And you might have heard of middle C, even if you’ve never played a piano before, and you might think of that as being the leftmost key there And then it’s D, E, F, G, and then A, B. And of course, on a real piano, there’s keys to the left, and there’s keys to the right Do you want to play what C might sound like here? [PIANO PLAYS] So, that’s C. And then, if you want to– very well done [APPLAUSE] Do you want to go all the way up through the scale to B? [PIANO PLAYS] That’s kind of unresolved, too, because what should have come next– [PIANO PLAYS] That would be another C. And so what Brian’s played for us is a full octave, now, referring to eight So, C to C inclusive, in this case And those of us who are kind of are familiar with music, or like listening to certain music, you’ll notice that certain things sound good And there’s actually mathematical and formulaic, or algorithmic, reasons that some of these sounds sound actually good But what about these black keys? They actually can be defined in a couple of different ways And if you’ve ever heard of flats, or sharps– Brian, do you want to explain what the relationship now is among the white keys and the black keys, and how they sound different? BRIAN: Yeah, sure So, a bit of terminology first A semi-tone is just the distance from one note to the note immediately after that, both white and black notes included And all it means for something to be sharp, represented by the hashtag or pound sign up there, is take a note and move it up by one semi-tone So, if we start with C, and make that note sharp, to C sharp, we move one semi-tone to the note immediately after it, which is that black note in between C and D. So, that’s C sharp And likewise, if we add E sharp, that is one semi-tone, or the note immediately after, E, which in this case, is the same thing as F. So, F and E sharp are the same note And in the meantime, flat is just the opposite of that If sharp means move up one semi-tone, flat means move down one semi-tone So if I have E, E flat is one semi-tone moving left on the piano keyboard DAVID MALAN: And so even though a typical piano keyboard wouldn’t be labeled as such, it does follow a pattern, and it does repeat, to the left and to the right as well And so as you learn to play piano, you learn what these notes sound like, you learn where these keys are, and you also learn, ultimately, how to read music, which might look like this This is a familiar song, now officially in the public domain And you’ll see here that there are these little shapes called notes, or little circles, that happen to be on specific lines And it turns out that if a note is on one line, it might represent the note A; if it’s on a different line, higher above or down below, it might represent B or C or D or E or F or G And if there is a sharp symbol, or a flat symbol, in front of it, that might shift it ever so slightly, so that you’re actually touching, in many cases, one of the black keys as well Which is to say that once you have the vocabulary, and you know what the alphabet is to which you have access, can you start to write it out, much like we write computer programs But this is what a musician would actually see And just to give us maybe a teaser of what you can actually do when you take into account the different sounds of notes, and the different pace at which you play notes, can you give us a little something more than just a scale? BRIAN: Sure [PIANO PLAYS] [APPLAUSE] DAVID MALAN: So, if you’re a little worried what we’re getting into, not only computer science and programming, but now music– I am absolutely among the least comfortable with this, and this is why Brian has kindly joined us here today But it’ll be fun, we hope, ultimately, to explore these relationships, and also the intersection of one field with another And to now tie these topics together, we thought we’d end by looking at a short visualization here, about a minute’s worth of computer-generated sounds, that

give you not just a visual feel of some of the algorithms and others that we’ve looked at today, but also associate sounds with the operations of moving things, swapping things, and ultimately touching bigger and smaller numbers digitally So, here we have, up first, insertion sort [COMPUTER SOUNDS] Again, it’s inserting into the right place the number This, now, is bubble sort And again, you can both see, and now kind of feel, all of the swaps that it’s doing We will get the satisfaction this time This, now, is selection sort, whereby you go through the list selecting the next smallest element, and plop it in its place And the bars are getting higher and higher, just like the notes, or the frequencies This, now, is merge sort And notice the halves that are developing And this is by far the most gratifying sound, at the end of this one This is gnome sort, which we didn’t look at, but very distinctly has a different shape, too It’s not quite as ordered as the others And that, then, are algorithms And Brian, play us out for today Otherwise, we will see you next week