Transcript

the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu all right everyone let's get started so all right good afternoon so this is the third lecture of 61 and 600 as always please download slides and code to follow along so quick recap of what we did last time last time we talked about uh strings as a new object type as sequences of characters and then we introduced um uh two new Concepts that allowed us to write slightly more complicated programs so we introduced branching with these keywords if L if else and branching allowed us to write programs that uh us as programmers could could introduce decisions into our programs and then we introduced two different kinds of Loops y loops and for loops and those also added a little bit of complexity to our programs today we're going to talk a little bit more about strings so we're going to see a couple more operations that you can do on strings and string objects and then we're going to talk about three different algorithms a guess and check algorithm an approximate solution algorithm and a bisection method algorithm okay so let's Dive Right In we'll talk a little bit about strings first so strings we thought of them as sequences of characters right K sensitive as we saw in in Pre in programs we wrote last lecture and strings are objects and we can do all of these uh operations on on string objects like test if they're equal less than greater than and so on turns out we can do more than just concatenate two strings together or do these little tests on them so we're going to start introducing the the idea of of a function or a procedure and we're going to see more about functions and how you can write your own functions next lecture but for today you can think of a function as sort of a procedure that does something for you okay someone already wrote this so the first one we're going to look at is a pretty popular function and when applied on a string this function called Len will tell you the length of a string so that's going to tell you how many characters are in the string and characters are going to be letters digits special characters spaces and so on so it's just going to count how many letter how many how many characters are in their string so if I have the string s is equal to ABC remember a string is in quotation marks then if I do this um this if if I write this expression Len s here since it's an expression it has a value so it evaluates to a certain value and by definition it's going to tell me what the length of the string is which is three characters long okay another thing that we can do on strings is since there a sequence of characters I might want to get what character is at a certain position so we do this using this uh fancy word called indexing but pretty much what indexing into a string means is you're going to tell python I want to know the character at this certain position or at this certain index inside my string okay so once again let's use this string s is equal to ABC and let's index into it so in computer science we start from zero counting by convention notice we had a problem set zero in this class Python's no different so python in Python you start indexing at position zero or you start indexing at zero so the first character in your string we say is at position zero so or at index zero the next character in the string is at index one and the next character in the string is at index two in Python turns out you can also use negative numbers to index and if you use if you index into the string with negative one for example that means that you want the last character in the string so the last character in your string is always going to be at position negative one second to last character is at -2 third to last character is atg -3 and so on and so on okay so the way you index into a string is with these square brackets here and this is the notation so if I want the character at position zero or at index zero I say s which is the string I want to index into and then inside the square brackets I say what index I want so s at index zero is going to be the value a s at index one is going to be the value B and so on and so on and we can also do negative uh negative indexing as well if you do try I added this in here if you do try to index into a string beyond the limits of the string and we can even try this out just to show you that it's not the end of the world if we do that if we have S is equal to ABC and we have S at position 20 for example obviously my string is only length three so what's at position 20 I get an error right I call this angry text here in Python but really the most relevant thing to note is these last couple of lines here this tells you what line is problematic so s at position 20 has an issue and this last line here tells me what actual error I have so it's an index error which means I'm trying to index too far into the string because it's it only has three characters okay so it's nice to be able to get a single character out of my string but sometimes I might want to get a substring so I want to start at you know the first character and go halfway into the string or I want to take the a few a few characters in between or I want to skip every other letter or something like that in my string so if I want to do this slightly more complicated um interaction with strings we call that slicing slicing into a string okay and this notation here should seem a little bit familiar because we saw it last lecture when we did it with range okay we had a start stop and a step the notation was a little bit different because in range we had open close parentheses and commas in between but except for that this sort of works the same the start is the index starting from zero from where you want to slice into the string the stop is the stop index so you're going to go up until stop minus one and take that index and then the step is every house how many uh letters you wish to take so this is the full notation here but sometimes you can not give it a third um a third sort of number in here so if you only give it two numbers then that to python that represents just the start and the stop and by default step is going to be one and there's a lot of other things you can do with um with strings you can just you can omit numbers and just leave colons and python just by the way that uh by by definition the way that whoever wrote slicing had decided if you omit numbers then it's going to be equivalent to these things here so we slice using square brackets just like indexing except now that we can get now we can give it two numbers okay so with this string s if we slice into the if we slice into the string s we start from index three and go up up until index six so if we have a b c d e f g h right this is position zero 1 2 3 four five six seven and you just you just count so s starting from three and going till six is going to start here three right so it's going to come up with sorry D and then we're going to take e and then we're going to take F and since we're going until stop minus one we're not going to take G right because this is position six and we're going until 6 minus one okay the next one here 362 is going every other one right so we start at three and then we skip every other one so we go D but not e and then F and then stop if you do s and then nothing nothing inside except colons notice that you're going to have s and then nothing and then colon nothing colon nothing so nothing for start nothing for stop nothing for step and that's just going to evaluate to the string itself it's the same as zero to the length s going every step this one might actually be useful it reverses the string automatically for you so with this one little line here you can get the inverse of your string and that's equivalent to that so the minus one represents starting from the end and going back every letter and then this one's a little bit more more complicated but also not too bad okay okay okay so as we're doing with the as we're as we're doing these string slices again if you're unsure what something does just type it into spider and you know you might be surprised you might not be but it's a good way to check yourself to make sure you know uh you you're understanding what's happening okay one thing I want to mention and it's good to keep this in the back of your mind we're going to come back to this as we as we start talking about slightly more complicated object types but strings are immutable so just keep the word in the back of your mind as we go through this class and what I mean by this is that an actual string object once it's created cannot be modified okay this might not mean anything right now but let me just draw a little something let's say I have this string s is equal to hello remember in the first lecture we drew a diagram sort of like this this is my memory I have this object hello and this object hello is bound to this variable s right so now I can access the object hello using this variable s now you might think well since I can index into a string I might be able to you know just say something like s at position Z is equal to Y right and that'll just change the little H into a y and I'll have a new object well strings are immutable which means in Python you're not actually allowed to do this and it gives you an error if you do try to do that if you want the variable s to point to the string y l o you could just say s is equal to Yo or you could do string operations like this and this takes the Y and it concatenates it to the string s all of the elements starting from position one which is e l l o so this makes y e o now internally what happens when I when I write this line is python says okay I'm going to break my bond with this original object hello I'm going to bind my new my string variable s to the new object yellow and this other old object still is in memory somewhere right but it's an entirely different object that I've created here again might not mean anything right now but just keep this in the back of your mind strings are immutable okay all right so the next thing I want to talk about is a little bit of recap of on for loops and we're going to see how we can apply for Loops very easily to write very nice readable code um when dealing with strings okay so remember that for Loops had a loop variable right my Loop variable being this VAR here in this particular case it could be anything you want and this variable in this particular case iterates iterates over this sequence sequence of numbers 0 1 2 3 4 so the very first time through the loop VAR has a value of zero it does the expressions in the loop soon as they're done VAR takes the value one it does all the expressions in the loop and then VAR takes the value two and it does that all the way up until 012 and the last time it goes around is with VAR is equal to three and remember we said that we can customize our range in order to start from a custom value to end at different value and to skip certain numbers so so far we've only been using four Loops over a sequence of numbers but actually for Loops are a lot more powerful than that you can use them to iterate over any sequence of of values not just numbers but also strings okay so here are two pieces of code this one and this one here okay these two pieces of code both do the exact same thing okay to me possibly to you this one looks a lot more readable than this one right just at a first glance if I were to read this one just using the keywords and and and and uh variables here it sound it would sound like broken English right but you you could decipher what I'm trying to say for a Char in a string s if the Char is equal to I or a Char is equal to U print there is an i or a u okay sounds weird but you could probably tell what I was trying to do here whereas up here it's it's a little more complicated to tell what I'm doing right you have to sort of think about it a little bit for some index in this range of numbers zero through the length of the of the string s if s at position index is an i or s at position index is a u print there's an i or a u okay both of these codes just go through the string s and if it encounters a letter that's an i or a u it's just going to print out this string here but this bottom one is a lot more pythonic it's an actual word created by the python community and it just looks pretty right like you can you can tell what it what this code's supposed to do whereas this one is a little bit harder to decipher so that's sort of an illustration of a for Loop over a sequence of characters right so Char is going to be a loop variable still and the loop variable instead of getting instead of iterating over a set of numbers it's going to iterate over every character in s directly and Char is going to be a spe a character right it's going to be a a letter Okay so so here's a more complicated example I wrote this code oh a couple years ago and it was my attempt at creating a robot cheerleaders because I needed some motivation and um and then you I Googled last night robot cheerleaders and was not disappointed created this GIF looks pretty cool and it looks like they kind of stole my idea but that's fine so let's look at what this code's supposed to do I'm going to run it okay I'm going to run it and then we'll go through it okay so all right it prints out I will cheer for you enter a word you know what I like robots so I'll put in robots how enthusiastic am I about robots let's say six okay so what this is going to print is it's a cheerlead right give me an r r give me an o o give me a b b and so on and so on what does that spell robots and it's going to print it six times because I'm six out of 10 enthusiastic about robots Okay so that's pretty much what that code's supposed to do and you can write it using what we've learned so far now let's go through it a little bit and I'm going to show you just how how easy it is to convert this code um using a for Loop over characters right right now what it does is it asks the user for input so a word and a number and then it does this thing here right first it uses a while loop and second it uses indexing okay and the tip here that what tips you off that it's using indexing is right it's using the square bracket here into the word okay and obviously it's using a y Loop and it has to First create a a counter initialize it and then down here it's going to increment it inside the while loop if you remember um that's sort of what we need to do for while Loops so it's going to start at zero and it's just basically going to go through index I is equal to 0 1 2 3 4 which is going to go all the way to the end of the word whatever the user typed in in this case robots it's going to get the character at that position right word at position I is going to be a character this line here is just sort of for pretty uh for for the cheerleading to make sense it's just to take care of letters that make sense to to use un right so give me a give me unb so give me unb does not make sense right so that's just taking care of that and I'm using this in keyword to check whether the character so the character R for example in robots is inside unlet and unlet I've defined up here which is these are all the letters that make sense to put an un before the letter okay so give me an R for example here on the right okay and so if it makes sense to use un before the letter use that and otherwise use just an A and after I'm done I say what does that spell and then it's just a for Loop that goes times many times and prints out the word and the exclamation mark so um okay so this code might have been a little bit more intuitive if I rewrote it or if I had or orig Al wrot written it with a for Loop okay so this part here right the while loop and indexing and creating my original counter we can get rid of that and we can replace it with this for Char in word okay I'm originally using Char so I can use Char as my Loop variable again and simply I'm just going to iterate over the word itself so now instead of having this mess here I have one liner that says for every character in my word do all this stuff here so That Remains the Same and then I don't even need to increment a counter variable because I'm not using Y Loops anymore I'm just using a for Loop okay so the code becomes delete that for chart in word and then delete that and that does the exact same thing okay and it's a lot more readable right all right so this was our toolbox at the beginning of this course we are two and a half I guess lectures in these are the things we've added to it we know integers float floats booleans we know bit of string manipulation math operations we added recently these conditionals in branching right to write slightly more interesting programs and now we have loops for and while Loops to add interesting and more complicated programs okay so with these the second part of this lecture is going to be looking at three different algorithms okay that's the sort of computer science part of this of this class introduction to computer science and programming using python don't let the word algorithms scare you right they're they're not that complicated you just have to sort of think a little bit about them and and and you'll be able to get them okay so we're going to look at three algorithms all in the context of solving one problem which is finding the cube root first algorithm is guess and check then we're going to look at an approximation algorithm and then a bisection search so the first is the guess and check method okay you might have done this in math uh in high school the guest and check method is is also sometimes called exhaustive in numeration and you'll see why so given a problem let's say find the cube root of a number let's say you can guess a starting value for a solution the guess and check method works if you're able to check if your solution is correct so if your guess is originally zero you can say is Zer cubed equal to the cube the cube of whatever I'm trying to find the cube root of so if I'm trying to find the cube root of 8 is 0 cubed equal to 8 no right so the solution is not correct if it's not correct guess another value do it systematically until you find the solution or you've guessed all of the values Poss in you know all of the possible values you've exhausted all of your search space so here's very simple guess and check code that finds the cube root of a number so I'm trying to find the cube root of eight so my cube is eight I'm going to have a for Loop that says I'm going to start from zero and I'm going to go all the way up to so I'm going to start from zero and go all the way up to eight for every one of these numbers I'm going to say is my guest to the power of three equal to the Cube 8 and if it is I'm going to print out this this message okay pretty simple however this code is not very user friendly right if if the user wants to find the cube root of nine they're not going to get any output okay because we never print anything in the case of of the the the guess not being a perfect Cube or the cube not being a perfect Cube okay so we can modify the code a little bit to add two extra features okay the first is we're going to be able to deal with negative cubes which is kind of cool and the second is we're going to tell the user if the cube is not a perfect Cube hey this cube is not a perfect Cube so we're not going to silently just fail because then the user has some sort of feedback on their on their input so let's step through this code we have first of all a for Loop just like before and we're going to go through zero to eight in this case we're using the absolute value because we might want to find the the cube root of of negative numbers first thing we're doing is doing this check here instead of guessing if the C instead of uh guessing whether the guess to the power of three is equal to the cube we're going to check if it's greater or equal to and we're going to do that for the following reason so if we're if we're trying to find the cube root of eight for example versus a cube root of n this is eight and this is nine okay what is this code going to do it's going to first guess zero 0 cubed is not greater or equal to 8 1 cubed is not greater or equal to 8 2 cubed is greater or equal to 8 so here once we've guessed two we're going to break because we found a number that works and there's no need to keep looking right once we found the perfect the per the cubed root of this number eight there's no need to keep searching right the remainder 3 4 5 6 seven eight okay sort of the same idea when we're trying to find the cube root of nine we're going to start with 0o 0 to^ 3 is less than 9 1 to the^ 3 is less than 9 2 to the^ 3 is less than 9 when we get to 3 to the^ of three that's going to be greater than n so this code tells us once we've picked a number that's beyond the logical sort of cubes of the what's sorry once we've picked a number that's beyond the reasonable number of our cubed root of our cube the cube root of our Cube then we can we should stop because again it doesn't make sense to keep searching because if 3 to the power of three is already greater than nine four to the power of three is also going to be greater than nine and so on okay so once we break here we either have guess being two or guess being three depending on what Cube we're trying to find and if the guest to the power of three is not equal to the cube then obviously the cube was not a perfect Cube so that's this case here if we were looking at three at the cube root of N and otherwise this part here just looks at whether we should make it a positive or um or a negative Cube okay so if our original Cube was less than zero then obviously the cube root of a negative number is going to be a negative number and otherwise it's just our guess okay so that's the guess and check method slightly more feature program for guessing the cube root but that only tells us the cube root of perfect cubes and doesn't really give us any anything else any more information so sometimes you might want to say well I don't care that nine is not a perfect Cube just give me a close enough answer okay so that's where approximate Solutions come in so this is where we're good we're okay with having a good enough solution okay so in order to do that we're going to start with a guess and then increment that guess by some small value okay start from zero and start incrementing by 01 and just go upwards from there and at some point you might find uh a good enough solution in this program we're going to keep guessing as long as we're not close enough and close enough is going to be given by this Epsilon value in the program okay so as long as the guest cubed minus the cube so how far away are we from the actual answer is greater than some Epsilon keep guessing right because the solution's not good enough but once this is less than Epsilon then we've reached a good enough solution so two things to note with approximate Solutions right so you can get more accurate answers if your step size is really really small if you're incrementing by 01 you're going to get a really good approximate solution but your program will be a lot slower okay same sort of idea with Epsilon you can change Epsilon if you change Epsilon to be a bigger Epsilon right you're sacrificing accuracy but you're going to reach a solution a lot faster so here's the code for the approximate solution of a cube root might look intimidating but look almost half this code is just initializing variables okay so we're initializing this is the cube we want to find the cube root of we pick an Epsilon of this we start with a guess of zero we start with an increment of 01 and just for fun let's keep track of the number of guesses that it takes us to get to the answer this is similar to the guess and check from before if or it's not so this part is similar to The Guessing check from before so if so we're going to take the guest to the power of 3 minus the cube right so that's how far away are we from the actual answer and we're going to say if that's not good enough so if we're still greater or equal to the Epsilon then keep guessing so we're going to be stuck in this Loop where we keep guessing values until we've reached a guess that's good enough so until we're small we're less than Epsilon and the way we keep guessing is just with this line right here which says increment by guess by increment by guess by increment and increment being this really small value that make sense okay so I'm going to keep incrementing my guess by that small value before I go on I'm going to run the code and we're going to discover a small issue with it okay so with 27 we're going to run it perfect it took me 300 guesses but 2999999 is close to the cube root of 27 okay we can find the cube root of this guy here and it took me 20,000 guesses but I figured out that 200 9999 so 201 is close to the cube root of of that large number and then I should have done this this is going to be a giveaway you guys sorry then we're going to have let's say I want to try cube of 10,000 so 10,000 is not a perfect Cube so we can run the code and with 8120 601 I had already gotten an answer but with 10,000 I'm not getting an answer yet right so I'm I I'm thinking that there might be something wrong so I'm going to stop my code so I just hit contrl C because I feel like I've entered an infinite Loop and in fact I have so what ended up happening is this problem here so I'm going to draw something according to the code I'm going to start from zero and I'm going to increment right my guesses like that with every with every little increment I'm going to make a new guess I'm going to take that guess to the power of three I'm going to subtract the cube and I'm going to figure out if I'm less than Epsilon okay this is the Epsilon that I want to be in okay this little bit here so with every new guess I might be maybe so this is where I want to be right within this little boundary here with every new guess I might be here with the next guess over here I might be here when I make another guess I might be here so I'm getting close to being with an Epsilon but maybe with my next guess I'm going to hop over my Epsilon and have made too big of a guess okay so just because of the way the numbers right the numbers were chosen in this example just to illustrate this using an increment of 01 with finding the cube of 10,000 and Epsilon of 0.1 it turns out that as I'm doing all these calculations I'm going to skip over this perfect bound this perfect sort of Epsilon um uh difference so first I'm going to be too too small and then I'm going to be too large and once I've become too large or too far away from Epsilon the guesses I continue to make are just going to be even even farther away from Epsilon and I'm not going to going to get to my answer and that's why I've reached an infinite Loop in this code okay all I'm doing in this code is guessing whether is checking whether my guest Cube minus cube is less than Epsilon the only thing I need to do here is sort of add this little Clause here that says oh by the way also check that I'm less than Cube because this is just like we did in the very first program when I'm taking I'm checking you know 0 1 2 3 4 five 6 seven8 right when I'm trying to find the cube root of eight ah what cube root of eight right once I've reached eight I'm going to stop and it's the same thing here so I just added this little Clause that says well while I'm greater than equal to Epsilon and I'm still less than the actual Cube just keep searching but once I've reached the cube then stop searching and with 10,000 you can see that I failed to actually find so that's what I that's what this part here does it tells me that I've failed to find um the cube root with those particular parameters okay last thing we're going to look at is B section search and to illustrate this I'm going to need one volunteer uh and you're you're going to play a game with me in front of the whole class and there will be a prize ah there go the hands um in the blue shirt right there all right cool so the prize is going to be once again this I promise I don't have I don't have millions of these Google Glasses I also don't work for Google I just happen to get a couple okay so the game is this I'm gonna ask I'm gonna ask you to pick a number a whole number between zero and 100 okay and I'm gonna try to guess it and you need to make it hard for me and you make it so hard for me that I cannot guess it within 10 guesses okay and if you can do that if I cannot guess it within 10 guesses you get this okay so and I'm going to draw out what I do as we go along okay so do you have your number yes okay perfect um let me erase that actually I should kept that because I'll still use it okay there's the numbers 0 to 100 okay is your number 50 okay 50 was my guess so I've made one guess uh is is your number higher or lower than 50 higher okay is your number my next guess is going to be 75 and the guess and the reason I'm guessing 75 is because what's your name what's that Sophie Sophie said said 50 was too low so I immediately know that it cannot be any less than 50 so I've already eliminated half of the numbers right so my next guess is 75 is your number 75 okay lower is your number lower or higher higher is your okay so I'm since it's higher I'm eliminating this half here is your number between 75 and 100 oh boy you're putting me on the spot what's that 87 thank you 87 higher or lower lower lower okay so since it's lower I'm elimin eliminating that half is your number 81 higher or lower okay so she said lower so I'm eliminating that half um is your number 78 boy that's really hard 78 okay um higher or lower is your number 76 yay all right perfect 76 was the number so how many guesses have I made one two three four five six I made six guesses so I did get it under under 10 but you know what the game was rigged so you get so you get the prize anyway just because I break the game here you go thank you all right so notice in bisection search what I did was I eliminated half the search space right with every guess I said well she said it's higher or lower so I definitely cannot be in the other search space right if I was doing approximate solution or in this case guess and check I would be I would be asking um Sophie is your number zero 1 2 3 4 and so on right so with guess and check it would have taken me 76 guesses to get to the number whereas with with uh this bisection search that I just did it only took me six right Isn't that cool so that means that the larger the space actually is that I need to search the better it is to use bisection search this bisection search method okay so that's basically what I'm illustrating here so we have our original search space we're going to choose a guest halfway eliminate half of the guest then we're going to choose look in the remaining interval eliminate half the guesses and so on and so on okay so then this is the code for bisection search also looks intimidating but it's not so bad so we're initializing a bunch of stuff up here most important couple things we're initializing are first of all this high and this low boundaries Okay so with the guessing game the low boundary was zero and the high boundary was 100 right when we're looking at the cube root the low boundary is going to be zero right and the high boundary is going to be just my cube right because the cube because a guess to the power of three cannot be any greater than Cube and then just going to do the same procedure that I did the guessing game which is I'm going to make my guess be halfway in between so with this guessing game I had to sort of choose if if if there were three numbers if there were four numbers in between you know should I go higher or lower but when we're doing bisection bisection search here we don't care about that we're just going to do floating Point division because we want uh um we want decimal numbers okay so I have a low boundary and a high boundary and I've figured out my halfway point then I have this y Loop here y Loop is similar to the approximation method where as long as I'm not as long as I don't have a guess that's good enough so this depicted by this greater or equal to Epsilon as long as my guess is not good enough I'm going to keep guessing Okay that's what this y Loop is saying so if the guess to the^ 3 minus cube is not good enough keep guessing and the way I keep guessing is this part here says my guess was too low so if my guess was too low set the low boundary to be the guess right because I don't care about all of the other numbers that are much lower than me so set the low to be the guess that's what that Line's doing and otherwise my guess was too high that's what this else is doing so set the high to be the guess because I don't care about numbers any higher than my guess okay once I have these new boundaries I make another guess again halfway in between the new boundary points okay so essentially I'm just having my interval with every single guess okay and that's what the while loop is doing and then I print out the remaining part so notice the search space right originally being n we're having it with each guess so the first guess divides it by two second guess divides it by four and so on so by the time we get to the kith guess n / 2K right the Ki guess let's say that's the actual answer we're interested in there's only one value in that little interval and that's the answer we want so 2 to the K is equal to n and then how many guesses did we make K is equal to log base 2 of n okay so when we were playing the guessing game of 100 right my n was 100 log base 2 of 100 is six point something I think so in fact I could have said if I don't guess it within seven guesses um uh you would have won as well so that's why the game was riged right so the guess notice it converges on the order of log base n instead of just linearly in terms of n so that's why it's so powerful one last thing I want to mention is the code I showed only works for positive cubes and that's because of the following so I have this 0 and one let's say I'm trying to find the cube root of 0.5 when I first set my initial boundaries my low is this one and my high is this one right but what's the cube root of 0.5 is it within this boundary or is it outside this boundary I heard outside it's like seven something so it's out here so with this particular code I'm going to be having my interval in between those numbers but I'll never get to an answer because the actual cube root of 0.5 or numbers less than one is going to be outside that boundary so there's a small change you can make to the program which will fix that and that's in the code I didn't put it in but it's a very small change small if statement so that's it all right thank you

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

3. String Manipulation, Guess and Check, Approximations, Bisection