**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.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
def sqrt(x):
guess = x / 2
newguess = (guess + x / guess) / 2
while abs(guess - newguess) > 0.000001:
guess = newguess
newguess = (guess + x / guess) / 2
return newguess
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+++++
# `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()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
`is_valid_variable_name1`: because `return` exits the function, this loop will only check the first character of `name` and then return.
`is_valid_variable_name2`: we need to make sure `name` doesn't start with a number, but `ok_characters` contains numbers, so `name[0] in ok_characters` won't do the check that we want. Also, `name in ok_characters` will only be `True` if the entire string `name` appears in `ok_characters` (e.g., only when `name` is something like `"abcd"`). So we'd need a loop over each character. A fixed version might look like
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
def is_valid_variable_name2(name):
ok_characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_"
for c in name:
if c not in ok_characters:
return False
return name[0] not in "012345679"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
`is_valid_variable_name3`: `result` keeps getting overwritten with checks on the current character in the loop, so it won't accumulate the way we want. Second, we want the first character to **not** be a number. Here's a fixed version:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
def is_valid_variable_name3(name):
result = True
for c in name:
result = result and (c.isalnum() or c == "_")
return result and not 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)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[1, 5, 6, 7, 8, 9]
[1, 5, 6, 4, 8, 9]
[1, 5, 6, 4, 6, 9]
+++++
# 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.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Python
v = [3, 2, 1, 0, -1, -2, -3]
i = 1
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
i = 2
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
i = 3
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
i = 4
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
i = 5
v[i - 1] = v[i]**2 + v[i + 1]**2
print(v)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This prints
[5, 2, 1, 0, -1, -2, -3]
[5, 1, 1, 0, -1, -2, -3]
[5, 1, 1, 0, -1, -2, -3]
[5, 1, 1, 5, -1, -2, -3]
[5, 1, 1, 5, 13, -2, -3]