
Laboratory 7: Dictionaries, Recursion, Rootfinding (Newton's method)
Prerequisites: +recursion, +dictionaries, +finite differences
Create a file training7.py which provides the following functions:
A function count_chars(s) which takes a string s and returns a dictionary. The dictionary's keys are the set of characters that occur in string s. The value for each key is the number of times that this character occurs in the string s. Examples:
In [ ]: count_chars('x')
Out[ ]: {'x': 1}
In [ ]: count_chars('xxx')
Out[ ]: {'x': 3}
In [ ]: count_chars('xxxyz')
Out[ ]: {'x': 3, 'y': 1, 'z': 1}
In [ ]: count_chars('Hello World')
Out[ ]: {' ': 1, 'H': 1, 'W': 1, 'd': 1, 'e': 1, 'l': 3, 'o': 2, 'r': 1}
Note that the order in which the keyvalue pairs are listed in the
output dictionary is not important.
A function derivative(f, x) which computes a numerical
approximation of the first derivative of the function f(x) using
central differences. The value that the function returns is
Example:
In [ ]: def f(x):
...: return x * x
In [ ]: derivative(f, 0)
Out[ ]: 0.0
In [ ]: derivative(f, 1)
Out[ ]: 2.0000000000575113
In [ ]: derivative(f, 2)
Out[ ]: 4.000000000115023
Note that you may not get exactly the same numbers as shown
above.
Modify the derivative function such that it takes an optional
third parameters eps to represent the greek letter epsilon in
the equation above. The parameter eps should default to
1e6.
Examples:
In [ ]: import math
In [ ]: derivative(math.exp, 0, eps=0.1)
Out[ ]: 1.000416718753101
In [ ]: derivative(math.exp, 0)
Out[ ]: 1.0000000000287557
In [ ]: derivative(math.exp, 0, eps=1e6)
Out[ ]: 1.0000000000287557
Save your file training7.py under the new name lab7.py (as you will need to use the derivative() function from the training part in the assessed part) and add the following functions:
A function newton(f, x, feps, maxit) which takes a function f(x) and an initial guess x for
the root of the function f(x), an allowed tolerance feps and the maximum number of iterations that are allowed maxit. The newton function should use the following NewtonRaphson algorithm:
while f(x) > feps, do
x = x  f(x) / fprime(x)
where fprime(x) is an approximation of the first derivative
(df(x)/dx) at position x. You should use the derivative function from the training part of this lab.
Make sure you copy the derivative function definition from training7.py into lab7.py (there are more elegant ways of doing this, but for the purpose of the assessment, this is the most straightforward way we recommend).
If maxit or fewer iterations are necessary for f(x) to become smaller than feps, then the value for x should be returned:
In [ ]: def f(x):
....: return x ** 2  2
....:
In [ ]: newton(f, 1.0, 0.2, 15)
Out[ ]: 1.4166666666783148
In [ ]: newton(f, 1.0, 0.2, 15)  math.sqrt(2)
Out[ ]: 0.002453104305219611
In [ ]: newton(f, 1.0, 0.001, 15)
Out[ ]: 1.4142156862748523
In [ ]: newton(f, 1.0, 0.001, 15)  math.sqrt(2)
Out[ ]: 2.1239017571339502e06
In [ ]: newton(f, 1.0, 0.000001, 15)  math.sqrt(2)
Out[ ]: 1.5949463971764999e12
If more than maxit iterations are necessary for the function
newton, then the newton function should raise the
RuntimeError exception with the message:
Failed after X iterations where X is to be replaced with the number of
iterations:
In [23]: def g(x):
....: return math.sin(x) + 1.1 # has no root!
....:
In [24]: newton(g, 1.0, 0.02, 15)
Traceback (most recent call last):
File "<ipythoninput60a9db3f67256>", line 1, in <module>
newton(g, 1.0, 0.02, 15)
File "..lab7.py", line 16, in newton
raise RuntimeError("Failed after %d iterations" % maxit)
RuntimeError: Failed after 15 iterations
The relevant line of Python to be executed if the number of maxit iterations is reached, is
raise RuntimeError("Failed after %d iterations" % maxit)
A function is_palindrome(s) which takes a string s and
returns the value True if s is a palindrome, and returns
False otherwise. (Note that the return value is not the
string "True" but the special Python value True  see the
section True and False in the appendix below. The same applies
to False.)
A palindrome is a word that reads the same backwards as forwards, such as madam, kayak, radar and rotator.
Hints for a suggested algorithm:
 if s is an empty string, then it is a palindrome.
 if s is a string with one character, then it is a palindrome.
 if the first letter of s is the same as the last letter of s, then s is a palindrome if the remaining letters of s (i.e. starting from the second letter, excluding the last letter) are a palindrome.
Examples:
In [ ]: is_palindrome('rotator')
Out[ ]: True
In [ ]: is_palindrome('radiator')
Out[ ]: False
In [ ]: is_palindrome('ABBA')
Out[ ]: True
We treat small letters (e.g. a) and capital letters
(e.g. A) as different letters for this exercise: the string
ABba is thus not a palindrome.
Suggestion: if you struggle with the concept of recursion, take
some time to study the output of this recursive factorial
computation.
True and False
True and False are special boolean values (of Python type bool), and different from strings. Here is some demonstration of this:
In [ ]: a = True
In [ ]: b = "True"
In [ ]: type(a)
Out[ ]: bool
In [ ]: type(b)
Out[ ]: str
In the function is_palindrome() above, you must return the bool value True or False, but not the string "True" or the string "False".
Last updated: 20161030 at 12:17
