3. String Manipulation, Guess and Check, Approximations, Bisection
Vložit
- čas přidán 26. 06. 2024
- MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
View the complete course: ocw.mit.edu/6-0001F16
Instructor: Dr. Ana Bell
In this lecture, Dr. Bell discusses string manipulation, guess-and-check algorithms, approximate solution methods, and bisection search.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
0:01:54 Strings
0:03:32 Strings indexing
0:05:34 (Coding)
0:06:49 Strings slicing
0:08:37 Strings slicing example
0:10:05 Strings slice inversly
0:11:18 Strings was fixed in memory
0:13:20 For loops recap
0:16:31 Coding example : robot cheer leaders
0:18:00 Coding example : robot cheer leaders(Coding)
0:20:36 Coding example : robot cheer leaders
0:22:00 Coding example : robot cheer leaders
0:23:37 Guess and check cube root1.0
0:26:00 Guess and check cube root2.0
0:28:30 Linear Search for cube root approximation
0:31:22 Linear Search for cube root approximation examples
0:32:53 Linear Search for cube root approximation of 10000
0:34:33 Linear Search preventing going to far
0:36:48 Bisection Search
0:38:00 Bisection Search @3rd iteration
0:39:52 Bisection Search summary
0:42:47 O(n) (Complexity)
The true hero here
Thanks a lot, it is handy.
I rlly appreciate Gigachads like you who make our life easy
tnx
Dr. Bell really does deserve an applause. Nice to see that the students actually did that in the end of the lecture.
An amazing lecture with such articulate explanation of concepts. Thank to MIT OCW and also to the course staff!
👍👍👍
I love Dr. Bell's enthusiasm for this. Makes learning it so much more fun!
Cannot exaggerate how helpful this content is. Thank you MIT OCW.
I know hindsight is 20/20, but I wish I would’ve watched these videos (and the Walter Lewis videos) when I was in high school. I would’ve been so much more motivated to work hard and try to get into MIT.
Edit: Walter Lewin
You live a sad life of regret.
This series of lectures and this lecturer are both so insightful that I often have to take long breaks between views because of the amount of complex and hidden/misunderstood information they make so accessible can make life overwhelmingly easy to understand
Thank you Dr. Ana Bell, MIT and everyone involved with all of this! You are all amazing!
(no angry text here :)
Im watching these lectures and practicing the course works from the website (the assignments and problem sets, also playing around with each thing I've learned). I've learned more in 3 days watching these than I have with a month of watching how-to tutorials (which is not surprising at all, just what I was trying before) and I am so glad I found this. I've made a very simple calculator that can add 2 numbers together that the user inputs! Very simple, but it's a victory to me! I'm starting college soon and majoring in computer science, so I can't wait to look back and see how far I've come. Really thanks to these kind people and this great teacher, I am understanding concepts that were constantly foreign to me no matter how much I tried to understand on my own. Although I haven't attended a class, I'll remember Dr. Bell as one of my favorite teachers because I have learned so much.
It was very useful. HUGE THANKS TO MIT.
cube = float(input("Enter a no whose cube root is to be calculated: "))
epsilon = 0.01
num_guesses = 0
if cube > 1:
low = 0
high = cube
guess = (low + high)/2.0
while abs(guess**3 - cube) >= epsilon:
if guess**3 < cube:
low = guess
else:
high = guess
guess = (low + high)/2.0
num_guesses += 1
elif 0 < cube < 1:
low = cube
high = 1
guess = (low + high)/2.0
while abs(guess**3 - cube) >= epsilon:
if guess**3 < cube:
low = guess
else:
high = guess
guess = (low + high)/2.0
num_guesses += 1
elif -1 < cube < 0:
low = cube
high = 1
guess = (abs(low) + high)/2.0
while abs(guess**3 - abs(cube)) >= epsilon:
if guess**3 < abs(cube):
low = guess
else:
high = guess
guess = (low + high)/2.0
num_guesses += 1
else:
low = cube
high = 0
guess = (abs(low) + high)/2.0
while abs(guess**3 - abs(cube)) >= epsilon:
if guess**3 < abs(cube):
low = guess
else:
high = guess
guess = (low + high)/2.0
num_guesses += 1
print('num_guesses = ', num_guesses)
if cube < 0 :
guess = -guess
print(guess, "is close to the cube root of", cube)
I guess this covers all possible cases?
Thanks a bunch! I'm a MD trying to learn python. This helped a lot, couldn't really wrap my head around the class challenges.
appreciated.
I suppose it should be >=1, otherwise else: applies
Thank you for these videos MIT and Professor Bell, I've learned so much from watching these videos and this has accelerated the career change I'm beginning now at 27.
Much love,
-Sam :)
I'm 27 years old and me to
In Metrology, the Approximate solution or Guess and check is analogous to Linear search
and the bi-sectIon search that Dr. Bell used is called Binary search.
We use it comprehensively to find the levels and timing parameters of an integrated circuit.
Ana Bell you’re the best 🙏🏽
She is an amazing teacher! Explain it so clearly and fun. Thank you so much!
Hi guys. I'm going to thank the MIT team. Thank you, for these awsome courses.
college drop out learning python for free from MIT, who would have ever thought...
kuuz am here in disbelief too
Here!
Same here. I dropped out years into a CS degree ten years ago. Am learning it all from MIT now. Better lecturers than I ever had.
There also good python courses outside
Same here
first sorry about my miserable English.
All I want to say is thank you very very much
You gave me a new start and a new goal in my life with python.
Code at 35:33 does not work for negative cubes. Here some changes in order to let it work also for negative numbers. Hope it will be useful :).
___________________________________________________________________________________
cube = 27
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0
while abs(guess**3 - cube) >= epsilon and abs(guess**3) = epsilon:
print('Failed on cube root of', cube)
else:
print(guess, 'is close to the cube root of', cube)
#this works too 👍🏾
cube = float(input(" enter your preferred number: "))
guess = 0.0
epsilon = 0.1
increment = 0.01
if cube >= 1:
while abs(guess**3 - cube) >= epsilon:
guess += increment
print(guess, "is close to the cube root of", cube)
else:
while abs(guess**3 + cube) >= epsilon:
guess += increment
print(-guess, "is close to the cube root of", cube)
nice!
Wow! They clapped at the end. Can't remember ever being so much into the class that I end up clapping.
The final algorithm that she explained is actually called Successive Approximation which there is also circuits for that which is called Successive Approximation Register (SAR) Analog to Digital Converter (ADC). Looking at these algorithms being in both computer science and electronic engineering is so cool.
You get a little extra bang for your buck at MIT 💪🥳
Love it. Dr. Bell, I hope you're still at this: you do it *really* well, and as I've watched from the first lecture, you're losing (or taming?) what seems to be a little stage-fright. I've never lost mine, but I did tame it enough to teach by interactive lectures way back when. Good onya. :-)
One question: the "bisection" method seems just like (electronics engineering technology 35 years ago) what we called "successive approximation by halves"... and we did it with logic-gate constructs and not code... but is that the same idea?
Yes, it's the same idea. In fact, I just Googled it out of curiosity (electronics are not my area, though I'd like to get more into it) and several articles on successive approximation by halves make reference to binary search (another name for bisection search) explicitly.
This video literally answered all of my remaining questions
prof. Anna Bel your lectures are very helpful thanks
21:58 Start of Basic Algorithms
I absolutely love these courses! Learning so much! Both lecturers I've seen are outstanding, and much appreciation to everyone involved in this amazing gift to mankind! I do have one, small suggestion, though. It would be great to leave the camera on the slides for longer periods of time. In a classroom, as I'm taking notes, I am focused more on the slides and what the teacher is saying, than on how they look (even though these teachers are very pleasant to watch). Because there is so much video of the instructors, it leads to a lot of pausing on slides and interrupting their wonderful lectures. :(
Brother you can find the slide on the course website alongside with the code and most importantly there are some challenging assignments.....I highly recommend you to check those.
this was a good lecture. I hope I watch them all.
thnks alot prof Ana Bell ,,its very helpful for me
Thank you for these courses. I took programming 17 years ago and wanted to brush up and learn Python. Since that seems to be the go to language now. I learned on VB. I've written a couple programs in VB for my current employer to connect to, manipulate, and retrieve data from a database. Mainly to make my job easier. LOL... I thought I would try and learn to do it in a more current language. Granted I have to get through this 6.0001 course first so I can get to 6.0002 where I need to be for database programming.
I'm just hoping to learn something I didn't know. So far it's just refresher, which is fine. I already know pretty much everything being discussed. It's just slightly different syntax such as the double =, that's not a thing in VB. Or the single quote vs double quote. Yeah that's not a thing in VB either double quote only for strings.
I really love this course and had to donate! Between MIT OCW & Free Code Camp, I'm definitely learning a lot of valuable information! Thank you! You guys are absolutely amazing!
Yes definitely this is more informative
Amazing content. Thank you MIT.❤
13:21 loop variable that iterates over a collection, not a set?
Thanks for sharing knowledge in free
Actually Approximations were a headache for me which u guys solved.
Excellent videos!! Thanks MIT
thank you ,mit
akbar rauf and Dr Ana Bell
@@88bjjmichael f
What a helpful and interesting class!
Great lecture, thank you!
43:51 She meant to say it only works for cubes greater than or equal to 1
Great session! Thank you for contributing to the coding community.
13:00 On for loops
#pre 14:20
#14:39 It seems that you don't need to use the word range() when u are binding characters to the iteration variable
16:27 more complicated example of assigning characters to iteration variable
#pre 19:32 explanation of 'in' keyword
19:50
20:14
thanks a lot Dr. Ana Bell
lol. thank MIT. she's being paid to teach whilst being filmed. nothing glorious there. if anything, she stutters so much it feels like her mind keeps wandering off somewhere. Prof. Eric Grimson was way better!
bisection,very insightful
# cube root calc
cube = input("Please input a number: ")
cube = int(cube)
for guess in range(abs(cube) + 1):
if guess**3 == abs(cube):
if cube > 0:
print("The cube root of", cube, "is", guess)
break
elif cube < 0:
guess = -guess
print("The cube root of", cube, "is", guess)
break
if guess**3 > abs(cube):
print("Not a perfect cube")
38:00 the fact Sophie chosed 76 makes me wonder if she had an inkling as to what the teacher was aiming at.
I mean a middle guess +1 is the hardest to find in a bisectional search.
So either Sophie was lucky, or she's a sly fox >:)
lol right
Absolutely well done and definitely keep it up!!! 👍👍👍👍👍
picking up python, I know absolutely nothing but I am 3 lectures in. Anybody else actually following along with the whole series and doing the problems the course gives ?
You may check on internet by searching the topics names and basic problems regarding them
Im the same, how did it go pal?
@@jamaldangelo4227 oh wow it’s been a year, it went so well lol, I am much more confident in my programming abilities and have done a lot of really cool projects. Coding has been a very rewarding journey
@@thomasgarman6353 Good to hear pal, I'm currently just starting now, trying to find a coding job in the next 6-9 months...
nice lecture
Who edited this? Every time she's pointing and talking about something on the board the camera is on her for some reason. Really bad practice.
yup that is so dumb edition
I am sending a packet of thanks to mit for this clear explanation
And sorry I can't afford a Google product so only thank you
can''t believe sophie didn't pick 69
I can't believe Bell pronounces gif "jif"
Creep
Very useful
Thanks
# This might be of help to someone as I had trouble following along due to this misconception
# Assign the string "MIT" to variable "i"
i = 'MIT'
# Print the elements of variable "i" starting from index 0 and ending at index 3 but not including index 3 - "[0:3]"
print(i[0:3])
# When working with an index remember that it starts at 0 "[0:]"
# when specifying where you would like to end the index "[:3]" it's up to the index value 3 but not including it
# So in this example - "M" is located at index 0
# "I" is located at index 1
# "T" is located at index 2
# >>> MIT
# If we were to print the elements of variable "i" at index "[0:2]" it would be
print(i[0:2])
# >>> MI
# "M" is located at index 0
# "I" is located at index 1
# "T" is located at index 2
# Rember it's up to the index value 2 but not including it
You're a saviour.
this is very helpful
God bless you.
Here's what I have for bisection search that accounts for negative numbers and abs (numbers) < 1:
cube = -0.027
epsilon = 0.0001
num_guesses = 0
if cube >= 1:
low = 0
high = cube
elif cube >= 0 and cube < 1:
low = cube
high = 1
elif cube < 0 and cube > -1:
low = -1
high = cube
else:
low = cube
high = 0
if abs(cube) == 1:
guess = cube
else:
guess = (high + low) / 2.0
while abs(guess**3 - cube) >= epsilon:
if guess**3 < cube:
low = guess
else:
high = guess
guess = (high + low) / 2.0
num_guesses += 1
print('num_guess is', num_guesses)
print(guess, 'is close to cube root of', cube)
Why aren't we getting cube root of 27 and 8120601 in form of x.xx as we always increment guess by second decimal place.
37:00 that's exactly how one should play the clock game on the price is right.
0:34:43 I would add 'and abs(guess**3)
Are there any recommended videos to watch on CZcams following this course to build more upon Python knowledge? Thanks!
Her Voice is Good and the Explaining is perfect ! thanks M-I-T the game of guess was Fun :D .
Great. I was hoping she would use Newton-Raphson or secant method for the cube root calculation.
Dammnnn what an experience should be studying at MIT!!!
The idea of creating something to cheer oneself up is just funny
At 10:05, a typo in screen slides ...evaluates to "hgfedbca", should be "hgfedcba".
when should we start doing those given assissgnment
Correct me if I'm wrong but in 43:50 when the professor says the code works only for positive cubes, she makes an example of 0.5 not working, but that is the positive cube of 0.79... So I guess the correct statement to make is that this algorithm works only for positive cubes "bigger or equal to 1".
My understanding is that her code does not work for 2 situations: 1) negative cubes 2) x
@@wenjucui9272 I know she said it is a simple if statement but I can't figure it out. What did you do to make it work?
My thought is:
if cube < 0:
guess = -guess
@@Adam-bq2us I considered two situations:
if cube >=0:
low=0
high=cube
guess = (high + low)/2.0 then do the while loop comparing epsilon;
else:
low=cube
high=0
guess = (high + low)/2.0 then do the while loop again to compare with epsilon.
hope this helps. I haven't worked out the between 0, 1 situation.
@@Adam-bq2us Before running the code listed just state If cube is >= 1 then {insert code from course}
that's all that is needed
@@bkpickell can you please give the full solution? I cannot find any
@21:20 Clean and peaceful
What is the answer of cube = 27 on the exercise. I rewrote the code on the IDE but the execution never ended, why?
Help, please
LOL Happens, Your increment is may be too small, so that it is maybe taking too much time.
Dude the same thing happened for me. I never got an answer even after changing the 27 to some other value.
Try.......If you copied and pasted from slides the last three lines may be indented. they should start at beginning of each line.
thanks!
An "all possible inputs" approach for cheer loop (Eric taught me 😐):
an_letters = "aefhilmnorsxAEFHILMNORSX"
word = input("I will cheer for you!. Enter a word:
")
times = int(input("Enthusiasm level (1 - 10):
"))
if times > 10:
while times > 10:
times = int(input("Please ensure an enthusiasm level between 1-10
"))
for char in word:
if char == ' ':
continue
if char in an_letters:
print("Give me an " + char + "! " + char)
else:
print("Give me a " + char + "! " + char)
print("What does that spell?")
print((word + "!!!
")*times)
39:37 bisection search code
Guess & Check:
cube = -27
# only guess the first natural number for which guess**3 >= cube
for guess in range(abs(cube)+1):
if guess**3 >= abs(cube):
break
# return perfect cube, if exists
if guess**3 == abs(cube):
if cube < 0:
print("Cube root of " + str(cube) + " is " + str(-guess))
else:
print("Cube root of " + str(cube) + " is " + str(guess))
# if there exists no perfect cube
else:
print(str(cube) + " is not a perfect cube")
I love her.
MIT one and only!👍🇷🇸
Is there a typo at 6:56? s[: : -1] -> "hgfed'BC'a" doesn't make sense, unless it's supposed to be "...cba"
Yes it is cba or BCa
true, there is a mistake. this comment should have a lot of like !!!
Nice tutorial and lesson. Just a small note, IMHO, on ~35:00 Anna made a small "mistake" when added "and guess
What I get from the approximation algorithm is that it will only give you an answer if the difference between guess**3 and cube is equal to epsilon, if it manages to jump above epsilon, guess will increase in value until it is
cube = 10000 epsilon = 0.1
guess = 0.0
increment = 0.01
num_guesses= 0
while abs(guess**3 -cube) >= epsilon: # and guess = epsilon and guess**3 > cube:
# new inserted line
print("sorry the the epsilon jumped up and the cube is not found the last guess was",c)
# new inserted line
break
# new inserted line
print('num_guesses=', num_guesses)
if abs(guess**3 -cube) >= epsilon:
print('Failed on cube root of', cube)
else:
print(guess, 'is close to the cube root of', cube)
In the approximate way of finding cube root codes: the guesses is increasing by guess += increment. I may think the output of guess should be multiply of increment, why the final output is something like .999999999998
Could you please tell me which programming environment python do you use in the lecture?
they use anaconda but you can use geany also. I prefer geany
It's called Spyder, it comes with anaconda. Link to website --> anaconda.org/anaconda/spyder
What does she mean with we can use for loops to iterate ANY SEQUENCE OF VALUES?? Im learning coding from scratch and some terms and concepts are quite sneaky to comprenhend, dont be to harsh pleas, and thanks
18:00 nice example
nice work by DR. ANNA BELL and MIT as well..
cube = 27
epsilon = 0.01
num_guess = 0
low = 0
high = cube
guess = (high + low) / 2
while abs(guess**3 - cube) >= epsilon:
print(abs(guess**3 - cube), guess, (guess ** 3))
if guess**3 < cube:
low = guess
else:
high = guess
guess = (high + low) / 2
num_guess += 1
print('num_guess =', num_guess)
print(guess, 'is close to cube root of', cube)
13:05 for loops
when the robots are cheering, can you index word[1,3] in the for loop?
for char in word[1,3]:
The index notation uses colons, not commas, so it would be word[1:3]. But other than that, yes, you could do that, and then you would loop over only the characters that are in that substring. So if the original string word is "ROBOTS", the substring word[1:3] would be "OB".
I’ve watched this twice, and it’s still hard as hell for me to grasp
Thanks, now i can learn python in high school
27:39 what if the cube is not perfect and negative? ,
my teacher is beautyfull
How do you do a bisection search for a cuberoot when x is a decimal? I can’t be find an answer anywhere.
if abs(cube) < 1.0:
high = 1.0
This worked for me. Logic is that if 1 is less than 0 we just need to change the higher bound and a good number to change it to is 1 because the answer won't be greater than one anyway.
@@rysknet if cube < 1:
high = 1
low = guess
And even with that you may have an infinite loop because doing comparison for float numbers is tricky, see the style guide pdf
when I try to run the code at 32:07, my cell just says In[*] instead if In[a number] and the cell doesn't even run. Anyone know what's going on? Note: the rest of my notebook until this point is running perfectly.
go to the kernel tab, click on interrupt. then try again
Cube root simple guess.
Why does that code keeps running?
38:50 why was my first thought before she even explained the method to choose e as my number
and guess**3
S[4:1:-2] evaluates to "eca"
someone please give me the bisection solution for cube = 0.5 and cube < 0 🙏🙏
My teacher in INDIA taught me in same way, iam studing in class 11th feeling too good after watching this, that i have same access to learning as any other brilliant student have 💛💛😇😇🇮🇳🇺🇸
Hello bro I am indian
Im sorry for shouting GRADIENT DESCENET at the computer when she said that epsilon missed its stop due to inremention :)
Can someone help me out - surely the code at 29:55 is wrong? The While loop should not run because the condition is not true i.e. guess**3 - cube is NOT greater than or equal to 0.1.
Rather 0x0x0 - 27 is LESS than 0.1? So surely the While loop would not run in the first place?
The abs is a function that returns the absolute value of the argument, so in this case abs(-27) returns 27, which in turn is greater than (or equal) to 0.01 (epsilon)
13:29 0,1,2,3 since it starts from 0
21:25 recap
13:25 range(4) is not 0,1,2,3,4
0,1,2,3