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

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
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

[vibhumaheshwari]

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!

[farmcat]

I love Dr. Bell's enthusiasm for this. Makes learning it so much more fun!

[flvsedl]

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)

[Boobio--ZOO-BOOKS]

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.

[nmfkcbb]

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 :)

[protoype]

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 :)

[llwqoww]

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.

[rustycanofbeans]

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.

[aumkaarpranav]

Wow! They clapped at the end. Can't remember ever being so much into the class that I end up clapping.

[onemilee]

Hi guys. I'm going to thank the MIT team. Thank you, for these awsome courses.

[mohdyasirfaridi]

It was very useful. HUGE THANKS TO MIT.

[roshanshanbhag]

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.

[sp]

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?

[spyinsecret]

She is an amazing teacher! Explain it so clearly and fun. Thank you so much!

[PedramNG]

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.

[leonardoagostini]

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) <= abs(cube):
# the increment must be negative if cube < 0 and intitial guess = 0, otherwise (guess**3 - cube) will always increase as guess increases
guess += cube/abs(cube)*increment
num_guesses+=1
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)

[alienlan]

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. :(

[kuuz]

college drop out learning python for free from MIT, who would have ever thought...

[qcislander]

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?

[markmahathey]

this was a good lecture. I hope I watch them all.