Description
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 f0(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 . The algorithm is as follows:
Algorithm:
- Starting from an initial guess x0, calculate the error of your guess f(x0).
, then you are done because x0 is close enough to the root. Otherwise, a better approximation than x0 is given by.
- Keep updating your guess xn using the formula until you have
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:
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.
