**CS 111 f19 - Lecture 12 Worksheet**
---
# Newton's Method
Issac Newton devised an effective way to estimate the square root of a number. You start with a simple guess like the number divided by two. Then, you repeatedly refine your guess with the following formula: $new guess = \frac{guess + \frac{x}{guess}}{2}$ where $x$ is the original number. It turns out that it doesn't take many refinements to get very close to the exact square root.
Write a function that takes a number and uses Newton's Method to return an estimate of the square root of that number. How many times should you refine the estimate? Until it converges (i.e., the difference between the existing estimate and an improved estimate gets very small). You can use a `while` loop to apply the above formula until this occurs.
+++++
# `is_valid_variable_name`
I'm trying to write a function that takes a string and returns whether that string would be a valid variable name. Remember that a variable name can only have numbers, letters, and underscores. In addition, a variable name cannot start with a number. Describe why each of the versions below will not return the correct result.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
def is_valid_variable_name1(name):
if name[0].isdecimal():
return False
for c in name:
if c.isalnum() or c == "_":
return True
else:
return False
def is_valid_variable_name2(name):
ok_characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_"
return name[0] in ok_characters and name in ok_characters
def is_valid_variable_name3(name):
result = True
for c in name:
result = c.isalnum()
result = c == "_"
return result and name[0].isdecimal()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+++++
# List Mystery
What will be printed by the following code? Make a table with the values of `v` and `i` after each line to help you work through it.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python linenumbers
v = [4, 5, 6, 7, 8, 9]
v[0] = v[-1] - v[-2]
print(v)
i = v[0] + 2
v[i] = v[i - 2] - v[i - 3]
print(v)
v[len(v) - 2] = i * 2
print(v)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+++++
# Unrolling a Loop
One way to think about what a Python `for` loop will do is to *unroll* the loop into the repeated code without the loop. This can help make it clearer what will occur. For example, we would turn this code
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
v = [2, 3, 4]
for i in range(len(v)):
print(v)
v[i] = v[i] * v[i]
print(v)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
into this code by working out what the value of `i` will be each time around the loop
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
v = [2, 3, 4]
# first time around the loop
i = 0
print(v)
v[i] = v[i] * v[i]
# first time around the loop
i = 1
print(v)
v[i] = v[i] * v[i]
# first time around the loop
i = 2
print(v)
v[i] = v[i] * v[i]
# after the loop
print(v)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This helps us see that the list `v` will be printed four times: before each change, and then after the last change. What will the four lines of printed output be?
Now consider the this more complicated loop:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
v = [3, 2, 1, 0, -1, -2, -3]
for i in range(1, len(v) - 1):
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Use the unrolling technique to work through what will be printed out.