Description
Instructions: Name your le hw2.py and submit on CCLE. Add comments to each function.
Problem 1:
Write a function longestpath(d) that nds the length of the longest path, (a : b) !
(b : c) ! , in a dictionary d. It counts each pointer from a key to a value as one
step. For example, the path (a : b) ! (b : c) has length 2. To avoid cycles, we do not allow any key to appear more than once in a path (as a key).
Test cases:
d1 = {“a”:”b”,”b”:”c”}
d2 = {“a”:”b”,”b”:”c”,”c”:”d”,”e”:”a”,”f”:”a”,”d”:”b”} longestpath(d1) should return 2.
longestpath(d2) should return 5.
Problem 2:
Implement Newton’s method (also known as the Newton-Raphson method) to nd a root (zero) of a function. No prior knowledge of this algorithm is needed. Just follow the steps.
Given a function f(x) , the function’s derivative f0(x), and a desired tolerance (usually a very small positive number), your goal is to nd a desired value x which is close enough to a root of f(x) such that jf(x )j . The algorithm is as follows:
Algorithm:
-
-
Starting from an initial guess x0, calculate the error of your guess f(x0).
-
-
-
If jf(x0)j , then you are done because x0 is close enough to the root. Otherwise,
-
-
a better approximation than x0 is given by x1 = x0
f (x0)
:
f 0 (x0)
3. Keep updating your guess xn using the formula xn+1 = xn
f (xn)
until you have
f 0 (xn)
jf(xn)j :
Instructions:
{ Write your algorithm in a solve function that takes as input a function f(x), its derivative f0(x), an initial guess x0 and the tolerance . This function can be called like this:
print solve(lambda x: [x**2-1, 2*x], 3, 0.0001)
{ Test your solve function using the following functions f(x), their derivatives f0(x), and initial guesses x0:
f(x) = x2 1, f0(x) = 2x, x0 = 3
f(x) = x2 1, f0(x) = 2x, x0 = 1
f(x) = exp(x) 1, f0(x) = exp(x), x0 = 1
f(x) = sin(x), f0(x) = cos(x), x0 = 0:5.
Use a calculator to test if the solutions provided by your code are correct, and put results in comment in your script.
Suggestions:
{ You can start by hard-coding the function, its derivative, the initial guess, and the tolerance in your script without getting user input. This will help you better understand the algorithm.
{ If you are still confused, watch this video for an example of Newton’s method with two iterations: https://www.youtube.com/watch?v=xdLgTDlFwrc.
