Homework 2  Write a function longestpath(d)

 Homework 2 
Instructions: Name your file hw2.py and submit on CCLE. Add comments to each function.
• Problem 1:
Write a function longestpath(d) that finds 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 find 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 f
0
(x), and a desired tolerance ? (usually
a very small positive number), your goal is to find a desired value x
∗ which is close
enough to a root of f(x) such that |f(x
∗
)| ≤ ?. The algorithm is as follows:
Algorithm:
1. Starting from an initial guess x0, calculate the error of your guess f(x0).
2. If |f(x0)| ≤ ?, 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)
f
0(xn)
until you have
|f(xn)| ≤ ?.
Instructions:
– Write your algorithm in a solve function that takes as input a function f(x),
its derivative f
0
(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
f
0
(x), and initial guesses x0:
f(x) = x
2 − 1, f
0
(x) = 2x, x0 = 3
f(x) = x
2 − 1, f
0
(x) = 2x, x0 = −1
f(x) = exp(x) − 1, f
0
(x) = exp(x), x0 = 1
f(x) = sin(x), f
0
(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.
Due 5 PM, Wednesday, October 16 Homework 2 PIC 16
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.