**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]